5 --------------------------------------------------------------------------------
7 -- Solve a fixed-point of a dataflow problem.
9 -- dependants: map from nodes to those who's value depend on the argument node
11 -- Given the node which needs to be updated, and
12 -- which node caused that node to need to be updated,
14 -- (The causing node will be 'Nothing' if this is the initial update.)
15 -- Must return 'Nothing' if no change,
16 -- otherwise returrn 'Just' of the new state
17 -- nodes: a set of nodes that initially need updating
18 -- state: some sort of state (usually a map)
19 -- containing the initial value for each node
21 -- Complexity: O(N+H*E) calls to 'update' where
22 -- N = number of nodes,
23 -- E = number of edges,
24 -- H = maximum height of the lattice for any particular node.
26 -- Sketch for proof of complexity:
27 -- Note that the state is threaded through the entire execution.
28 -- Also note that the height of the latice at any particular node
29 -- is the number of times 'update' can return non-Nothing for a particular node.
30 -- Every call (except for the top level one) must be caused by a non-Nothing
31 -- result and each non-Nothing result causes as many calls as it has
32 -- out-going edges. Thus any particular node, n, may cause in total
33 -- at most H*out(n) further calls. When summed over all nodes,
34 -- that is H*E. The N term of the complexity is from the initial call
35 -- when 'update' will be passed 'Nothing'.
38 -> (node -> Maybe node -> s -> Maybe s)
40 fixedpoint dependants update nodes state =
41 foldr (fixedpoint' Nothing) state nodes where
42 fixedpoint' cause node state =
43 case update node cause state of
46 foldr (fixedpoint' (Just node)) state' (dependants node)