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