    {-# OPTIONS -Wall -fno-warn-name-shadowing #-}

    module Dataflow (
            fixedpoint
      ) where

    -----------------------------------------------------------------------------
    -- | 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'.
    fixedpoint ::
        (node -> [node])            -- map from nodes to those who's
                                    -- value depend on the argument node
        -> (node -> Maybe node -> s -> Maybe s)
                                    -- Given the node which needs to be
                                    -- updated, and which node caused that node
                                    -- to need to be updated, update the state.
                                    --
                                    -- The causing node will be 'Nothing' if
                                    -- this is the initial/bootstrapping update.
                                    --
                                    -- Must return 'Nothing' if no change,
                                    -- otherwise returrn 'Just' of the new state.

        -> [node]                   -- Nodes that should initially be updated

        -> s                        -- Initial state
                                    -- (usually a map from node to
                                    -- the value for that node)

        -> s                        -- Final state
    fixedpoint dependants update nodes state =
        foldr (fixedpoint' Nothing) state nodes where
            -- Use a depth first traversal of nodes based on the update graph.
            -- Terminate the traversal when the update doesn't change anything.
            fixedpoint' cause node state =
                case update node cause state of
                  Nothing -> state
                  Just state' ->
                      foldr (fixedpoint' (Just node)) state' (dependants node)