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

ajb@spamcop.net wrote:

G'day Tamas.

Quoting Tamas K Papp :

...

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_.

The compiler may not deforest that list, so creating the list may be a small overhead of this method.

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 where ainit = x * 0.5

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

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

loop break = loop' ainit where 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.

Cheers, Andrew Bromage

Note that "f x" should be "f a" above. But I like it. My version of the above looks like

import Control.Monad.Cont

mysqrt :: Double -> Double mysqrt x = doWhile goOn f aInit where aInit = x * 0.5 f a = 0.5 * (a + x/a) goOn a1 a2 = abs (a1 - a2) > 1e-5

doWhile :: (a -> a -> Bool) -> (a -> a) -> a -> a doWhile goOn f x0 = runCont (callCC withBreak) id where withBreak break = let loop x = do let x' = f x when (not (goOn x x')) (break x') loop x' in loop x0