Menu Close

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 lista de las sumas 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)

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>

5 soluciones de “Sumas parciales

  1. Rubén Muñoz Mkrtchian
    sumasParciales :: [Integer] -> [Integer]
    sumasParciales xs = scanr (+) 0 xs
  2. Mercedes Vega Gallo
    sumasParciales :: [Integer] -> [Integer]
    sumasParciales xs = scanl (-) (sum xs) xs
  3. Joaquín Infante Rodríguez
     
    import Data.List
     
    listasParciales :: [Integer] -> [[Integer]]
    listasParciales [] = [[]]
    listasParciales (x:y:xs) = (x:y:xs) : (y:xs) : listasParciales xs
     
    sumasParciales :: [Integer] -> [Integer]
    sumasParciales xs = map sum $listasParciales xs
  4. Alejandro García Alcaide
    sumasParciales :: [Integer] -> [Integer]
    sumasParciales xs = [sum x | x <- lista xs]
     
    -- Definimos una funcion auxiliar. 
    lista :: [Integer] -> [[Integer]]
    lista []     = [[]]
    lista (x:xs) = [x:xs] ++ lista (xs)
  5. Juan María Jiménez Jiménez
     
    sumasParciales :: [Integer] -> [Integer]
    sumasParciales xs = reverse (scanl (+) 0 (reverse xs))
     
    --Otra definicion quizas mas intuitiva, utilizando "tails"
     
    sumasParciales' :: [Integer] -> [Integer]
    sumasParciales' xs = map sum (tails xs)
     
    --La diferencia de eficiencia es muy significativa no calculando esta segunda el ultimo ejemplo.

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.