Reiteración de suma de consecutivos
Publicado el 4 de marzo de 2024 por José A. Alonso

sumaReiterada :: Num a => [a] -> a

sumaReiterada [1,5,3]    ==  14
sumaReiterada [1,5,3,4]  ==  29

module Reiteracion_de_suma_de_consecutivos where

import Test.Hspec (Spec, describe, hspec, it, shouldBe)
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])

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([Integer] -> Integer) -> Spec
specG sumaReiterada = do
  it "e1" $
    sumaReiterada [1,5,3] `shouldBe` 14
  it "e2" $
    sumaReiterada [1,5,3,4] `shouldBe` 29

spec :: Spec
spec = do
  describe "def. 1" $ specG sumaReiterada1
  describe "def. 2" $ specG sumaReiterada2
  describe "def. 3" $ specG sumaReiterada3
  describe "def. 4" $ specG sumaReiterada4
  describe "def. 5" $ specG sumaReiterada5
  describe "def. 6" $ specG sumaReiterada6
  describe "def. 7" $ specG sumaReiterada7
  describe "def. 8" $ specG sumaReiterada8
  describe "def. 9" $ specG sumaReiterada9
  describe "def. 10" $ specG sumaReiterada10

-- La verificación es
--    λ> verifica
--
--    20 examples, 0 failures

-- 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)

from sys import setrecursionlimit
from timeit import Timer, default_timer
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A')
setrecursionlimit(10**6)

# 1ª solución
# ===========

# 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)]
def consecutivos(xs: list[A]) -> list[tuple[A, A]]:
    return list(zip(xs, xs[1:]))

def sumaReiterada1(xs: list[int]) -> int:
    if len(xs) == 1:
        return xs[0]
    return sumaReiterada1([x + y for (x, y) in consecutivos(xs)])

# 2ª solución
# ===========

# sumaConsecutivos(xs) es la suma de los de pares de elementos
# consecutivos de xs. Por ejemplo,
#    sumaConsecutivos([1,5,3,4])   ==  [6,8,7]
def sumaConsecutivos(xs : list[int]) -> list[int]:
    return [x + y for (x, y) in list(zip(xs, xs[1:]))]

def sumaReiterada2(xs: list[int]) -> int:
    if len(xs) == 1:
        return xs[0]
    return sumaReiterada2(sumaConsecutivos(xs))

# 3ª solución
# ===========

def sumaReiterada3(xs: list[int]) -> int:
    if len(xs) == 1:
        return xs[0]
    return sumaReiterada3([x + y for (x, y) in list(zip(xs, xs[1:]))])

# Verificación
# ============

def test_sumaReiterada() -> None:
    for sumaReiterada in [sumaReiterada1, sumaReiterada2,
                          sumaReiterada3]:
        assert sumaReiterada([1,5,3]) == 14
        assert sumaReiterada([1,5,3,4]) == 29
    print("Verificado")

# La verificación es
#    >>> test_sumaReiterada()
#    Verificado

# Equivalencia de las definiciones
# ================================

# La propiedad es
@given(st.lists(st.integers(), min_size=1))
def test_sumaReiterada_equiv(xs: list[int]) -> None:
    r = sumaReiterada1(xs)
    assert sumaReiterada2(xs) == r
    assert sumaReiterada3(xs) == r

# La comprobación es
#    >>> test_sumaReiterada_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('sumaReiterada1(range(4000))')
#    2.18 segundos
#    >>> tiempo('sumaReiterada2(range(4000))')
#    1.90 segundos
#    >>> tiempo('sumaReiterada3(range(4000))')
#    1.97 segundos