[Haskell] Re: graphs and trees again
Jeremy Gibbons
Jeremy.Gibbons at comlab.ox.ac.uk
Mon Feb 23 10:23:33 EST 2004
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
More information about the Haskell
mailing list