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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell