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

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

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) 

Answer 2

简化/sf/answers/521373331/的代码将是:

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

功能不会改变.该函数被交给((==) >>=),它从收敛和后来给出参数(减少),直到意味着在每次迭代中它将检查是否将电流施加a到f,(f a == a).

Answer 3

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

until是一个鲜为人知的Prelude函数.(一个小缺点是它使用simplify'大约2n次而不是大约n次.)

但是,我认为最明确的方法是将您的版本修改为使用警卫,其中:

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