Restricted type classes

Ivan Lazar Miljenovic

3 Sep 2010 3 Sep '10

12:16 a.m.

When I released the first version of container-classes (which I hacked on during AusHac), some people said I should split out the various folding, etc. into duplicates of the current Foldable class, etc. rather than having large monolithic classes. I've been working on this (see my more recent email with the subject along the lines of "fighting the type system"), and I think I've worked out how to do this: * Have one version of the class (when this makes sense) for values of kind * * Have another version that's closer to the original class for kind * -> * but allowing restrictions (e.g. allowing Set to be an instance of Functor). This is based upon Ganesh Sittampalam's rmonad package (http://hackage.haskell.org/package/rmonad). Rather than my original goal of forcing all kind * -> * values to be instances of the kind * classes, my new approach is to write instances that automatically make all instances of a * -> * class to also be an instance of the kind * class, and to use a newtype wrapper with a phantom type value to allow lifting/promotion of a kind * value to a kind * -> * value (e.g. "foo :: (Word8 -> Word8) -> ByteString -> ByteString; foo f = unpromote . fmap f . Promote" is a valid usage, rather than using the kind * function of rigidMap). My goal with this is that if I have duplicated a class Foo to allow restricted values, then it should be a drop-in replacement for the original in terms of _usage_ (i.e. the class and method/function names are the same, but the type signatures are not). However, I would appreciate the communities advice on a few matters: 1) How should I name the kind * versions? For example, the kind * version of Functor is currently called Mappable with a class method of rigidMap. What should I call the kind * version of Foldable and its corresponding methods? Is there a valid system I can use for these? 2) How far should I go? Should I restrict myself to the "data-oriented" classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should: 2a) Which namespace to use? Should Monad go in Data.Restricted.Monad to keep it in the same namespace as the other classes, or should I make it closer to base with Control.Restricted.Monad? 2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default <*> (since (a -> b) isnt' an instance of Ord). 2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base? 3) Am I wasting my time with this? -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

Show replies by date

Tobias Brandt

3 Sep 3 Sep

9:19 a.m.

On 3 September 2010 06:16, Ivan Lazar Miljenovic wrote:

...

2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)?

I also opt for putting the constraints in.

...

3) Am I wasting my time with this?

Definitely not. A standard container interface is something a lot of people want.

wren ng thornton

4 Sep 4 Sep

3:40 a.m.

On 9/3/10 12:16 AM, Ivan Lazar Miljenovic wrote:

...

1) How should I name the kind * versions? For example, the kind * version of Functor is currently called Mappable with a class method of rigidMap. What should I call the kind * version of Foldable and its corresponding methods? Is there a valid system I can use for these?

I think it'd be good to be consistent, whatever you do. For (*->*->*) monads I've seen them called GMonads (for "generalized") and indexed monads. For the (*->*) monads, I've seen RMonads and parameterized monads. Here are some links for those who may be interested; they have more links to independent invention by Oleg Kiselyov and also by Bob Atkey, as well as a Coq implementation and a mention of Agda. (For my part, I've since moved on to playing with monads between different categories, which isn't really germane here.) http://winterkoninkje.dreamwidth.org/65416.html http://winterkoninkje.dreamwidth.org/65585.html So, in the interest of generality, perhaps you should just pick a letter or a short prefix and use that for each of the classes. In my blog posts I called them 0-monads, 1-monads, and 2-monads; following Ganesh Sittampalam and Matthieu Sozeau, they'd be monads, r-monads, and g-monads.

...

2) How far should I go? Should I restrict myself to the "data-oriented" classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should:

I'd say you should do as much as seems reasonable. I tend to take things as far as I can, but that'd end up doing a lot of the same work as category-extras. For a general collections library, I think it'd make sense to try to keep things simpler than that if possible. The simpler it is, the better the uptake will be, so long as it's still complex enough to capture what it needs to. I'd say you should include: Functor, Foldable, Traversable, Pointed, Applicative, Monad, and Monoid (both additive and multiplicative in separate classes, as in the monoids package). Those eight make for a really comprehensive toolkit that does most of the things people frequently need. Of course, not every collection will have instances for all of them. (N.B., following the naming convention in those blog posts, 2-monoids are exactly the same as categories.)

