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
If you care about performance then explicit dictionary passing is
going to be worse than using type classes.
At that point though, what do you gain from using the module system as
you are just going to pass the same dictionaries into every function
and never change them.
So, for me, keep using modules but make the APIs of each module more
consistent if you think it's worthwhile.
On Thu, May 30, 2019 at 6:11 PM Andrey Mokhov
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 ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Hi Andrey,
FWIW, mono-traversable (http://hackage.haskell.org/package/mono-traversable)
suggests decoupling IsSet and Funtor-like.
In a nutshell, they define the IsSet class (in Data.Containers) with
typical set operations like member and singleton, union and intersection.
And then they tackle a (seemingly) independent problem of mapping
monomorphic containers (like IntSet, ByteString, etc.) with a separate
class MonoFunctor (in Data.MonoTraversable):
class MonoFunctor mono where
omap :: (Element mono -> Element mono) -> mono -> mono
And gazillion of instances for both polymorphic containers with a fixed
type parameter and monomorphic ones.
--
Best wishes,
Artem
On Thu, 30 May 2019 at 20:11, Andrey Mokhov
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 ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
participants (3)
-
Andrey Mokhov -
Artem Pelenitsyn -
Matthew Pickering