[Haskell-cafe] Factoring into type classes

[wren ng thornton]

Patai Gergely wrote:
> Hi everyone,
> 
> I have a general program design question, but I can't really think of
> good examples so it will be a bit vague. There was a discussion on Show
> not long ago which brought up the problem that there are several ways to
> "show" a data structure, and it depends on the context (or should I call
> it a use case?) which of these we actually want, e.g. human readable
> form, debug information, serialisation for later reading and so on, and
> one of the solutions was to propose a family of show functions that
> carry the intended use in their name.
> 
> However, there are other type classes that are too general to assign
> such concrete uses to. For instance, if a data structure can have more
> than one meaningful (and useful) Functor or Monoid instance, what should
> one do? Should one refrain from instantiating these classes altogether
> and just use the names of operations directly? If one still decides to
> pick a certain set of operations as an instance, what are the factors
> that should guide this decision? What about designing libraries, how
> much should one prefer standard classes for their interfaces?
> 
> It seems to me that there is practically no literature on design issues
> like these, and it would be nice to hear some opinions from experienced
> Haskellers.

As others have mentioned or alluded to, I think that if you're designing 
general functions where you anticipate running into these issues then 
you should avoid the instance-selection mechanism of type classes. You 
can still use the dictionary-passing idea of type classes, but you must 
pass the dictionaries explicitly. This approach is used by the 
generalized functions in Data.List[1], as well as many other places.

Dictionary passing is, in essence, what higher-order programming is all 
about. Most often we deal with degenerate cases of dictionary passing 
where we only pass a single function (e.g. Data.List), but that's not 
the only way.

Another place where dictionary passing is used extensively is in the 
category-extras package[2] where the dictionaries are called 
"F-(co)algebras". An F-algebra is still degenerate as dictionaries go 
(it's a single function :: f a -> a), but it can be insightful to 
consider it as a dictionary proper, for example with "folding" functions 
like foldr. Normally we look at the type of foldr and think of it as 
taking two arguments, one for each constructor of lists. Instead, we can 
use a case expression to pack those two arguments together into a single 
F-algebra, selecting which argument to return based on the constructor. 
And this can be generalized to the folding functions for any datatype.

Thus, it's helpful to think of dictionaries as algebras (in generic and 
universal terms). A monoid is just one example of an object in universal 
algebra, it is an algebra defined by the underlying type, the operator, 
and the identity. Any type class is also an example of an algebra (e.g. 
Num defines an algebra with addition, multiplication, etc; Show is an 
algebra for showing). We can package any algebra up into a record and 
then pass that record around to the generic functions which need to use 
an instance of the algebra. The same idea can be used for passing around 
"laws" and "proofs" about data types (e.g. any function of type F(G a) 
-> G(F a) is a law that says we can distribute F over G).

The only difference between using type classes and manually passing 
these records around is that Haskell has linguistic and runtime support 
for plucking the records out of the aether based on types. Since the 
compiler knows about type classes it can do smarter things for them than 
just passing dictionaries, so they should be used whenever reasonable. 
Type classes are wonderful, but they're not a silver bullet. Even when 
they're not reasonable, having first-class functions means we're not 
limited by their restrictions.


[1] http://cvs.haskell.org/Hugs/pages/libraries/base/Data-List.html#22
[2] 
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/category-extras

-- 
Live well,
~wren