I'm an advanced beginner Haskell programmer. I implemented a set data type in Haskell and I wanted to find out if I made correct choices when writing it. Would there be a way to improve some of the algorithms like intersection etc.
data SET a = E | Add(a, SET a) deriving (Eq, Ord, Read, Show)
--test data
setx = listToSet[1,2,3,4]
setx2 = listToSet[3,4,2,1]
sety = listToSet[3,4,5,6]
setys = listToSet[3,4]
listToSet :: [a] -> SET a
listToSet [] = E
listToSet (s:x) = Add(s, listToSet x)
inS :: (Eq a) => a -> SET a -> Bool
inS a E = False
inS a (Add(value, set)) = if (value == a)
then True
else (inS a set)
nullSET :: (Eq a) => SET a -> Bool
nullSET s = s == E
headSET :: SET a -> a
headSET (Add(v, s)) = v
tailSET :: SET a -> SET a
tailSET (Add(v, s)) = s
addToSet :: (Eq a) => a -> SET a -> SET a
addToSet a (Add(value, set)) = if (inS a (Add(value, set)) == False)
then Add(a, Add(value, set))
else (Add(value, set))
setFilter :: (Eq a) => (a -> Bool) -> SET a -> SET a
setFilter f s
| nullSET s = E
| f h == False = setFilter f t
| otherwise = Add(h, setFilter f t)
where
h = headSET s
t = tailSET s
intersection :: (Eq a) => SET a -> SET a -> SET a
intersection s1 s2 = setFilter (\x -> inS x s1) s2
union :: (Eq a) => SET a -> SET a -> SET a
union set E = set
union set (Add(value2, set2)) = if (inS value2 set == False)
then Add(value2, (union set set2))
else union set set2
subSet :: (Eq a) => SET a -> SET a -> Bool
subSet set1 set2
| set1 == E = True
| inS h set2 = subSet t set2
| otherwise = False
where
h = headSET set1
t = tailSET set1
setEq :: (Eq a) => SET a -> SET a -> Bool
setEq s1 s2 = (subSet s1 s2) == (subSet s2 s1)