User:Hakerh400/Unordered set in Haskell

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.