repeatedly applying a function until the result is stable

Question

I want to repeatedly apply a function simplify' until the result is "stable" (i.e. simplify'(x) == x):

simplify :: Expr -> Expr simplify expr =     let iterations = iterate simplify' expr         neighbours = zip iterations (tail iterations)         simplified = takeWhile (\(a, b) -> a /= b) neighbours     in  snd $ last ((expr, expr) : simplified)  simplify' :: Expr -> Expr 

This seems to be a common problem to me. Is there a more elegant solution?

Update: I found a much simpler solution, but I'm still looking for a more elegant solution :)

simplify expr =     let next = simplify' expr     in  if next == expr         then expr         else simplify next 

Answer 1

Here's a slight generalization implemented with straightforward pattern matching and recursion. converge searches through an infinite list, looking for two elements in a row which satisfy some predicate. It then returns the second one.

converge :: (a -> a -> Bool) -> [a] -> a converge p (x:ys@(y:_))     | p x y     = y     | otherwise = converge p ys  simplify = converge (==) . iterate simplify' 

This makes it easy to for example use approximate equality for the convergence test.

sqrt x = converge (\x y -> abs (x - y) < 0.001) $ iterate sqrt' x     where sqrt' y = y - (y^2 - x) / (2*y)