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