28

我想重复应用一个函数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
4

5 回答 5

18

这是用简单的模式匹配和递归实现的轻微概括。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) 
于 2011-09-16T10:32:00.083 回答
18

sdcvvc代码的简化是:

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

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

于 2014-05-29T01:07:30.887 回答
10
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
于 2011-09-16T17:12:50.183 回答
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
于 2011-09-16T20:57:36.823 回答
0

下面是一种可以使用的实现:

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
于 2011-09-16T12:48:25.083 回答