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#... [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#... [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#... [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#... [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#... [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#... -- Jeremy.Gibbons@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