重复应用函数直到结果稳定 [英] repeatedly applying a function until the result is stable

问题描述

我想重复应用一个函数 simpl''，直到结果为stable（即 simplify'（x）== x < code $）：

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

推荐答案

模式匹配和递归。 converge 通过一个无限列表进行搜索，在一行中查找满足某个谓词的两个元素。然后它返回第二个。

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) 

这篇关于重复应用函数直到结果稳定的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！