[Haskell-cafe] iterative algorithms: how to do it in Haskell?

[Chris Kuklewicz]

Tamas K Papp wrote:
> Hi,
> 
> I am a newbie learning Haskell.  I have used languages with functional
> features before (R, Scheme) but not purely functional ones without
> side-effects.
> 
> Most of the programming I do is numerical (I am an economist).  I
> would like to know how to implement the iterative algorithm below in
> Haskell.
> 
> f is an a->a function, and there is a stopping rule 
> goOn(a,anext) :: a a -> Bool which determines when to stop.  The
> algorithm looks like this (in imperative pseudocode):
> 
> a = ainit
> 
> while (true) {
>       anext <- f(a)
>       if (goOn(a,anext))
>       	 a <- anext
>       else
>          stop and return anext
> }
> 
> For example, f can be a contraction mapping and goOn a test based on
> the metric.  I don't know how to do this in a purely functional
> language, especially if the object a is large and I would like it to
> be garbage collected if the iteration goes on.
> 
> Thank you,
> 
> Tamas
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

iterUntil :: (a -> a -> Bool) -> (a -> a) -> a -> a
iterUntil goOn f aInit =
   let loop a =
     let a' = f a
     in if goOn a a'
          then loop a'    -- tail recursive (so "a" will be collected)
          else a'
   in loop aInit

-- 
Chris