...

2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default<*> (since (a -> b) isnt' an instance of Ord).

That depends. In general, it's better to have smaller classes because it reduces the burden on programmers writing instances and it allows for smaller dictionaries at runtime. In general, I'd say that functions should be included into the class when they often permit specialized definitions which are more efficient than the generic one. And of course, they should be included when they serve as the basis of the class (e.g., both (==) and (/=) should be included in Eq since they both serve as a basis for equality, with no one being obviously easier to implement than the other). If there's little chance of a performance gain, then why would you want it in the class at all? For example, many types can implement fmap/(<$>) more efficiently than by using the liftM/liftA implementations or the default implementation from Foldable. (Of course, fmap is also a basis for the class.) For applicatives, the (<*) and (*>) operators should be included in the class too. While they seem trivial, some parser combinator libraries can get major performance improvements by using non-generic definitions. There was a discussion about this a while back, I forget if it was here or on the libraries list. And I forget if (<**>) also had efficient implementations... For another example of the principle, while compare is a sufficient basis for defining Ord, we include (<), (<=), (>), (>=) because they can often be implemented more efficiently than by using compare.

...

2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base?

If you're defining a new hierarchy, I'd say you should do it correctly, i.e. class Functor where fmap class Functor => Pointed where unit -- or point class Pointed => Applicative where (<*>) ; (<*) ; (*>) class Applicative => Monad where (>>=) ; join There's no benefit to preserving the ill designs of the past.

...

3) Am I wasting my time with this?

Not at all. Many people want a good containers API, and many people want a cleaned up version of the categorical classes which isn't quite as involved as category-extras. Go for it! -- Live well, ~wren

Ivan Lazar Miljenovic

3:50 a.m.

On 4 September 2010 17:40, wren ng thornton wrote:

...

On 9/3/10 12:16 AM, Ivan Lazar Miljenovic wrote:

...
1) How should I name the kind * versions? For example, the kind * version of Functor is currently called Mappable with a class method of rigidMap. What should I call the kind * version of Foldable and its corresponding methods? Is there a valid system I can use for these?

I think it'd be good to be consistent, whatever you do. For (*->*->*) monads I've seen them called GMonads (for "generalized") and indexed monads. For the (*->*) monads, I've seen RMonads and parameterized monads. Here are some links for those who may be interested; they have more links to independent invention by Oleg Kiselyov and also by Bob Atkey, as well as a Coq implementation and a mention of Agda. (For my part, I've since moved on to playing with monads between different categories, which isn't really germane here.)

http://winterkoninkje.dreamwidth.org/65416.html http://winterkoninkje.dreamwidth.org/65585.html

So, in the interest of generality, perhaps you should just pick a letter or a short prefix and use that for each of the classes. In my blog posts I called them 0-monads, 1-monads, and 2-monads; following Ganesh Sittampalam and Matthieu Sozeau, they'd be monads, r-monads, and g-monads.

I think I'd prefer to put the prefix on the kind * versions (though does a kind * version of something like Monad even make sense?).

...

...
2) How far should I go? Should I restrict myself to the "data-oriented" classes such as Functor, Traversable, etc. or should I try to make restricted versions of Applicative and Monad? Assuming I should:

I'd say you should do as much as seems reasonable. I tend to take things as far as I can, but that'd end up doing a lot of the same work as category-extras. For a general collections library, I think it'd make sense to try to keep things simpler than that if possible. The simpler it is, the better the uptake will be, so long as it's still complex enough to capture what it needs to.

I'd say you should include: Functor, Foldable, Traversable, Pointed, Applicative, Monad, and Monoid (both additive and multiplicative in separate classes, as in the monoids package). Those eight make for a really comprehensive toolkit that does most of the things people frequently need. Of course, not every collection will have instances for all of them.

Monoid was probably just going to be re-exported from base, since it's already for kind * (and as such works with all types, and doens't need any parametricity).

...

