Deleting an element of a set

Question

im trying to delete an element from a set but I can't seem to get the syntax right. The datatype is defined as follows:

data Menge el = Menge [el] deriving (Eq, Ord, Show)

and the function is:

loeschen :: (Ord el) => el -> Menge el -> Menge el
loeschen el (Menge []) = Menge []
loeschen el (Menge (x:xs))
    | el == x = Menge xs
    | otherwise = Menge (x : loeschen el (Menge xs))

The error says

Couldn't match expected type: [el] with actual type: Menge el

I've tried several versions of the part after (x:) but I always get the same error.

Answer 1

The problem is that your loeschen el (Menge xs) returns a Menge, so you can not use that with x : loeschen el (Menge xs), since that expects a list as second parameter.

You probably overcomplicate this however. You can just unwrap the list once, remove the item, and then add the result in a Menge, like:

loeschen :: Eq el => el -> Menge el -> Menge el
loeschen el (Menge xs) = Menge (go xs)
  where
    go [] = []
    go (x : xs)
      | el == x = xs
      | otherwise = x : go xs

removing an element from a list is however alread implemented with delete :: Eq a => a -> [a] -> [a], so we can implement this as:

import Data.List (delete)

loeschen :: Eq el => el -> Menge el -> Menge el
loeschen el (Menge xs) = Menge (delete el xs)

Answer 2

Willem Van Onsem's answer is a good way to implement this function; I would certainly do it one of those two ways. However, from your question it seems to me that the sticking point you were struggling with is how to implement a recursive function of type Menge el -> Menge el, and that other answer in some sense avoids the problem by delegating to a recursive function of type [el] -> [el] instead. It's perfectly possible to do what you were trying to do: just make sure to wrap and unwrap the Menge into a list when necessary:

loeschen :: (Ord el) => el -> Menge el -> Menge el
loeschen el (Menge []) = Menge []
loeschen el (Menge (x:xs))
    | el == x = Menge xs
    | otherwise = let Menge xs' = loeschen el (Menge xs)
                  in Menge (x : xs')