module Set where
Self-contained reusable chunks of code should be organized into modules.
data Set a = Empty | Set a (Set a)
deriving (Read, Show)
All-caps types are not a thing, just
Set is fine. Single letter constructors are uncommon too, so instead of
E use a meaningful name like
Empty. Constructors can take multiple arguments, so don't use tuples where you don't have to. I'll also point out that this data type you've defined is isomorphic to
[a]. Besides the magic square brackets, Haskell lists are a data type like any other, i.e.
data [a] =  | (:) a [a]. Notice the similarity? Is this a situation where you need a new
datatype or might it make sense to use a
-- Test data
setx, setx2, sety, setys :: Set Int
setx = listToSet [1,2,3,4]
All top-level bindings should be given a type signature, get into the habit now and you'll save yourself the frustration of a lot of cryptic misplaced error messages later. These names are all over the place too, they should be more consistent, e.g.
exampleSetA, exampleSetB, exampleSetC. Don't crowd together functions and their arguments, leave some space and let it breathe.
fromList :: [a] -> Set a
fromList  = Empty
fromList (x:xs) = Set x (fromList xs)
fromList is a common name for converting lists to arbitrary datatypes. When it conflicts with other names from modules you have imported, you disambiguate with qualified imports, not a menagerie of globally unique names.
(x:xs) is a common naming pattern for lists, that is, some variable
e, or whatever, and then the plural form (
es... it's a pun, get it?). Again, space out function application, tuples are a datatype in Haskell, not a method of passing arguments.
member :: (Eq a) => a -> Set a -> Bool
member _ Empty = False
member a (Set x xs) | a == x = True
| otherwise = member a xs
A common function name for testing set membership is
member. When you don't use an argument name in the body of a function, replace it with
_. If you compile with
-Wall (as you should), GHC will warn you about unused bindings. That is, names that you defined in a function body but didn't use. Often this can help you to notice errors before you ever get to running your code! Use guards (e.g.,
| a == x) instead of
if statements where you can. Guards are like a multiway
if, when you have multiple cases it becomes much clearer than chaining
ifs, get into the habit now, there's no reason not to.
null :: Set a -> Bool
null Empty = True
null _ = False
Use pattern matching where you can, it's more explicit than equality testing, often faster, and helps you avoid unnecessary constraints. Notice how my version lacks the
(Eq a) constraint?
-- Mourn headSet and tailSet here
These functions are meaningless on
Sets. Being unordered collections,
Sets do not have meaningful heads or tails, so you should not leak implementation details by exposing them.
insert :: (Eq a) => a -> Set a -> Set a
filter :: (a -> Bool) -> Set a -> Set a
intersection :: (Eq a) => Set a -> Set a -> Set a
union :: (Eq a) => Set a -> Set a -> Set a
isSubset :: (Eq a) => Set a -> Set a -> Bool
Around now you're starting to feel the pain of your choice of
Set representation. Implementations are slow and unwieldy. For instance, your version of
intersection is an \$O(n^2)\$ operation. You can improve running times by utilizing any of a number of standard algorithms, try using balanced binary trees to represent your sets instead of linked lists.
instance (Eq a) => Eq (Set a) where
Instead of making up another name, write your own instances for standard functions like equality. If the derived instance doesn't do what you want, don't use it, don't keep it around (because you'll be unable to keep it from being exported to users of your library), and don't let it clutter up good namespace.