...
2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default<*> (since (a -> b) isnt' an instance of Ord).

That depends. In general, it's better to have smaller classes because it reduces the burden on programmers writing instances and it allows for smaller dictionaries at runtime. In general, I'd say that functions should be included into the class when they often permit specialized definitions which are more efficient than the generic one. And of course, they should be included when they serve as the basis of the class (e.g., both (==) and (/=) should be included in Eq since they both serve as a basis for equality, with no one being obviously easier to implement than the other). If there's little chance of a performance gain, then why would you want it in the class at all?

Well, the point was that liftA/liftA2 might make more sense as being the methods to be defined for some types rather than <*>, but you could define them in terms of each other.

...

...
2c) Should I keep the classes as-is, or should I explicitly put in the constraints mentioned in the Typeclassopedia (e.g. make Applicative an explicit superclass of Monad, and define return = pure for compatability reasons)? If so, should I bring over Pointed, etc. from category-extras to round out the set or just stick with classes that are already in base?

If you're defining a new hierarchy, I'd say you should do it correctly, i.e.

class Functor where fmap class Functor => Pointed where unit -- or point class Pointed => Applicative where (<*>) ; (<*) ; (*>) class Applicative => Monad where (>>=) ; join

There's no benefit to preserving the ill designs of the past.

Yes, that was my point.

...

...
3) Am I wasting my time with this?

Not at all. Many people want a good containers API, and many people want a cleaned up version of the categorical classes which isn't quite as involved as category-extras. Go for it!

*sigh* I was almost wishing people would say I _was_ wasting my time with this... ;-) -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

wren ng thornton

4:27 a.m.

On 9/4/10 3:50 AM, Ivan Lazar Miljenovic wrote:

...

On 4 September 2010 17:40, wren ng thornton wrote:

...
So, in the interest of generality, perhaps you should just pick a letter or a short prefix and use that for each of the classes. In my blog posts I called them 0-monads, 1-monads, and 2-monads; following Ganesh Sittampalam and Matthieu Sozeau, they'd be monads, r-monads, and g-monads.

I think I'd prefer to put the prefix on the kind * versions (though does a kind * version of something like Monad even make sense?).

Oh sure. I was just meaning that you should do something systematic like have XFoo and YFoo, instead of having Foo and Bar. That way people can just remember ({X,Y},{Foo,Fob,Fez}) instead of having to remember {(Foo,Bar), (Fob,Baz), (Fez,Quux)}. I'm a fan of keeping the undecorated names for the current versions, and using a prefix for the * versions.

...

...
I'd say you should include: Functor, Foldable, Traversable, Pointed, Applicative, Monad, and Monoid (both additive and multiplicative in separate classes, as in the monoids package). Those eight make for a really comprehensive toolkit that does most of the things people frequently need. Of course, not every collection will have instances for all of them.

Monoid was probably just going to be re-exported from base, since it's already for kind * (and as such works with all types, and doens't need any parametricity).

I was just talking general API, not necessarily what you need to write. Reusing the standard classes is fine.

...

Well, the point was that liftA/liftA2 might make more sense as being the methods to be defined for some types rather than<*>, but you could define them in terms of each other.

Well, liftA and liftM are just generic implementations of fmap using pure/(<*>) and return/(>>=). If you can define fmap directly, then you should do so. If you can't, you're always free to use the implementations that liftA and liftM use. The liftA function is defined explicitly for allowing you can say """instance Functor F where fmap = liftA""". There's no reason for liftA to belong to Applicative, because it has Functor as a superclass and therefore fmap exists. Since fmap can be more efficient than liftA, it is better to use fmap when writing code. Note that (<$>) is defined as fmap, and liftA2, liftA3, etc are defined in terms of (<$>) i.e. fmap. For liftM things are a bit hazier because Monad fails to mention Functor as an explicit superclass, but it really ought to. Assuming it did, then there's no reason for liftM to belong to Monad, because we're assured that fmap exists. Though, again, liftM should be defined as a non-class function in order to serve as a default implementation of fmap for those who need it. This is the same reason why Data.Traversable defines fmapDefault and foldMapDefault: not so that they can be used as functions, but so that they can be used for giving class instances. Perhaps we should be calling them fmapApplictiveDefault, fmapMonadDefault, and fmapTraversableDefault instead... I suppose you could use liftA2 as the basis of Applicative instead of (<*>), but that seems a bit perverse to me. The (<*>) operation captures exactly what we want to say--- namely the K axiom for modal logics; which is equivalent to saying the applicative category has exponentials; which is also the name for the whitespace of function application;... . Whereas liftA2 seems like a far more round-about way of getting there. There may be efficiency reasons for arguing that liftA2 should be included in _addition_ to (<*>), but I'm not aware of them. -- Live well, ~wren

