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 <andrey.mok...@newcastle.ac.uk> wrote: > 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 >
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs