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