Reiteración de suma de consecutivos
La reiteración de la suma de los elementos consecutivos de la lista [1,5,3] es 14 como se explica en el siguiente diagrama
|
1 2 3 4 5 |
1 + 5 = 6 \ ==> 14 / 5 + 3 = 8 |
y la de la lista [1,5,3,4] es 29 como se explica en el siguiente diagrama
|
1 2 3 4 5 6 7 8 9 |
1 + 5 = 6 \ ==> 14 / \ 5 + 3 = 8 ==> 29 \ / ==> 15 / 3 + 4 = 7 |
Definir la función
|
1 |
sumaReiterada :: Num a => [a] -> a |
tal que (sumaReiterada xs) es la suma reiterada de los elementos consecutivos de la lista no vacía xs. Por ejemplo,
|
1 2 |
sumaReiterada [1,5,3] == 14 sumaReiterada [1,5,3,4] == 29 |
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 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
import Test.QuickCheck import Test.QuickCheck -- 1ª solución -- =========== sumaReiterada1 :: Num a => [a] -> a sumaReiterada1 [x] = x sumaReiterada1 xs = sumaReiterada1 [x+y | (x,y) <- consecutivos xs] -- (consecutivos xs) es la lista de pares de elementos consecutivos de -- xs. Por ejemplo, -- consecutivos [1,5,3,4] == [(1,5),(5,3),(3,4)] consecutivos :: [a] -> [(a,a)] consecutivos xs = zip xs (tail xs) -- 2ª solución -- =========== sumaReiterada2 :: Num a => [a] -> a sumaReiterada2 [x] = x sumaReiterada2 xs = sumaReiterada2 (sumaConsecutivos xs) -- (sumaConsecutivos xs) es la suma de los de pares de elementos -- consecutivos de xs. Por ejemplo, -- sumaConsecutivos [1,5,3,4] == [6,8,7] sumaConsecutivos :: Num a => [a] -> [a] sumaConsecutivos xs = zipWith (+) xs (tail xs) -- 3ª solución -- =========== sumaReiterada3 :: Num a => [a] -> a sumaReiterada3 [x] = x sumaReiterada3 xs = sumaReiterada3 (zipWith (+) xs (tail xs)) -- 4ª solución -- =========== sumaReiterada4 :: Num a => [a] -> a sumaReiterada4 [x] = x sumaReiterada4 (x:xs) = sumaReiterada4 (zipWith (+) (x:xs) xs) -- 5ª solución -- =========== sumaReiterada5 :: Num a => [a] -> a sumaReiterada5 [x] = x sumaReiterada5 xs@(_:ys) = sumaReiterada5 (zipWith (+) xs ys) -- 6ª solución -- =========== sumaReiterada6 :: Num a => [a] -> a sumaReiterada6 xs = head (head (dropWhile noEsUnitaria (iterate sumaConsecutivos xs))) -- (noEsUnitaria xs) se verifica si la lista xs no tiene sólo un -- elemento. Por ejemplo, -- noEsUnitaria [] == True -- noEsUnitaria [7,5] == True -- noEsUnitaria [7] == False noEsUnitaria :: [a] -> Bool noEsUnitaria [_] = False noEsUnitaria _ = True -- 7ª solución -- =========== sumaReiterada7 :: Num a => [a] -> a sumaReiterada7 = head . head . dropWhile (not . null . tail) . iterate sumaConsecutivos -- 8ª solución -- =========== sumaReiterada8 :: Num a => [a] -> a sumaReiterada8 = head . head . dropWhile (not . null . tail) . iterate (zipWith (+) =<< tail) -- 9ª solución -- =========== sumaReiterada9 :: Num a => [a] -> a sumaReiterada9 = head . until ((==1) . length) (zipWith (+) <*> tail) -- 10ª solución -- =========== sumaReiterada10 :: Num a => [a] -> a sumaReiterada10 xs = sum (zipWith (*) xs (map fromIntegral (pascal !! (length xs - 1)))) -- pascal es la lista de las filas del triángulo de Pascal. Por ejemplo, -- λ> take 7 pascal -- [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1]] pascal :: [[Integer]] pascal = [1] : map f pascal where f xs = zipWith (+) (0:xs) (xs++[0]) -- Equivalencia de las definiciones -- ================================ -- La propiedad es prop_sumaReiterada :: [Integer] -> Property prop_sumaReiterada xs = not (null xs) ==> all (== (sumaReiterada1 xs)) [f xs | f <- [sumaReiterada2, sumaReiterada3, sumaReiterada4, sumaReiterada5, sumaReiterada6, sumaReiterada7, sumaReiterada8, sumaReiterada9, sumaReiterada10 ]] -- La comprobación es -- λ> quickCheck prop_sumaReiterada -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (show (sumaReiterada1 [1..4000])) -- 1208 -- (4.84 secs, 4,444,754,000 bytes) -- λ> length (show (sumaReiterada2 [1..4000])) -- 1208 -- (3.07 secs, 3,332,858,616 bytes) -- λ> length (show (sumaReiterada3 [1..4000])) -- 1208 -- (3.04 secs, 3,270,112,112 bytes) -- λ> length (show (sumaReiterada4 [1..4000])) -- 1208 -- (3.05 secs, 3,332,857,768 bytes) -- λ> length (show (sumaReiterada5 [1..4000])) -- 1208 -- (3.08 secs, 3,332,570,672 bytes) -- λ> length (show (sumaReiterada6 [1..4000])) -- 1208 -- (3.03 secs, 3,270,469,704 bytes) -- λ> length (show (sumaReiterada7 [1..4000])) -- 1208 -- (3.03 secs, 3,270,598,416 bytes) -- λ> length (show (sumaReiterada8 [1..4000])) -- 1208 -- (3.14 secs, 3,202,183,352 bytes) -- λ> length (show (sumaReiterada9 [1..4000])) -- 1208 -- (3.71 secs, 2,869,137,232 bytes) -- λ> length (show (sumaReiterada10 [1..4000])) -- 1208 -- (6.48 secs, 4,621,303,752 bytes) |
El código se encuentra en GitHub.
4 Comentarios