Dataflow
- fixedpoint :: (node -> [node]) -> (node -> Maybe node -> s -> Maybe s) -> [node] -> s -> s
Documentation
fixedpoint :: (node -> [node]) -> (node -> Maybe node -> s -> Maybe s) -> [node] -> s -> sSource
Solve the fixed-point of a dataflow problem.
Complexity: O(N+H*E) calls to the update function where: N = number of nodes, E = number of edges, H = maximum height of the lattice for any particular node.
Sketch for proof of complexity:
Note that the state is threaded through the entire execution.
Also note that the height of the latice at any particular node
is the number of times update can return non-Nothing for a
particular node. Every call (except for the top level one)
must be caused by a non-Nothing result and each non-Nothing
result causes as many calls as it has out-going edges.
Thus any particular node, n, may cause in total at
most H*out(n) further calls. When summed over all nodes,
that is H*E. The N term of the complexity is from the initial call
when update will be passed Nothing.