How Do I implement a Set as an abstract data type in Haskell?

Question

I have to implement a set as an abstract data type in Haskell. The task is the following:

A set models a set of elements. It is valid that a set is either the empty set or recursively consists of one element and the rest of the set. The functions isEmpty, contains, add, remove are to be defined.

• The function isEmpty checks if a set is empty.
• contains takes a set and an element and indicates whether the set contains the element.
• add takes a set and an element and adds the element to the set if it is not already in the set. is not already contained in the set
• The remove function takes a set and an element and removes the element from the set, if the element is already in the set. If the element is not part of the set, the the function returns an error.

im struggling with the recursive part of the task, I have no idea. And how do I implement the "contains" specifically?

module Set (Set(EmptySet, MkSet), isEmpty, contains, add, remove)
    where
        
data Set a = EmptySet | MkSet a (Set a)
    deriving (Show, Eq, Enum, Ord, Read)

isEmpty :: Set a -> Bool
isEmpty EmptySet = True
isEmpty (MkSet a as) = False

contains :: Set a -> a -> Bool
contains EmptySet = error "no element in set."
contains (MkSet a as) a = True
contains (MkSet a as) b = False

add :: a -> Set a -> Set a
add a as = (MkSet a as)

remove :: Set a -> Set a
remove EmptySet = error "No remove operation on empty set allowed."
remove (MkSet a as) = as

(https://i.stack.imgur.com/W8kSj.png)

Answer 1

The pattern contains (MkSet a as) a which uses the pattern variable a twice is called a nonlinear pattern in the literature. Nonlinear patterns are not allowed in Haskell. Instead you must check equality explicitly like this:

contains (MkSet a as) b
  | a == b = ...
  | otherwise = ...

This also requires adding contains :: Eq a => Set a -> a -> Bool in the type signature.

Note that the fact that a and b are different variables doesn't necessarily mean that they must be assigned different values when matching.

Secondly, your case contains (MkSet a as) b = False doesn't take into account that the element might be contained in as (hint: use recursion).

And thirdly, it's not an error to ask if an element is in an empty set (thanks chepner). It should just return False in that case.