Неоднократно применяя функцию до тех пор, пока результат не будет стабильным

Я хочу многократно применять функцию 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

Ответ 1

Здесь небольшое обобщение, реализованное с прямым сопоставлением шаблонов и рекурсией. converge выполняет поиск по бесконечному списку, ищет два элемента в строке, которые удовлетворяют некоторому предикату. Затем он возвращает второй.

converge :: (a -> a -> Bool) -> [a] -> a
converge p (x:[email protected](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)

Ответ 2

Упрощение fooobar.com/questions/224635/... кода:

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

Функциональность не изменяется. Функция передается ((==) >>=), которая дает аргументы (уменьшенные) от сходимости и позже, пока не будет означать, что в каждой итерации она проверит, применяет ли ток a к f, (f a == a).

Ответ 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

Ответ 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

Ответ 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