[Haskell-beginners] what's a proper way to make a Set typeclass? and why is it not done already?

[Brent Yorgey]

On Wed, Jul 07, 2010 at 03:50:43PM +0300, Markus Läll wrote:
> A few more questions. (I've been trying to make a list instance of a set)
> 
> 
> 1. Which is better to use:
> 
> > class (Eq elem) => Set setTC elem where ...
> > instance (Eq elem) => Set [] elem where ...
> 
> or
> 
> > class (Eq elem) => Set set elem | set -> elem where ...
> > instance (Eq elem) => Set [elem] elem where ...
> 
> (I do need the functional dependency, because the set type, as being
> parametric, defines its element type?)

Right.  You could also use an associated type family, like this:

  class (Eq (Elem set)) => Set set where
    type Elem set :: *
    ...
    add :: Elem set -> set -> set
    ...

  instance (Eq elem) => Set [elem] where
    type Elem [elem] = elem
    ...

> The second one seemd easier to use at first when writing type
> signatures, but after a little fiddling, I got the other one working
> also.

The second one gives you a bit more flexibility, since you can have
Set instances for non-parametric types.  For example, with the second
you could have

  instance Set ByteString Word8 where
    ...

> 
> 2. Is there a way to make another instance for list as a set, when the
> element besides being instance of Eq, but also then of Ord (instead of
> just writing another class called OrdSet)?

There is, but it requires using newtype wrappers, like so:

  newtype OrdList a = OrdList [a]  -- lists with elements having an Ord constraint

  instance (Ord elem) => Set (OrdList elem) elem where
    ...

Of course, that does mean you'll have to wrap and unwrap OrdList
constructors a bit, but there are nice ways of dealing with that.

> 3. Lastly, I was thinking, that for elements from Enum types could use
> a bit-array for even faster set operations.
> 
> Should I make other types (like lists and trees) instances of the Set
> class, or, instead, make a set type, and have it have many
> constructors for many data-structures?

I should think the first option would be nicer.


-Brent