Sumas parciales
Los sufijos de la lista [3,7,2,5,4,6] son
[3,7,2,5,4,6]
[7,2,5,4,6]
[2,5,4,6]
[5,4,6]
[4,6]
[6]
[]
y la lista de sus sumas es [27,24,17,15,10,6,0].
Definir la función
sumasParciales :: [Integer] -> [Integer]
tal que (sumasParciales xs) es la suma de los sufijos de xs. Por ejemplo,
sumasParciales [3,7,2,5,4,6] == [27,24,17,15,10,6,0] sumasParciales [1..10] == [55,54,52,49,45,40,34,27,19,10,0] sum (sumasParciales [1..5*10^6]) == 41666679166667500000
Soluciones
import Data.List (tails) -- 1ª solución sumasParciales1 :: [Integer] -> [Integer] sumasParciales1 xs = map sum (tails xs) -- 2ª solución sumasParciales2 :: [Integer] -> [Integer] sumasParciales2 [] = [0] sumasParciales2 (x:xs) = (x + s):s:ss where (s:ss) = sumasParciales2 xs -- 3ª solución sumasParciales3 :: [Integer] -> [Integer] sumasParciales3 = foldr (\x (s:ss) -> (x + s) : (s:ss)) [0] -- 4ª solución sumasParciales4 :: [Integer] -> [Integer] sumasParciales4 xs = scanl (-) (sum xs) xs -- 5ª solución sumasParciales5 :: [Integer] -> [Integer] sumasParciales5 xs = reverse (0 : scanl1 (+) (reverse xs)) -- 6ª solución sumasParciales6 :: [Integer] -> [Integer] sumasParciales6 = scanr (+) 0 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> sum (sumasParciales1 [1..3*10^4]) -- 9000450005000 -- (19.70 secs, 40,132,872,616 bytes) -- λ> sum (sumasParciales2 [1..3*10^4]) -- 9000450005000 -- (0.04 secs, 16,932,840 bytes) -- λ> sum (sumasParciales3 [1..3*10^4]) -- 9000450005000 -- (0.02 secs, 13,880,608 bytes) -- λ> sum (sumasParciales4 [1..3*10^4]) -- 9000450005000 -- (0.03 secs, 12,178,080 bytes) -- λ> sum (sumasParciales5 [1..3*10^4]) -- 9000450005000 -- (0.02 secs, 9,974,600 bytes) -- λ> sum (sumasParciales6 [1..3*10^4]) -- 9000450005000 -- (0.02 secs, 10,694,368 bytes) -- -- λ> sum (sumasParciales2 [1..3*10^6]) -- 9000004500000500000 -- (3.13 secs, 1,685,139,696 bytes) -- λ> sum (sumasParciales3 [1..3*10^6]) -- 9000004500000500000 -- (2.37 secs, 1,380,492,448 bytes) -- λ> sum (sumasParciales4 [1..3*10^6]) -- 9000004500000500000 -- (1.84 secs, 1,211,188,264 bytes) -- λ> sum (sumasParciales5 [1..3*10^6]) -- 9000004500000500000 -- (1.22 secs, 987,790,392 bytes) -- λ> sum (sumasParciales6 [1..3*10^6]) -- 9000004500000500000 -- (1.34 secs, 1,059,792,344 bytes) -- -- λ> sum (sumasParciales5 [1..5*10^6]) -- 41666679166667500000 -- (2.36 secs, 1,844,332,576 bytes) -- λ> sum (sumasParciales6 [1..5*10^6]) -- 41666679166667500000 -- (2.03 secs, 1,964,365,912 bytes)