Ivan Lazar Miljenovic

4:45 a.m.

On 4 September 2010 18:27, wren ng thornton wrote:

...

On 9/4/10 3:50 AM, Ivan Lazar Miljenovic wrote:

...
On 4 September 2010 17:40, wren ng thornton wrote:

...
So, in the interest of generality, perhaps you should just pick a letter or a short prefix and use that for each of the classes. In my blog posts I called them 0-monads, 1-monads, and 2-monads; following Ganesh Sittampalam and Matthieu Sozeau, they'd be monads, r-monads, and g-monads.

I think I'd prefer to put the prefix on the kind * versions (though does a kind * version of something like Monad even make sense?).

Oh sure. I was just meaning that you should do something systematic like have XFoo and YFoo, instead of having Foo and Bar. That way people can just remember ({X,Y},{Foo,Fob,Fez}) instead of having to remember {(Foo,Bar), (Fob,Baz), (Fez,Quux)}.

I'm a fan of keeping the undecorated names for the current versions, and using a prefix for the * versions.

Right, so what prefix? ;-)

...

Well, liftA and liftM are just generic implementations of fmap using pure/(<*>) and return/(>>=). If you can define fmap directly, then you should do so. If you can't, you're always free to use the implementations that liftA and liftM use. The liftA function is defined explicitly for allowing you can say """instance Functor F where fmap = liftA""". There's no reason for liftA to belong to Applicative, because it has Functor as a superclass and therefore fmap exists. Since fmap can be more efficient than liftA, it is better to use fmap when writing code. Note that (<$>) is defined as fmap, and liftA2, liftA3, etc are defined in terms of (<$>) i.e. fmap.

Gah, you're right. I didn't think that liftA = fmap.

...

For liftM things are a bit hazier because Monad fails to mention Functor as an explicit superclass, but it really ought to. Assuming it did, then there's no reason for liftM to belong to Monad, because we're assured that fmap exists. Though, again, liftM should be defined as a non-class function in order to serve as a default implementation of fmap for those who need it.

Hmmm, I was thinking of just having "liftM = fmap", but yeah using the monadic defaults makes sense to avoid having to define fmap explicitly.

...

This is the same reason why Data.Traversable defines fmapDefault and foldMapDefault: not so that they can be used as functions, but so that they can be used for giving class instances. Perhaps we should be calling them fmapApplictiveDefault, fmapMonadDefault, and fmapTraversableDefault instead...

I suppose you could use liftA2 as the basis of Applicative instead of (<*>), but that seems a bit perverse to me. The (<*>) operation captures exactly what we want to say--- namely the K axiom for modal logics; which is equivalent to saying the applicative category has exponentials; which is also the name for the whitespace of function application;... . Whereas liftA2 seems like a far more round-about way of getting there. There may be efficiency reasons for arguing that liftA2 should be included in _addition_ to (<*>), but I'm not aware of them.

Well, I _can_ define <*> for Sets (and have done so), but such an instance doesn't make any sense because functions don't have Ord instances. As such, the default liftA2, etc. definitions don't work with Sets because of this. -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

Stephen Tetley

4:54 a.m.

On 4 September 2010 08:50, Ivan Lazar Miljenovic wrote:

...

...
...
3) Am I wasting my time with this?

Not at all. Many people want a good containers API, and many people want a cleaned up version of the categorical classes which isn't quite as involved as category-extras. Go for it!

