graphs and trees again

[Wolfgang Jeltsch]

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 at 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 at jeltsch.net) nicht
erreichen können, kontaktieren Sie mich bitte unter meiner provisorischen
Adresse wolfgang.jeltsch at onlinehome.de!