[Haskell-cafe] Restricted type classes

[wren ng thornton]

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