[Haskell-cafe] Restricted type classes
wren ng thornton
wren at freegeek.org
Sat Sep 4 03:40:49 EDT 2010
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.)
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
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
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!
More information about the Haskell-Cafe