*sigh* I was almost wishing people would say I _was_ wasting my time with this... ;-)

Hi Ivan Okay, I'll bite... Its good someone is looking into arity versions of Monad, Applicative etc. I think previously pointed you to Conor McBride's message on the subject: http://www.haskell.org/pipermail/haskell-cafe/2008-June/044011.html But, I don't know that work on this will lead to a better API for collection classes... Supposing classes is the way to go, I think there's still a lot of design work to be done on what the classes should be rather than how they are implemented. The current design space (ListLike and your Data.Containers) looks like a factoring of the operations from Data.List and Data.Sequence, personally I have serious doubts that this will lead to a nice API. If I was looking at it myself, I'd start from Chris Okasaki and Ralf Hinze's observations that data structures have analogies to numerical representations. So, I would try to build classes upwards from that (monoid is obviously already in place), rather than design by factoring what List already has. As an example, I think someone has pointed out on the Cafe that C++ has a container library following the analogy to numerical representations. As an aside I thought someone added an implementation of Simon Peyton Jones's "Bulk Types with Class" to Hackage recently? If they did they didn't give it a findable description. Best wishes Stephen

Ivan Lazar Miljenovic

4:57 a.m.

On 4 September 2010 18:54, Stephen Tetley wrote:

...

Supposing classes is the way to go, I think there's still a lot of design work to be done on what the classes should be rather than how they are implemented. The current design space (ListLike and your Data.Containers) looks like a factoring of the operations from Data.List and Data.Sequence, personally I have serious doubts that this will lead to a nice API. If I was looking at it myself, I'd start from Chris Okasaki and Ralf Hinze's observations that data structures have analogies to numerical representations. So, I would try to build classes upwards from that (monoid is obviously already in place), rather than design by factoring what List already has. As an example, I think someone has pointed out on the Cafe that C++ has a container library following the analogy to numerical representations.

Where exactly can I find these observations on the analogies between data structures and numerical representations? -- Ivan Lazar Miljenovic Ivan.Miljenovic@gmail.com IvanMiljenovic.wordpress.com

Stephen Tetley

5:08 a.m.

On 4 September 2010 09:57, Ivan Lazar Miljenovic wrote:

...

Where exactly can I find these observations on the analogies between data structures and numerical representations?

Chris Okasaki - Chapter 9 of Purely Functional Data Structures. Ralf Hinze's slides Number Systems and Data Structures, March 2005 - http://www.cs.nott.ac.uk/~gmh/bctcs-slides/hinze.pdf On second thoughts, I don't think C++ has a collection classes library designed in this way. The message on the Cafe I had in mind was this one, but it is talking about something else: http://www.haskell.org/pipermail/haskell-cafe/2010-April/076157.html

Ben Millwood

1:14 p.m.

I have only one thing to add to this discussion: On Fri, Sep 3, 2010 at 5:16 AM, Ivan Lazar Miljenovic wrote:

...

2b) Is it OK to promote functions that use a class to being class methods? When I was discussing this in #haskell several people mentioned that defining something like liftA2 for the Set instance of (restricted) Applicative would make more sense than the default <*> (since (a -> b) isnt' an instance of Ord).

One problem with defining both <*> and liftA2 in the class in terms of each other is that omitting them from instances is no longer a compile-time error, nor is it even an obvious runtime error - it's frequently an infinite loop, which is unpleasant. Though I understand that it's nice to be able to choose the methods you want to define, I think static error detection is nice too, so I tend to avoid providing extra class methods with defaults unless the alternative is much worse. On that note, why *do* we have missing instance methods filled in with bottoms, so that even without defaults, it's a warning rather than an error? It seems like quite an un-Haskelly thing to do. I know there may be some cases where you do not need to define a particular method, but imo you should be required to explicitly opt out of it if that's the case.

5375

Age (days ago)

5376

Last active (days ago)

List overview

Download

9 comments

5 participants

participants (5)

Ben Millwood
Ivan Lazar Miljenovic
Stephen Tetley
Tobias Brandt
wren ng thornton