[Haskell-cafe] data declarations should provide fold functions

Tim Newsham newsham at lava.net
Wed Jan 7 23:22:36 EST 2009

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
and disjunction.

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.

Tim Newsham

More information about the Haskell-Cafe mailing list