Re: graphs and trees again
Am Dienstag, 13. Januar 2004 22:56 schrieb Ross Paterson:
On Tue, Jan 13, 2004 at 09:36:58PM +0100, Wolfgang Jeltsch wrote:
Am Dienstag, 13. Januar 2004 19:12 schrieb Ross Paterson:
* made the types abstract, but provided the equivalent constructor and destructor functions. I'm not sure that gains anything.
Well, I did this to be consistent with the Graph module where abstract types are crucial. Yes, it doesn't make much sense. But declaring Forest via newtype instead of type surely makes sense because this way you're able to define a meaningful Functor instance.
You get to write fmap instead of map . fmap, but you lose the ability to treat forests simply as lists.
With an seperate forest type, you are also able to use functions which work with arbitrary functors.
* added upwards and downwards accumulators (except that your "upwards" accumulator is actually a variant downwards accumulator, with quadratic performance).
What do you mean with "a variant"? Is foldl a variant foldr?
A downwards accumulation normally replaces each value with the foldl of the path (list) of items from the root to here (as yours does). An upwards accumulation normally replaces the values each item with the (tree) fold of that subtree:
foldTree :: (a -> [b] -> b) -> Tree a -> b foldTree n (Node a ts) = n a (map (foldTree n) ts)
upAccumTree :: (a -> [b] -> b) -> Tree a -> Tree b upAccumTree f = foldTree ft where ft a ts = Node (f a (map root ts)) ts root (Node a _) = a
It's a different generalization of scanr: yours replaces each item with a foldr on the list of ancestors.
BTW, do you have any uses for these things? (The unfolds are useful for search problems.)
I use flattenTree $ downAccuTree (flip (:)) [] $ spanningTree vertex graph to get paths from a graph vertex to every reachable vertex (actually, the reversed paths). Wolfgang
Sorry, this was meant to go to the library list. Am Mittwoch, 14. Januar 2004 10:55 schrieb Wolfgang Jeltsch:
Am Dienstag, 13. Januar 2004 22:56 schrieb Ross Paterson:
On Tue, Jan 13, 2004 at 09:36:58PM +0100, Wolfgang Jeltsch wrote:
Am Dienstag, 13. Januar 2004 19:12 schrieb Ross Paterson:
* made the types abstract, but provided the equivalent constructor and destructor functions. I'm not sure that gains anything.
Well, I did this to be consistent with the Graph module where abstract types are crucial. Yes, it doesn't make much sense. But declaring Forest via newtype instead of type surely makes sense because this way you're able to define a meaningful Functor instance.
You get to write fmap instead of map . fmap, but you lose the ability to treat forests simply as lists.
With an seperate forest type, you are also able to use functions which work with arbitrary functors.
* added upwards and downwards accumulators (except that your "upwards" accumulator is actually a variant downwards accumulator, with quadratic performance).
What do you mean with "a variant"? Is foldl a variant foldr?
A downwards accumulation normally replaces each value with the foldl of the path (list) of items from the root to here (as yours does). An upwards accumulation normally replaces the values each item with the (tree) fold of that subtree:
foldTree :: (a -> [b] -> b) -> Tree a -> b foldTree n (Node a ts) = n a (map (foldTree n) ts)
upAccumTree :: (a -> [b] -> b) -> Tree a -> Tree b upAccumTree f = foldTree ft where ft a ts = Node (f a (map root ts)) ts root (Node a _) = a
It's a different generalization of scanr: yours replaces each item with a foldr on the list of ancestors.
BTW, do you have any uses for these things? (The unfolds are useful for search problems.)
I use flattenTree $ downAccuTree (flip (:)) [] $ spanningTree vertex graph to get paths from a graph vertex to every reachable vertex (actually, the reversed paths).
Wolfgang
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- ACHTUNG! Es kann dieser Tage zu Ausfällen des Mailsystems meines Providers kommen. Sollten Sie mich unter meiner normalen Adresse (wolfgang@jeltsch.net) nicht erreichen können, kontaktieren Sie mich bitte unter meiner provisorischen Adresse wolfgang.jeltsch@onlinehome.de!
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
participants (2)
-
Jeremy Gibbons -
Wolfgang Jeltsch