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