[Haskell-cafe] common class for Set (and Map, resp.) implementations with different constraints on the keys

Johannes Waldmann johannes.waldmann at htwk-leipzig.de
Fri Sep 7 15:24:54 UTC 2018


Dear Cafe,


we have Data.Set, Data.IntSet, Data.HashSet,
and they all have similar API, where the only difference
is the constraint on the elements. (Same thing for maps.)

Can we unify this as follows:

{-# language ConstraintKinds, TypeFamilies #-}
class SetC s where
  type Con s :: * -> Constraint
  singleton :: (Con s a) => a -> s a
  foldMap :: (Con s a, Monoid m) => (a -> m) -> s a -> m
  ...

Then for Data.Set, we write

instance SetC S.Set where  type Con S.Set = Ord ; ...

It seems to work, and it allows me to write polymorphic code,
and switch implementations from the top.
Full source:
https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/tree/master/src/Data/Set
Example use case (switch implementation):
https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/blob/master/src/Matchbox/Tiling/Working.hs#L48



Still, there are some clumsy corners in this code, perhaps you can help:


* for  instance SetC HashSet, there are two constraints. I want to write

type Con HashSet = \ e -> (Hashable e, Eq, e)

but this does not work (there is no "type lambda"?)


* for maps, I want to write

class (forall k . Foldable m k) => MapC m

but this seems impossible now (This is would work
with  -XQuantifiedConstraints ?)


* in some other code using the same idea (the class exports the
constraint), I had an instance where the constraint was empty.

Again, I cannot write  type Con Foo = \ s -> ()


- J.W.


More information about the Haskell-Cafe mailing list