function - 結果が安定するまで関数を繰り返し適用する

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

score 18 · Accepted Answer

これは、単純なパターンマッチングと再帰を使用して実装された、わずかな一般化です。converge無限リストを検索し、述語を満たす行内の 2 つの要素を探します。次に、2 番目のものを返します。

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)

score 18 · Accepted Answer

sdcvvcのコードを単純化すると、次のようになります。

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

機能は変わりません。関数はに渡され((==) >>=)、converge から (削減された) 引数が与えられ、後で until は、各反復で currentaをfに適用するかどうかをチェックすることを意味し(f a == a)ます。

score 10 · Accepted Answer

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

untilあまり知られていないプレリュード関数です。（小さな欠点は、これがsimplify'約n回ではなく約2n回使用することです。）

ただし、最も明確な方法は、ガードを使用するようにバージョンを変更することです。

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

score 1 · Accepted Answer

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

score 0 · Accepted Answer

以下は、使用できるそのような実装の1つです。

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

function - 結果が安定するまで関数を繰り返し適用する

5 に答える 5

Related

Reference