Re: graphs and trees again
[moving to libraries] On Tue, Jan 13, 2004 at 05:46:29PM +0100, Wolfgang Jeltsch wrote:
for my studies I recently needed graph and tree handling code. Because nothing I found seemed to satisfy my needs, I finally started writing my own graph and tree module. I was especially disappointed with Data.Graph and Data.Tree. The reasons are: * The Implementation of the types is not hidden so that code using Data.Graph and Data.Tree can get very implementation-dependent. * Vertices are ints which is too low level in my opintion. I think it would be better to allow different types for vertices because this seems to closer reflect what applications demand. * I'd prefer to be able to use arbitrary sets of vertices instead of only continuous ranges. * There are only very few functions for trees and forests.
The Data.Tree module in base is certainly quite small. You've made two changes: * made the types abstract, but provided the equivalent constructor and destructor functions. I'm not sure that gains anything. * added upwards and downwards accumulators (except that your "upwards" accumulator is actually a variant downwards accumulator, with quadratic performance). It might be worthwhile to add fold and accumulators. I was also thinking of adding unfolds (pure, and monadic depth-first and breadth-first).
Am Dienstag, 13. Januar 2004 19:12 schrieb Ross Paterson:
[moving to libraries]
On Tue, Jan 13, 2004 at 05:46:29PM +0100, Wolfgang Jeltsch wrote:
for my studies I recently needed graph and tree handling code. Because nothing I found seemed to satisfy my needs, I finally started writing my own graph and tree module. I was especially disappointed with Data.Graph and Data.Tree. The reasons are: * The Implementation of the types is not hidden so that code using Data.Graph and Data.Tree can get very implementation-dependent. * Vertices are ints which is too low level in my opintion. I think it would be better to allow different types for vertices because this seems to closer reflect what applications demand. * I'd prefer to be able to use arbitrary sets of vertices instead of only continuous ranges. * There are only very few functions for trees and forests.
The Data.Tree module in base is certainly quite small. You've made two changes:
* 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.
* 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?
It might be worthwhile to add fold and accumulators. I was also thinking of adding unfolds (pure, and monadic depth-first and breadth-first).
Sounds interesting. Wolfgang
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.
* 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.)
[resending to the library list] 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
participants (2)
-
Ross Paterson -
Wolfgang Jeltsch