data declarations should provide fold functions

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

data declarations should provide fold functions

Tim Newsham
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
http://www.thenewsh.com/~newsham/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: data declarations should provide fold functions

wren ng thornton
Tim Newsham wrote:
> 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.

If you don't mind the hairy code, there's always this generic answer
from #haskell almost a year ago:

     http://hpaste.org/7682

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.

--
Live well,
~wren
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: data declarations should provide fold functions

Johan Jeuring
In reply to this post by Tim Newsham
> 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):

http://hackage.haskell.org/cgi-bin/hackage-scripts/package/multirec

A description of the library can be found in

http://www.cs.uu.nl/research/techreps/UU-CS-2008-019.html

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.

All the best,

Johan Jeuring

> Tim Newsham
> http://www.thenewsh.com/~newsham/
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe