反复应用函数直到结果稳定

Question

我想要重复应用函数 simplify' 直到结果“稳定”（即 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

这对我来说似乎是一个常见的问题。是否有更优雅的解决方案？

更新：我找到了一个更简单的解决方案，但我仍在寻找更优雅的解决方案 :)

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

- fredoverflow

---

“fix”适用于这个吗？看起来你正在寻找一个固定点。 - Tim Seguine

@Tim：也许是这样，但是fix的文档让我困惑不已。 - fredoverflow

@FredOverflow 我想给你指明方向，但我对 Haskell 并不是很了解。两个关键点似乎是你需要有一个懒惰函数来使 fix 收敛，并且它会收敛到“最少定义”的固定点。然而，我不确定这两个点如何影响你的情况。 - Tim Seguine

@Tim（抄送给自己）你_可以_使用fix，但这不会是一个_有趣的_使用fix。在Haskell中，fix等同于递归--您可以通过调用fix使任何递归定义非递归，并且您可以将任何对fix的调用替换为递归定义。因此，“我可以在定义此特定函数时使用fix吗？”的问题等同于“我可以在定义此特定函数时使用递归吗？”答案是肯定的，但问题很愚蠢，因为编写函数才是真正的目标，无论您是否使用递归都是次要的。 - Daniel Wagner

@Tim提到fix函数发现了一种不同类型的不动点，在这里是指将递归定义转化为固定点迭代的方法。 - hammar

Answer 1

这里有一个使用简单模式匹配和递归实现的轻微泛化。converge搜索无限列表，寻找满足某个谓词的两个连续元素，然后返回第二个元素。

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

simplify = converge (==) . iterate simplify'

这使得例如使用近似相等来进行收敛测试变得容易。

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

- hammar

---

你的模式匹配与(x:y:ys)有何不同，它们是否等价？ - Caridorc

@Caridorc 假设列表是 [1, 2, 3, 4]。使用模式 (x:y:ys)，你会得到 ys = [3, 4]。使用 (x:ys@(y:_))，你会得到 ys = [2, 3, 4]。ys@(y:_) 部分被称为“as-pattern”，它将整个 (y:_) 模式匹配的值绑定到 ys，从而给出整个列表，而 (y:ys) 则将第一个元素绑定到 y，其余元素绑定到 ys。在 GHCi 中尝试使用 let (x:ys@(y:_)) = [1..4] in (x, y, ys) 及其变体进行实验，你会看到它是如何工作的。 - hammar

Answer 2

对 sdcvvc 代码的简化如下：

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

功能没有改变。函数被传递给((==) >>=)，它给定了从收敛到最后减少的参数，这意味着在每次迭代中它将检查应用当前a到f，(f a == a)是否成立。

- galva

---

这里提供最优雅的解决方案。 - user945967

这里的每个 f a 实际上计算了两次吗？一次是在 until 内部进行私有计算，另一次是在作为停止条件的函数中进行计算吗？ - Michal Charemza

Answer 3

simplify = until (\x -> simplify' x == x) simplify'

until 是一个比较不常见的预定义函数。(一个小缺点是它使用了大约2n次的 simplify', 而不是n次.)

我认为最清晰的方式是修改您的版本以使用 guards 和 where:

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

另外一种方法：

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

Answer 4

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

Answer 5

以下是一个可用的实现：

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

使用示例：

applyTill ( (==) stableExpr ) simplify' initExpr

- Ankur

---

applyTill 显然在 Prelude 中，以 until 的名称存在，正如我从 sdcvvc 的回答中了解到的。 - Max

你可以使用(stableExpr ==)将( (==) stableExpr )写成一个部分。 - icktoofay