ghc-7.0.1: The GHC API

Dataflow

Synopsis

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.