what's a proper way to make a Set typeclass? and why is it not done already?
I started like this: {-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-} import qualified Data.List as L class (Eq e) => Set s e where empty :: s e fromList :: [e] -> s e ... ..and started to implement it on a list: instance (Eq e) => Set [] e where empty = [] fromList xs = L.nub xs But I can't understand, why there has to be a (Eq a) context to the Set instance of a list, when the class definition seems to already say it? It won't compile without it.. Secondly, why do I need FlexibleInstances -- it gives me an eror which I don't understand ("all instance types must be of the form T a1 ... an" and so on, and recommends to add the flexible instances.) Also I couldn't find other elaborate Set typeclasses -- there seems to be only the "Set a" type. Why is that(?), because you could use other datastructures, better and worse in various ways, than the balanced binary tree.. Markus
On Tue, Jul 06, 2010 at 01:35:41AM +0300, Markus Läll wrote:
I started like this:
{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances #-}
import qualified Data.List as L
class (Eq e) => Set s e where empty :: s e fromList :: [e] -> s e ...
..and started to implement it on a list:
instance (Eq e) => Set [] e where empty = [] fromList xs = L.nub xs
But I can't understand, why there has to be a (Eq a) context to the Set instance of a list, when the class definition seems to already say it? It won't compile without it..
The class definition says that an Eq constraint is *required*, it does not provide it. 'instance Set [] e' would promise that the instance will work for *any* type e (even ones without an Eq instance), but the class declaration requires that e must have an Eq instance. Hence the error.
Secondly, why do I need FlexibleInstances -- it gives me an eror which I don't understand ("all instance types must be of the form T a1 ... an" and so on, and recommends to add the flexible instances.)
The Haskell98 standard is quite convervative when it comes to the sorts of instances you are allowed to declare. I think in this case it is complaining about the fact that e is a variable and not a particular type constructor; I agree that particular error is rather hard to decipher. In any case, enabling FlexibleInstances is quite common and harmless.
Also I couldn't find other elaborate Set typeclasses -- there seems to be only the "Set a" type. Why is that(?), because you could use other datastructures, better and worse in various ways, than the balanced binary tree..
I guess for no better reason than because no one has ever wanted it. Actually, another reason may be because it is a rather large design space and no one has been able to agree on what such a type class might look like. But don't let either of those stop you. -Brent
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?) 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. 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)? This is to take advandage of the Ord class -- like having a sorted list of elements. Then, for inserting or checking for membership, I could look only as far as I need in the list. 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? Markus
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
participants (2)
-
Brent Yorgey -
Markus Läll