common class for Set (and Map, resp.) implementations with different constraints on the keys
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/Da... Example use case (switch implementation): https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/blob/master/src/Ma... 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.
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/Da... Example use case (switch implementation): https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/blob/master/src/Ma...
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.
In my opinion, such a class should usually have more than one parameter. In the case of Set, I think it makes more sense to use a value type than a constraint type. class e ~ Elem s => SetC e s where type Elem s :: Type type Elem (_ a) = a singleton :: e -> s elem :: e -> s -> Bool union :: s -> s -> s ... instance Ord a => SetC a (S.Set a) where singleton = S.singleton ... instance a ~ Int => SetC a IntSet where type Elem IntSet = Int ... For maps, you can do something similar: class k ~ Key m => MapC k m where type Key m :: Type type Key (_ k) = k lookup :: k -> m a -> Maybe a ... instance Ord k => MapC k (M.Map k) where lookup = M.lookup .... instance k ~ Int => MapC k IM.IntMap where type Key IntMap = Int lookup = IM.lookup If you like, you can add some constraints, like Traversable m. If you want to use MFoldable for sets, you can use its Element type family instead of Elem. On Fri, Sep 7, 2018, 11:25 AM Johannes Waldmann < johannes.waldmann@htwk-leipzig.de> 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/Da... Example use case (switch implementation):
https://gitlab.imn.htwk-leipzig.de/waldmann/pure-matchbox/blob/master/src/Ma...
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.
On 09/07/2018 05:51 PM, David Feuer wrote:
class e ~ Elem s => SetC e s where
OK. At the use site, under both proposals, there'll be a two argument constraint. In my version, the second argument was curried away. One way or the other - why don't we? What could be the downsides here? I guess since it's meant to sit atop (some) modules from various packages (containers, unordered-containers, enummapset) it's best to release it as a separate package, containing the classes, and orphan instances. - J.
The instances won't be orphans if they're in the same module as the class
definition.
On Fri, Sep 7, 2018, 2:12 PM waldmann
On 09/07/2018 05:51 PM, David Feuer wrote:
class e ~ Elem s => SetC e s where
OK. At the use site, under both proposals, there'll be a two argument constraint. In my version, the second argument was curried away.
One way or the other - why don't we? What could be the downsides here?
I guess since it's meant to sit atop (some) modules from various packages (containers, unordered-containers, enummapset) it's best to release it as a separate package, containing the classes, and orphan instances.
- J.
participants (4)
-
David Feuer -
Johannes Waldmann -
Li-yao Xia -
waldmann