Container type classes

Artem Pelenitsyn a.pelenitsyn at
Thu May 30 19:56:02 UTC 2019

Hi Andrey,

FWIW, 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,

On Thu, 30 May 2019 at 20:11, Andrey Mokhov <andrey.mokhov at>

> 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 =
> 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 at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the ghc-devs mailing list