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