Reiteración de una función
Definir la función
|
1 |
reiteracion :: (a -> a) -> Int -> a -> a |
tal que (reiteracion f n x) es el resultado de aplicar n veces la función f a x. Por ejemplo,
|
1 2 3 4 |
reiteracion (+1) 10 5 == 15 reiteracion (+5) 10 0 == 50 reiteracion (*2) 4 1 == 16 reiteracion (5:) 4 [] == [5,5,5,5] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
import Test.QuickCheck (Fun (..), Positive (..), quickCheck) -- 1ª solución -- =========== reiteracion1 :: (a -> a) -> Int -> a -> a reiteracion1 _ 0 x = x reiteracion1 f n x = f (reiteracion1 f (n-1) x) -- 2ª solución -- =========== reiteracion2 :: (a -> a) -> Int -> a -> a reiteracion2 _ 0 = id reiteracion2 f n = f . reiteracion2 f (n-1) -- 3ª solución -- =========== reiteracion3 :: (a -> a) -> Int -> a -> a reiteracion3 _ 0 = id reiteracion3 f n | even n = reiteracion3 (f . f) (n `div` 2) | otherwise = f . reiteracion3 (f . f) (n `div` 2) -- 4ª solución -- =========== reiteracion4 :: (a -> a) -> Int -> a -> a reiteracion4 f n x = reiteraciones f x !! n reiteraciones :: (a -> a) -> a -> [a] reiteraciones f x = x : reiteraciones f (f x) -- 5ª solución -- =========== reiteracion5 :: (a -> a) -> Int -> a -> a reiteracion5 f n x = (iterate f x) !! n -- 6ª solución -- =========== -- Se puede eliminar los argumentos de la definición anterior como sigue: -- reiteracion4 f n x = iterate f x !! n -- reiteracion4 f n x = ((!!) (iterate f x)) n -- reiteracion4 f n x = (((!!) . (iterate f)) x) n -- reiteracion4 f n x = ((!!) . (iterate f)) x n -- reiteracion4 f n x = flip ((!!) . (iterate f)) n x -- reiteracion4 f = flip ((!!) . (iterate f)) -- reiteracion4 f = flip (((!!) .) (iterate f)) -- reiteracion4 f = flip (((!!) .) . iterate) f -- reiteracion4 f = (flip . ((!!) .) . iterate) f -- reiteracion4 = flip . ((!!) .) . iterate reiteracion6 :: (a -> a) -> Int -> a -> a reiteracion6 = flip . ((!!) .) . iterate -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_reiteracion :: Fun Int Int -> Positive Int -> Int -> Bool prop_reiteracion (Fun _ f) (Positive n) x = all (== reiteracion1 f n x) [reiteracion2 f n x, reiteracion3 f n x, reiteracion4 f n x, reiteracion5 f n x, reiteracion6 f n x] -- La comprobación es -- λ> quickCheck prop_reiteracion -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> reiteracion1 (+1) (10^7) 0 -- 10000000 -- (5.09 secs, 2,505,392,792 bytes) -- λ> reiteracion2 (+1) (10^7) 0 -- 10000000 -- (5.45 secs, 2,896,899,728 bytes) -- λ> reiteracion3 (+1) (10^7) 0 -- 10000000 -- (2.14 secs, 816,909,416 bytes) -- λ> reiteracion4 (+1) (10^7) 0 -- 10000000 -- (4.24 secs, 1,696,899,816 bytes) -- λ> reiteracion5 (+1) (10^7) 0 -- 10000000 -- (2.53 secs, 1,376,899,800 bytes) -- λ> reiteracion6 (+1) (10^7) 0 -- 10000000 -- (2.34 secs, 1,376,899,984 bytes) |
El código se encuentra en GitHub.
La elaboración de las soluciones se describe en el siguiente vídeo
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>