function - the_tags - wordpress get first tag

Aplicando repetidamente una función hasta que el resultado sea estable.

Question

Quiero aplicar repetidamente una función simplify'' hasta que el resultado sea "estable" (es decir, 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

Esto parece ser un problema común para mí. ¿Hay una solución más elegante?

Actualización: encontré una solución mucho más simple, pero sigo buscando una solución más elegante :)

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

Answer 1

A continuación hay una implementación que puede ser usada:

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

Ejemplo de uso:

applyTill ( (==) stableExpr ) simplify'' initExpr

Answer 2

Aquí hay una ligera generalización implementada con un patrón de coincidencia y recursión directos. converge búsquedas a través de una lista infinita, buscando dos elementos en una fila que satisfagan algún predicado. Luego devuelve el segundo.

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

simplify = converge (==) . iterate simplify''

Esto facilita, por ejemplo, el uso de igualdad aproximada para la prueba de convergencia.

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

Answer 3

Una simplificación del código https://.com/a/7448190/1687259 sería:

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

La funcionalidad no cambia. La función se entrega a ((==) >>=) , cuyos argumentos dados (reducidos) convergen y más tarde hasta que significa que en cada iteración comprobará si se aplica la corriente de la a a la f , (fa == a) .

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

Answer 5

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

until es una función de Preludio algo menos conocida. (Una pequeña desventaja es que este uso simplify'' aproximadamente 2n veces en lugar de aproximadamente n).

Sin embargo, creo que la forma más clara es que se modifique su versión para usar guardas y dónde:

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

Otra forma más:

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