[Haskell] Re: graphs and trees again

[Jeremy Gibbons]

I've been catching up on things I meant to reply to weeks ago.

> > BTW, do you have any uses for [upwards and downwards
> > accumulations on trees]?  
> 
> I use
>     flattenTree $ downAccuTree (flip (:)) [] $ spanningTree vertex graph
> to get paths from a graph vertex to every reachable vertex (actually, the 
> reversed paths).

My PhD thesis from many years ago [1] was about upwards and
downwards accumulations on particular kinds of trees,
including the "rose trees"

  data Tree a = Node a [Tree a]

you use. I'm afraid it isn't available online (though I do
have a few paper copies), but a summary [2] appeared in MPC
in 1992. Roughly speaking, an upwards accumulation passes
information up a tree, from the leaves towards the root,
labelling every node with some function of its descendents
(like a scanr on lists); a downwards accumulation passes
information down the tree, from the root towards the leaves,
labelling every node with some function of its ancestors
(like a scanl on lists).

Richard Bird, Oege de Moor and Paul Hoogendijk [3] showed
how to do "generic" upwards accumulations, ie for an
arbitrary kind of tree. I returned to the scene of the crime
several times [4,5] to try to do the same for downwards
accumulations, but the best solution was given by Alberto
Pardo [6] at WCGP in 2002.

Applications? My thesis argument was that many algorithms
took the form of an upwards accumulation followed by a
downwards accumulation, collecting then disseminating
information about the tree. My MPC paper shows Ladner and
Fischer's parallel prefix algorithm. My thesis also shows
Reingold and Tilford's tree-drawing algorithm, which I wrote
up as a later paper [7]. I confess, two examples is not
really "many"...

Jeremy

[1] Jeremy Gibbons. Algebras for Tree
Algorithms. D. Phil. thesis, Programming Research Group,
Oxford University, 1991. Available as Technical Monograph
PRG-94. 
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#algebras

[2] Jeremy Gibbons. Upwards and Downwards Accumulations on
Trees. In LNCS 669: Mathematics of Program Construction,
ed. R. S. Bird, C. C. Morgan and J. C. P. Woodcock,
Springer-Verlag, 1993, p. 122-138. Revised version appears
in Proceedings of the Massey Functional Programming
Workshop, ed. E.  Ireland and N. Perry, 1992.
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#accumulations

[3] Richard Bird, Oege de Moor and Paul Hoogendijk. Generic
functional programming with types and relations.  Journal of
Functional Programming, 6(1), 1996.
http://www.comlab.ox.ac.uk/oucl/work/oege.demoor/papers/gen.ps.gz

[4] Jeremy Gibbons. Polytypic Downwards Accumulations. In
LNCS 1422: Mathematics of Program Construction, ed Johan
Jeuring, Marstrand, Sweden, June 1998.
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#polyda

[5] Jeremy Gibbons. Generic Downwards Accumulations. Science
of Computer Programming 37(1-3) p37-65, 2000.
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#genda

[6] Alberto Pardo. Generic Accumulations. In Jeremy Gibbons
and Johan Jeuring (eds), Proceedings of the IFIP TC2 Working
Conference on Generic Programming, Kluwer Academic
Publishers, 2003.
http://www.fing.edu.uy/~pardo/papers/wcgp02.ps.gz
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#wcgp

[7] Jeremy Gibbons. Deriving Tidy Drawings of Trees.
Journal of Functional Programming, 6(3) p535-562, June 1996.
http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/index.html#deriving

-- 
Jeremy.Gibbons at comlab.ox.ac.uk
  Oxford University Computing Laboratory,    TEL: +44 1865 283508
  Wolfson Building, Parks Road,              FAX: +44 1865 273839
  Oxford OX1 3QD, UK.  
  URL: http://www.comlab.ox.ac.uk/oucl/people/jeremy.gibbons.html