I've had to use some fold functions recently and I've come to
the conclusion that Haskell should automatically generate
fold functions for data definitions. To clarify what I mean,
for the data definition:
data MyData = This Int Char | That String Int Int
there should be a matching function definition:
foldMyData f g (This a b) = f a b
foldMyData f g (That a b c) = g a b c
This definition is as natural as the constructors "This" and
"That". Consider the tuple definition and its fold:
data (,) a b = (a, b)
foldTuple f (x, y) = f x y
and the definition of Either and its fold:
data Either a b = Left a | Right b
foldEither f g (Left x) = f a
foldEither f g (Right x) = g x
In logic these constructors define the introduction rules
((,), Left and Right) and the folds define the elimination
rules (exactly for Either, indirectly for tuples) for conjunction
Further, while pattern-matching is very convenient for accessing
the constituents of the data type, patterns are not first-class
objects in Haskell. Fold functions, on the othe hand, are.
They can be passed around and used in higher-order functions
to extract constituents in a points-free manner.
I know the short-term answer is "use TH" to derive folds if
I want them, but I think such an important concept should probably
be part of the language.
You'd need to hook it up with a preprocessor script since it's a
String->String function. It should be pretty easy to rewrite that into
TH code in order to clean it up.
I agree, it'd be nice to have it as a standard deriving clause, but
since every fold has a different type it's challenging to make it fit
into the language rather than being a wart. Some of the stuff in
Data.Generics, Data.Typable, etc might could help. If you come up with
anything you like, it shouldn't be too hard to (convince someone to)
convert the logic into a language extension.
> I know the short-term answer is "use TH" to derive folds if
> I want them, but I think such an important concept should probably
> be part of the language.
The fold function is an example of a generic program, which can
be defined using generic programming libraries. Since the fold
has to know about the recursive structure of a datatype, not
all (actually, very few) generic programming libraries can be
used to define a fold.
An example of a recent library that can define folds is multirec
(developed by our own group, blatant self promotion):
Older generic programming approaches such as PolyP could define
the fold too, be it only for so-called regular (non mutually
recursive) datatypes. The multirec library defines folds for
mutually recursive datatypes.
The released version of multirec doesn't include the TH files
for generating the boilerplate code (for example, embedding-projection
pairs for datatypes) necessary for using the library. However,
the head has TH support for this.