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

Li-yao Xia lysxia at gmail.com
Fri Sep 7 15:33:38 UTC 2018


You can define classes to serve as "constraint combinators", that can be 
partially applied:

     {- Unary Constraint conjunction -}
     class (c a, d a) => (&) (c :: k -> Constraint) (d :: k -> 
Constraint) (a :: k)
     instance (c a, d a) => (&) c d a

     {- Unary empty constraint -}
     class Empty a
     instance Empty a

Now you can write

     type Con HashSet = Hashable & Eq

     type Con Foo = Empty

Another alternative is to "eta-expand" the synonym Con:

     class SetC s where
       type Con s a :: Constraint

     class ...
       type Con HashSet a = (Hashable a, Eq a)

One issue with that is that Con cannot be partially applied.

Li-yao


On 9/7/18 11:24 AM, Johannes Waldmann wrote:
> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
> 


More information about the Haskell-Cafe mailing list