I am working through Thompson's "Haskell The Craft of Functional
programming", 2nd edition. I am not doing this as part of a class.
It is just for my own enjoyment.
I am having a problem with Exercise 16.38. Here is the exercise:
The abstract data type Set a can be represented in a number of
different ways. Alternatives include arbitrary lists (rather
than ordered lists without repetitions) and Boolean valued functions,
that is elements of the type a -> Bool. Give implementations of
the type using these two representations.
Note: the book previously showed a representation of Set a using ordered
lists without repetitions.
I had no problem representing Set a with arbitrary lists. My problem came
when I tried to represent Set a with boolean functions. My first question
was this: which of the following was Thompson asking for?
newtype Set a = Set (a -> Bool) (version 1)
newtype Set a = Set [a -> Bool] (version 2)
I decided on version 1. Version 2 did not seem to have any advantage over
version 1. Also, version 1 resembled something earlier in the book (an
associative list implemented as a boolean function). I had no trouble with
functions in the Module export list (see code below) which did not need
to know the contents of the set. However, when I got to eqSet, I was
stumped. I don't see how any function can see inside the set. I don't know
enough Haskell to be certain, but it looks impossible to me. Is there
something I am missing?
> module Set (
> Set,
> empty, -- Set a
> sing, -- a -> Set a
> memSet, -- Ord a => Set a -> a -> Bool
> union, -- Ord a => Set a -> Set a -> Set a
> inter, -- Ord a => Set a -> Set a -> Set a
> diff, -- Ord a => Set a -> Set a -> Set a
> symmDiff, -- Ord a => Set a -> Set a -> Set a
> eqSet, -- Eq a => Set a -> Set a -> Bool
> subSet, -- Ord a => Set a -> Set a -> Bool
> makeSet, -- Ord a => [a] -> Set a
> mapSet, -- Ord b => (a -> b) -> Set a -> Set b
> filterSet, -- (a -> Bool) -> Set a -> Set a
> foldSet, -- (a -> a -> a) -> a -> Set a -> a
> showSet, -- (a -> String) -> Set a -> String
> card) -- Set a -> Int
> where
>
> import Data.List hiding (union)
>
> instance Eq a => Eq (Set a) where
> (==) = eqSet
>
> instance Ord a => Ord (Set a) where
> (<=) = leqSet
>
> newtype Set a = Set (a -> Bool)
>
> empty :: Set a
> empty = Set $ \_ -> False
>
> sing :: Ord a => a -> Set a
> sing y = Set $ \x -> x == y
>
> memSet :: Ord a => Set a -> a -> Bool
> memSet (Set f) x = f x
>
> union :: Ord a => Set a -> Set a -> Set a
> union s1 s2 = Set $ \x -> memSet s1 x || memSet s2 x
>
> inter :: Ord a => Set a -> Set a -> Set a
> inter s1 s2 = Set $ \x -> memSet s1 x && memSet s2 x
>
> diff :: Ord a => Set a -> Set a -> Set a
> diff s1 s2 = Set $ \x -> memSet s1 x && not (memSet s2 x)
>
> symmDiff :: Ord a => Set a -> Set a -> Set a
> symmDiff s1 s2 = union (diff s1 s2) (diff s2 s1)
>
> -- Not exported:
> contents :: Ord a => Set a -> [a]
> contents (Set f) = undefined
>
> eqSet :: Eq a => Set a -> Set a -> Bool
> eqSet (Set xs) (Set ys) = undefined
>
> -- Not exported:
> leqSet :: Ord a => Set a -> Set a -> Bool
> leqSet (Set xs) (Set ys) = undefined
>
> subSet :: Ord a => Set a -> Set a -> Bool
> subSet (Set xs) (Set ys) = undefined
>
> makeSet :: Ord a => [a] -> Set a
> makeSet xs = foldl addElem empty xs
>
> -- Not exported:
> addElem :: Ord a => Set a -> a -> Set a
> addElem (Set f) y = Set g
> where
> g x = if x == y then True
> else f x
>
> mapSet :: Ord b => (a -> b) -> Set a -> Set b
> mapSet f (Set xs) = undefined
>
> filterSet :: (a -> Bool) -> Set a -> Set a
> filterSet p (Set xs) = undefined
>
> foldSet :: (a -> a -> a) -> a -> Set a -> a
> foldSet f x (Set xs) = undefined
>
> showSet :: (a -> String) -> Set a -> String
> showSet f (Set xs) = undefined
>
> card :: Set a -> Int
> card (Set xs) = undefined
For testing, I used the following. I checked individual
values for membership in the union, intersection, etc.
> list1 = [1..4] :: [Int]
> list2 = [3..6] :: [Int]
>
> set1 = makeSet list1
> set2 = makeSet list2
>
> setUnion = union set1 set2
> setInter = inter set1 set2
> setDiff = diff set1 set2
> setSymmDiff = symmDiff set1 set2
Robert Weisser
