graphs and trees again

[Wolfgang Jeltsch]

[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