[Haskell-cafe] Folding part of a graph, and FGL's gfold function.
Jeffrey Brown
jeffbrown.the at gmail.com
Thu Aug 13 20:43:41 UTC 2015
Given a node N and an edge label L, I want to do things like "find N, and
all of N's L-children, and all of their L-children ... and add up their
values". Ideally the fold would not traverse the whole graph. (Note that in
general, the subgraph induced by N and L-succession is not a tree.)
Writing the fold myself, I can only imagine a very inefficient solution --
I would find each of N's L-children first, collect them, then find each of
theirs, etc.
In Data.Graph.Inductive.Basic, FGL provides a function called "gfold". This
is its type signature:
-- | Directed graph fold.
gfold :: (Graph gr) => (Context a b -> [Node]) -- ^ direction of fold
-> (Context a b -> c -> d) -- ^ depth aggregation
-> (Maybe d -> c -> c, c) -- ^ breadth\/level aggregation
-> [Node]
-> gr a b
-> c
Is it what I'm looking for? If so, how does it work?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20150813/135e2ca0/attachment.html>
More information about the Haskell-Cafe
mailing list