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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
