Re: [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@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


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe