5 -----------------------------------------------------------------------------
6 -- | Solve the fixed-point of a dataflow problem.
8 -- Complexity: 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.
13 -- Sketch for proof of complexity:
14 -- Note that the state is threaded through the entire execution.
15 -- Also note that the height of the latice at any particular node
16 -- is the number of times 'update' can return non-Nothing for a
17 -- particular node. Every call (except for the top level one)
18 -- must be caused by a non-Nothing result and each non-Nothing
19 -- result causes as many calls as it has out-going edges.
20 -- Thus any particular node, n, may cause in total at
21 -- most H*out(n) further calls. When summed over all nodes,
22 -- that is H*E. The N term of the complexity is from the initial call
23 -- when 'update' will be passed 'Nothing'.
25 (node -> [node]) -- ^ map from nodes to those who's
26 -- value depend on the argument node
27 -> (node -> Maybe node -> s -> Maybe s)
28 -- ^ Given the node which needs to be
29 -- updated, and which node caused that node
30 -- to need to be updated, update the state.
32 -- The causing node will be 'Nothing' if
33 -- this is the initial/bootstrapping update.
35 -- Must return 'Nothing' if no change,
36 -- otherwise returrn 'Just' of the new state.
38 -> [node] -- ^ Nodes that should initially be updated
40 -> s -- ^ Initial state
41 -- (usually a map from node to
42 -- the value for that node)
45 fixedpoint dependants update nodes state =
46 foldr (fixedpoint' Nothing) state nodes where
47 -- Use a depth first traversal of nodes based on the update graph.
48 -- Terminate the traversal when the update doesn't change anything.
49 fixedpoint' cause node state =
50 case update node cause state of
53 foldr (fixedpoint' (Just node)) state' (dependants node)