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

[ivan gomez rodriguez]

Chris Kuklewicz wrote:
> 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
>
In Haskell you can do this

iterUntil :: (a -> a -> Bool) -> (a -> a) -> a -> a
iterUntil goOn f a  | goOn a anext = iterUntil goOn f anext
                               | otherwise    = anext
                               where anext = f a