[Haskell-beginners] Representing a Set using a boolean function

[Robert Weisser]

 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