We often need to iterate some update equation until convergence is detected. This module uses the State monad to provide a very general way of expressing computations of this kind.

Copyright (C) Sean Holden 2011. sbh11@cl.cam.ac.uk

- iterateOnce :: (s -> s) -> (s -> a) -> State s a
- iterateToConvergence :: State s a -> (a -> a -> Bool) -> a -> State s a
- iterateToConvergence' :: (s -> s) -> (s -> a) -> (a -> a -> Bool) -> State s a
- iterateToConvergence'' :: State s a -> (a -> a -> Bool) -> State s a

# Documentation

iterateOnce :: (s -> s) -> (s -> a) -> State s aSource

iterateOnce takes a function to update a state and another to compute a value associated with a given state.

It returns a state transformer performing the corresponding update - that is, one iteration.

iterateToConvergence :: State s a -> (a -> a -> Bool) -> a -> State s aSource

iterateToConvergence takes a state transformer typically generated using iterateOnce, a convergence test that compares two values associated with the current and next states returning True if we've converged, and an initial value.

It returns a state transformer that performs iteration until convergence. When run from an initial state it returns the state at convergence and the corresponding value.

iterateToConvergence' :: (s -> s) -> (s -> a) -> (a -> a -> Bool) -> State s aSource

The same as iterateToConvergence, but takes the state update and state value functions directly, so the resulting state transformer only requires a start state to be run.

iterateToConvergence'' :: State s a -> (a -> a -> Bool) -> State s aSource

The same as iterateToConvergence, but does one update to obtain an initial value and continues from there. Consequently, no initial value is required, but you do one extra update.