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

ajb at spamcop.net ajb at spamcop.net
Wed Aug 16 20:23:15 EDT 2006

G'day Tamas.

Quoting Tamas K Papp <tpapp at Princeton.EDU>:

> 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
> }

Here are a couple more suggestions.

First, this function scans an infinite list and stops when p x1 x2
is true for two adjacent elements x1 and x2:

    findFixpoint p (x1:xs@(x2:_))
        | p x1 x2   = x2
        | otherwise = findFixpoint p xs

Then you just need to pass it [ainit, f ainit, f (f ainit), ...]:

    findFixpoint dontGoOn (iterate f ainit)

Note that the function to pass to findFixpoint here is the condition
to use to _stop_.

If you're comfortable with monads, it's possible to directly simulate
complex imperative control flow.  It's not recommended to do this
unless the flow is very complex, but here we are for the record:

    import Control.Monad.Cont

    -- I used a Newton-Raphson square root evaluation for testing,
    -- but it has the same structure as your algorithm.
    mysqrt :: Double -> Double
    mysqrt x
      = runCont (callCC loop) id
        ainit = x * 0.5

        f x = 0.5 * (a + x/a)

        goOn a1 a2 = abs (a1 - a2) > 1e-5

        loop break
          = loop' ainit
            loop' a
              = do
                let anext = f a
                if goOn a anext
                 then loop' anext
                 else break anext

callCC defines a point outside the loop that you can "break" to.
You simply call that function (called a "continuation") and the
loop is broken.

Andrew Bromage

More information about the Haskell-Cafe mailing list