28

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
fredoverflow
  • 256,549
  • 94
  • 388
  • 662
  • I'd just write a simple recursive function. – augustss Sep 16 '11 at 10:13
  • Does "fix" apply to this? It seems like you are looking for a fixed point. – Tim Seguine Sep 16 '11 at 10:54
  • 3
    @Tim: Maybe, but the documentation for `fix` makes my head explode. – fredoverflow Sep 16 '11 at 11:40
  • @FredOverflow I'd like to point you in the right direction, but I don't know a heck of a lot about Haskell. The two sticking points seem to be that you need to have a lazy function for fix to converge, and that it converges to the "least defined" fixed point. I'm not sure, though, how either of those affect your situation. – Tim Seguine Sep 16 '11 at 11:50
  • @Tim (copying myself) You _can_ use `fix`, but it won't be an _interesting_ use of `fix`. In Haskell, `fix` is equivalent to recursion -- you can make any recursive definition non-recursive by calling `fix`, and you can take any call to `fix` and replace it by a recursive definition. So, the question "Can I use `fix` when defining this particular function?" is equivalent to the question "Can I use recursion when defining this particular function?". The answer is yes, but the question is silly, because writing the function is the real goal, and whether or not you use recursion is incidental. – Daniel Wagner Sep 16 '11 at 12:41
  • @Daniel: Okay, point taken. It just seems like since finding a fixed point is what he is asking for, that using the fixed point combinator does exactly that. His simpler definition of the function in his update seems to more or less do that except without using the fix function. It does: simplify expression, was expression a fixed point?, if not then repeat. Isn't it then simpler to just ask Haskell for the fixed point, since that is what he wanted in the first place? – Tim Seguine Sep 16 '11 at 13:27
  • 4
    @Tim: `fix` finds [a different kind of fixed point](http://en.wikibooks.org/wiki/Haskell/Denotational_semantics#Recursive_Definitions_as_Fixed_Point_Iterations). – hammar Sep 16 '11 at 14:08
  • @hammar: `fix` does find the regular fixed point in some special cases. e.g. `fix (const 42)` correctly returns 42 – newacct Sep 16 '11 at 20:07

5 Answers5

19

A simplification of sdcvvc's code would be:

converge :: Eq a => (a -> a) -> a -> a
converge = until =<< ((==) =<<)

The functionality doesn't change. The function is handed to ((==) >>=), which given arguments (reduced) from converge and later until means that in each iteration it will check if applying current a to f, (f a == a).

galva
  • 1,253
  • 10
  • 17
19

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)
hammar
  • 138,522
  • 17
  • 304
  • 385
  • How is your pattern matching different from `(x:y:ys)`, is it equivalent ? – Caridorc Aug 24 '16 at 19:40
  • 1
    @Caridorc Let's say the list is `[1, 2, 3, 4]`. With the pattern `(x:y:ys)` you get `ys = [3, 4]`. With `(x:ys@(y:_))` you get `ys = [2, 3, 4]`. The `ys@(y:_)` part is called an "as-pattern", and it binds the value matched by the whole `(y:_)` pattern to `ys` giving you the whole list, whereas `(y:ys)` would bind the first element to `y` and the rest to `ys`. Try playing around with `let (x:ys@(y:_)) = [1..4] in (x, y, ys)` and its variations in GHCi; you'll see how it works. – hammar Aug 25 '16 at 05:40
10
simplify = until (\x -> simplify' x == x) simplify'

until is a rather less-known Prelude function. (A small disadvantage is that this uses simplify' about 2n times instead of about n.)

I think the clearest way, however, is your version modified to use guards and where:

simplify x | x == y    = x
           | otherwise = simplify y
           where y = simplify' x

Yet another way:

until' :: (a -> Maybe a) -> a -> a
until' f x = maybe x (until' f) (f x)

simplify :: Integer -> Integer
simplify = until' $ \x -> let y = simplify' x in
                           if x==y then Nothing else Just y
sdcvvc
  • 25,343
  • 4
  • 66
  • 102
1
import Data.List.HT (groupBy)

fst_stable = head . (!!1) . groupBy (/=)
-- x, f(x), f^2(x), etc.
mk_lst f x = let lst = x : (map f lst) in lst
iter f = fst_stable . mk_lst f

test1 = iter (+1) 1 -- doesn't terminate
test2 = iter id 1 -- returns 1
test3 = iter (`div` 2) 4 -- returns 0
gatoatigrado
  • 16,580
  • 18
  • 81
  • 143
0

Below is one such implementation which can be used:

applyTill :: (a -> bool) -> (a -> a) -> a -> a
applyTill p f initial = head $ filter p $ scanl (\s e -> f s) initial [1..]

Example usage:

applyTill ( (==) stableExpr ) simplify' initExpr
Ankur
  • 33,367
  • 2
  • 46
  • 72