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

[Felipe Almeida Lessa]

On Fri, Dec 30, 2011 at 8:53 PM, Robert Weisser <Robert.Weisser at gmx.com> wrote:
>  newtype Set a = Set (a -> Bool) (version 1)

This one, certainly.

>  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?

You really can't look inside the function to decide if they are equal.
 The only way of doing it would be enumerating all possible items that
could be in a set and checking them.  Something like

eqSet s1 s2 = and [memSet s1 x == memSet s2 x | x <- allValues]

class AllValues a where
  allValues :: [a]

instance AllValues Bool where
  allValues = [True, False]

instance AllValues Char where
  allValues = ['\0'..]

instance AllValues Int where
  allValues = [0..] ++ [-1,-2..]

and so on.  Note that usually this is a really bad idea and perhaps it
would be better to not implement eqSet at all.

HTH,

-- 
Felipe.