graphs and trees again
wolfgang at jeltsch.net
Wed Jan 14 10:58:45 EST 2004
[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.)
flattenTree $ downAccuTree (flip (:))  $ spanningTree vertex graph
to get paths from a graph vertex to every reachable vertex (actually, the
More information about the Libraries