Fold-like functions for n-ary trees?

[Jon Fernquest]

While fiddling around with trees in Scheme my curiousity was
aroused...

Are there fold-like function for n-ary trees?
I've seen a function 'foldTree' in Haskell, but it was rather limited.

Are there higher order functions that do for tree recursion
what fold does for list recursion?
For instance to roll up numeric totals from the leaves of the tree
to the root or to pass inherited values down the tree.

I have a program that that displays the portion of the directory tree
over a certain threshhold disk space usage (e.g. 10 MB), but I'd like
to rewrite it with higher order functions.

Any paper or code references would be much appreciated.

Jon Fernquest
bayin...@hotmail.com

[Martin Gasbichler]

>>>>> "Jon" == Jon Fernquest <bayin...@hotmail.com> writes:

Jon> While fiddling around with trees in Scheme my curiousity was
Jon> aroused...

Jon> Are there fold-like function for n-ary trees?
Jon> I've seen a function 'foldTree' in Haskell, but it was rather limited.

Jon> Are there higher order functions that do for tree recursion
Jon> what fold does for list recursion?
Jon> For instance to roll up numeric totals from the leaves of the tree
Jon> to the root or to pass inherited values down the tree.

Jon> I have a program that that displays the portion of the directory tree
Jon> over a certain threshhold disk space usage (e.g. 10 MB), but I'd like
Jon> to rewrite it with higher order functions.

Jon> Any paper or code references would be much appreciated.

Folds are also called catamorphisms. The paper "A Fold for All
Seasons" by Tim Sheard and Leonidas Fegaras contains useful
information about this topic. You can download it from

http://citeseer.nj.nec.com/sheard93fold.html

--
Martin

[ol...@pobox.com]

In addition to Tim Sheard and Leonidas Fegaras' paper "A Fold for All
Seasons" you may want to check out:

Graham Hutton. "A tutorial on the universality and expressiveness of
fold" Journal of Functional Programming, 9(4):355-372, Cambridge
University Press, July 1999.
http://www.cs.nott.ac.uk/~gmh/fold.ps
A wonderfully written tutorial.

Jeremy Gibbons, Geraint Jones, "The Under-appreciated Unfold,"
Proc. ICFP'98, 1998, pp. 273-279.
http://citeseer.nj.nec.com/gibbons98underappreciated.html

The topic of folding a _stateful_ function over a tree has been
recently discussed in a thread

http://groups.google.com/groups?hl=en&safe=off&ic=1&th=132c402a835465d7
http://groups.google.com/groups?hl=en&safe=off&ic=1&th=b5f4378609901f5f

Note the regular tree fold isn't up to the task. If an action performed
at a node depends on the history of the traversal, you need to use a
higher-order fold, a continuation-passing fold, or foldt. All three
have been discussed in the above thread. The foldt is the backbone of
a SSAX XML parser. Indeed, an XML document is a n-ary tree laid out in a
particular way. XML parsing is then a depth-first traversal of that
tree. The function (a special form, actually) SSAX:make-elem-parser in
the middle of SSAX.scm literally implements the foldt (with a
slight generalization to handle processing instructions, PI, as well).

http://pobox.com/~oleg/ftp/Scheme/SSAX.scm

I'm trying to write a paper about this. I'm not sure though if I
manage to beat the deadline.

[Jon Fernquest]

Inspiring!
Thanks for all the information. I'm going to try to put it to use.
I also think there are mainstream applications for these tree
traversal folds:

I used to do a lot of work with corporate accounting systems
using Cobol/CICS+DB. One thing we did that clients liked was
give them the capability of designing their accounting/reporting
systems which are essentially just big forests of trees with
totals rolling up from the leaves (where journal entries are posted).
There are constraints that hold between nodes (debits = credits).
The reports that the accounting systems produce are essentially
slices through the tree, producing higher level summary trees.
Anyway it can get incredibly messy and that's often what highly
paid consultants from Price-Waterhouse are paid to clean up
(kind of like garbage men and about as exciting!)

The consulting firm I worked for had a "chart of accounts design tool"
that allowed accountants to build prototype accounting systems for
their company and then generate the actual proprietary system from
this prototype.

I just mention this, because this sort of chart of accounts design
tool might
(written in higher-order tree traversal functions, course) might be a
nice addition to BRL (Beautiful Report Language) and GNU Cash written
in the Guile dialect of scheme.

A few pages of concise, provably correct, optimizable Scheme instead
of reams of bug infested Cobol (usually accumulated over decades).

Jon Fernquest
bayin...@hotmail.com

[David Casperson]

In article <4c425cd3.01071...@posting.google.com>,

Jon Fernquest <bayin...@hotmail.com> wrote:
>While fiddling around with trees in Scheme my curiousity was
>aroused...
>
>Are there fold-like function for n-ary trees?
>I've seen a function 'foldTree' in Haskell, but it was rather limited.
>
>Are there higher order functions that do for tree recursion
>what fold does for list recursion?
>For instance to roll up numeric totals from the leaves of the tree
>to the root or to pass inherited values down the tree.
>
>I have a program that that displays the portion of the directory tree
>over a certain threshhold disk space usage (e.g. 10 MB), but I'd like
>to rewrite it with higher order functions.

I'm going to switch to SML notation because I understand it better. In
that notation, the crucial property of (right) fold is that for any list
L,
L = List.foldr nil (op ::) L

(read `(op ::)` as `cons`). In scheme and SML lists are entirely
constructable using nil and cons, and basicly what foldr allows you to
do is replace the constructors nil and cons with arbitrary things, e.g.,
List.foldr 0 (fn (a,b)=>b+1)
is the length function, etc.

So you want to do the same for a tree fold. It should take one
(function or constant) argument for each different kind of constructor
you have for your trees, and one final argument which is the tree to
which to apply the fold. The function or constant arguments should each
take the same number of arguments as the corresponding constructor.

Hope this helps.

David
--
Dr. David Casperson | cas...@unbc.ca
Department of Mathematics & Computer Science | (250) 960-6672
Faculty of Science |
College of Science and Management |