Hi all,
I tried to use type classes for unifying APIs of several similar data
structures and it didn't work well. (In my case I was working with graphs,
instead of sets or maps.)
First, you rarely want to be polymorphic over the set representation, because
you care about performance. You really want to use that Very.Special.Set.insert
because it has the right performance characteristics for your task at hand. I
found only *one* use-case for writing polymorphic functions operating on
something like IsSet: the testsuite. Of course, it is very nice to write a
single property test like
memberInsertProperty x set = (member x (insert x set) == True)
and then use it for testing all set data structures that implement `member` and
`insert`. Here you don't care about performance, only about correctness!
However, this approach leads to problems with type inference, confusing error
messages, and complexity. I found that it is much nicer to use explicit
dictionary passing and write something like this instead:
memberInsertProperty SetAPI{..} x set = (member x (insert x set) == True)
where `member` and `insert` come from the SetAPI record via RecordWildCards.
Finally, I'm not even sure how to create a type class covering Set and IntSet
with the following two methods:
singleton :: a -> Set a
map :: Ord b => (a -> b) -> Set a -> Set b
singleton :: Int -> IntSet
map :: (Int -> Int) -> IntSet -> IntSet
Could anyone please enlighten me about the right way to abstract over this
using type classes?
I tried a few approaches, for example:
class IsSet s where
type Elem s
singleton :: Elem s -> s
map :: Ord (Elem t) => (Elem s -> Elem t) -> s -> t
Looks nice, but I can't define the IntSet instance:
instance IsSet IntSet where
type Elem IntSet = Int
singleton = IntSet.singleton
map = IntSet.map
This fails with: Couldn't match type `t' with `IntSet' -- and indeed, how do I
tell the compiler that in the IntSet case s ~ t in the map signature? Shall I
add more associated types, or "associated constraints" using ConstraintKinds? I
tried and failed, at various stages, repeatedly.
...And then you discover that there is Set.cartesianProduct :: Set a -> Set b
-> Set (a, b), but no equivalent in IntSet and things get even more grim.
Cheers,
Andrey
_______________________________________________
ghc-devs mailing list
[email protected]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
