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 > [EMAIL PROTECTED] > 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 ([EMAIL PROTECTED]) nicht erreichen k�nnen, kontaktieren Sie mich bitte unter meiner provisorischen Adresse [EMAIL PROTECTED] _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
