{- | 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
{- This file is part of HasGP.

   HasGP is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.

   HasGP is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with HasGP.  If not, see <http://www.gnu.org/licenses/>.
module HasGP.Support.Iterate where

import Control.Monad.State

{- | 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.
iterateOnce::(s -> s) -> (s -> a) -> State s a
iterateOnce updateState stateValue = 
    do currentState <- get
       let newState = updateState currentState
       put newState
       return $ stateValue newState

{- | 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::State s a -> (a -> a -> Bool) -> a -> State s a
iterateToConvergence doOnce converged currentValue = 
    do newValue <- doOnce
       if (converged currentValue newValue) 
         then return newValue
         else iterateToConvergence doOnce converged newValue

{- | 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'::(s -> s) -> (s -> a) -> (a -> a -> Bool) -> State s a
iterateToConvergence' updateState stateValue converged = 
    do startState <- get
       let initialValue = stateValue startState
       let itOnce = iterateOnce updateState stateValue
       iterateToConvergence itOnce converged initialValue

{- | 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.
iterateToConvergence''::State s a -> (a -> a -> Bool) -> State s a
iterateToConvergence'' doOnce converged = 
    do newValue <- doOnce
       iterateToConvergence doOnce converged newValue