In this tutorial we explain how to implement a pure unordered set in Haskell.

## Problems with the standard implementation

The standard implementation `Data.Set` implicitly assumes the axiom of choice (that is, it assumes that all sets are well-ordered). Almost all functions provided by `Data.Set` require that the set elements implement the `Ord` interface (that is, the elements can be ordered). This is really an unecessary constraint. It seems more like a hack, added just to satisfy the performance requirements (because of the internal binary tree implementation).

## Basic operations

Instead of assuming the axiom of choice, why not just assume the axiom of extensionality and nothing more? That would allow us to require only the `Eq` constraint and not the `Ord` constraint.

So, what are the basic set operations from which we can build all other set operations? We need a way to construct a set from a list. We also need a function that checks whether an element belongs to the given set. Finally, we need some sort of a higher-order function that transforms each element of the given set. Therefore, we need to implement the following functions:

fromList :: (Eq a) => [a] -> Set a setElem :: (Eq a) => a -> Set a -> Bool setMap :: (Eq a, Eq b) => (a -> Set b) -> Set a -> Set b

Function `fromList` takes a list of elements and constructs a set. It ignores duplicates.

Function `setElem` takes an element and a set and returns `True` iff the element belongs to the set.

Function `setMap` takes a function and a set as arguments, then applies the function to all elements and takes the union of all the results.

## Implementation

data Set a = SetCtor [a] fromList :: (Eq a) => [a] -> Set a fromList = foldr insert (SetCtor []) where insert elm set@(SetCtor elms) = if elm `setElem` set then set else SetCtor (elm : elms) setElem :: (Eq a) => a -> Set a -> Bool a `setElem` (SetCtor b) = a `elem` b setMap :: (Eq a, Eq b) => (a -> Set b) -> Set a -> Set b setMap f (SetCtor elms) = foldr (union . f) (SetCtor []) elms where union (SetCtor a) (SetCtor b) = fromList (a ++ b)

As you can see, we implement set using a list. However, the order of the elements is not important.

Now, in order to introduce the axiom of extensionality, we need to implement `Eq` interface for sets:

instance (Eq a) => Eq (Set a) where SetCtor a == SetCtor b = all (`elem` b) a && all (`elem` a) b

## Other set operations

The set operations provided above (`fromList`, `setElem`, `setMap` and `==`) are enough to implement all other relevant set operations. The challenge for the reader of this article is to implement the following operations.

Note: You are not allowed to use `SetCtor` in destructuring to obtain the list of elements!

-- Create a set with no elements empty :: (Eq a) => Set a -- Create a set with exactly one element singleton :: (Eq a) => a -> Set a -- Create a set with two elements (unordered pair) -- In case the elements are the same, the resulting -- set will have just one element upair :: (Eq a) => a -> a -> Set a -- Return True iff the given set is empty isEmpty :: (Eq a) => Set a -> Bool -- Given a set of sets, return the union of all its elements unions :: (Eq a) => Set (Set a) -> Set a -- Given two sets, return their union union :: (Eq a) => Set a -> Set a -> Set a -- Insert an element into the given set insert :: (Eq a) => a -> Set a -> Set a -- Is there an element that satisfies the condition? some :: (Eq a) => (a -> Bool) -> Set a -> Bool -- Do all elements satisfy the condition? every :: (Eq a) => (a -> Bool) -> Set a -> Bool -- Given two sets, return their intersection intersect :: (Eq a) => Set a -> Set a -> Set a -- Given two sets, return their difference dif :: (Eq a) => Set a -> Set a -> Set a -- Remove an element from the given set remove :: (Eq a) => a -> Set a -> Set a -- Return the size of the given set as an integer size :: (Eq a) => Set a -> Integer -- Returns the power set of the given set powerSet :: (Eq a) => Set a -> Set (Set a) -- Is the first set a subset of the second set? isSubsetOf :: (Eq a) => Set a -> Set a -> Bool -- Is the first set a proper subset of the second set? isProperSubsetOf :: (Eq a) => Set a -> Set a -> Bool -- Return the Cartesian product of two sets cartesianProduct :: (Eq a, Eq b) => Set a -> Set b -> Set (a, b) -- Check whether two sets are disjoint disjoint :: (Eq a) => Set a -> Set a -> Bool -- Apply a function to each element from the given set smap :: (Eq a, Eq b) => (a -> b) -> Set a -> Set b -- Return the disjoint union of two sets disjointUnion :: (Eq a, Eq b) => Set a -> Set b -> Set (Either a b) -- Filter all elements that satisfy the predicate sfilter :: (Eq a) => (a -> Bool) -> Set a -> Set a -- Partition the set into two sets, one with all elements that -- satisfy the predicate and one with all elements that -- do not satisfy the predicate partition :: (Eq a) => (a -> Bool) -> Set a -> (Set a, Set a)

## Converting a set back to the list

Now, how do we convert a set back to the list, that is, how to obtain the elements of the set (of course, without using the `SetCtor` destructuring)? The answer is simple: you can't an you shouldn't. Obtaining a list of elements would imply that the elements can be ordered, which is not what we originally assumed. We intentionaly want to work with elements that do not implement the `Ord` interface. On the other hand, all of the above functions can be implemented (more or less easily). Every function from Haskell's `Data.Set` that does not require the `Ord` constraint can be implemented.