densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)]
   dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a]

     λ> densaAdispersa [9,0,0,5,0,4,7]
     [(6,9),(3,5),(1,4),(0,7)]

     λ> dispersaAdensa [(6,9),(3,5),(1,4),(0,7)]
     [9,0,0,5,0,4,7]

import Data.List (nub, sort)
import Test.QuickCheck

-- 1ª definición de densaAdispersa
-- ===============================

densaAdispersa :: (Num a, Eq a) => [a] -> [(Int,a)]
densaAdispersa xs = [(m,a) | (m,a) <- zip [n-1,n-2..] xs, a /= 0]
  where n  = length xs

-- 2ª definición de densaAdispersa
-- ===============================

densaAdispersa2 :: (Num a, Eq a) => [a] -> [(Int,a)]
densaAdispersa2 xs = reverse (aux (reverse xs) 0)
  where aux [] _ = []
        aux (0:ys) n = aux ys (n+1)
        aux (y:ys) n = (n,y) : aux ys (n+1)

-- Comprobación de equivalencia de densaAdispersa
-- ==============================================

-- La propiedad es
prop_densaAdispersa :: [Int] -> Bool
prop_densaAdispersa xs =
  densaAdispersa xs == densaAdispersa2 xs

-- La comprobación es
--    λ> quickCheck prop_densaAdispersa
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> densaAdispersa (5 : replicate (10^7) 0)
--    [(10000000,5)]
--    (4.54 secs, 3,280,572,504 bytes)
--    λ> densaAdispersa2 (5 : replicate (10^7) 0)
--    [(10000000,5)]
--    (7.35 secs, 3,696,968,576 bytes)

-- 1ª definición de dispersaAdensa
-- ===============================

dispersaAdensa :: (Num a, Eq a) => [(Int,a)] -> [a]
dispersaAdensa []      = []
dispersaAdensa [(n,a)] = a : replicate n 0
dispersaAdensa ((n,a):(m,b):ps) =
  a : replicate (n-m-1) 0 ++ dispersaAdensa ((m,b):ps)

-- 2ª definición de dispersaAdensa
-- ===============================

dispersaAdensa2 :: (Num a, Eq a) => [(Int,a)] -> [a]
dispersaAdensa2 []           = []
dispersaAdensa2 ps@((n,_):_) =
  [coeficiente ps m | m <- [n,n-1..0]]

-- (coeficiente ps n) es el coeficiente del término de grado n en el
-- polinomio cuya representación densa es ps. Por ejemplo,
--    coeficiente [(6,9),(3,5),(1,4),(0,7)] 3  ==  5
--    coeficiente [(6,9),(3,5),(1,4),(0,7)] 4  ==  0
coeficiente :: (Num a, Eq a) => [(Int,a)] -> Int -> a
coeficiente [] _                     = 0
coeficiente ((m,a):ps) n | n > m     = 0
                         | n == m    = a
                         | otherwise = coeficiente ps n

-- Comprobación de equivalencia de dispersaAdensa
-- ==============================================

-- Tipo de las representaciones dispersas de polinomios.
newtype Dispersa = Dis [(Int,Int)]
  deriving Show

-- dispersaArbitraria es un generador de representaciones dispersas de
-- polinomios. Por ejemplo,
--    λ> sample dispersaArbitraria
--    Dis []
--    Dis []
--    Dis [(3,-2),(2,0),(0,3)]
--    Dis [(6,1),(4,-2),(3,4),(2,-4)]
--    Dis []
--    Dis [(5,-7)]
--    Dis [(12,5),(11,-8),(10,3),(8,-10),(7,-5),(4,12),(3,6),(2,-8),(1,11)]
--    Dis [(7,-2),(2,-8)]
--    Dis [(14,-15)]
--    Dis [(17,5),(16,1),(15,-1),(14,10),(13,5),(12,-15),(9,12),(6,14)]
--    Dis [(19,17),(12,7),(8,-3),(7,13),(5,-2),(4,7)]
dispersaArbitraria :: Gen Dispersa
dispersaArbitraria = do
  (xs, ys) <- arbitrary
  let xs' = nub (reverse (sort (map abs xs)))
      ys' = filter (/= 0) ys
  return (Dis (zip xs' ys'))

-- Dispersa está contenida en Arbitrary
instance Arbitrary Dispersa where
  arbitrary = dispersaArbitraria

-- La propiedad es
prop_dispersaAdensa :: Dispersa -> Bool
prop_dispersaAdensa (Dis xs) =
  dispersaAdensa xs == dispersaAdensa2 xs

-- La comprobación es
--    λ> quickCheck prop_dispersaAdensa
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia de dispersaAdensa
-- ===========================================

-- La comparación es
--    λ> length (dispersaAdensa [(10^7,5)])
--    10000001
--    (0.11 secs, 560,566,848 bytes)
--    λ> length (dispersaAdensa2 [(10^7,5)])
--    10000001
--    (2.51 secs, 2,160,567,112 bytes)

-- Propiedad
-- =========

-- Tipo de las representaciones densas de polinomios.
newtype Densa = Den [Int]
  deriving Show

-- densaArbitraria es un generador de representaciones dispersas de
-- polinomios. Por ejemplo,
--    λ> sample densaArbitraria
--    Den []
--    Den []
--    Den []
--    Den [-6,6,5,-3]
--    Den []
--    Den [8,-7,-10,8,-10,-4,10,6,10]
--    Den [-6,2,11,-4,-9,-5,9,2,2,9]
--    Den [-6,9,-2]
--    Den [-1,-7,15,1,5,-2,13,16,8,7,2,16,-2,16,-7,4]
--    Den [8,13,-4,-2,-10,3,5,-4,-6,13,-9,-12,8,11,9,-18,12,10]
--    Den [-1,-2,11,17,-7,13,-12,-19,16,-10,-18,-19,1,-4,-17,10,1,10]
densaArbitraria :: Gen Densa
densaArbitraria = do
  ys <- arbitrary
  let ys' = dropWhile (== 0) ys
  return (Den ys')

-- Dispersa está contenida en Arbitrary
instance Arbitrary Densa where
  arbitrary = densaArbitraria

-- La primera propiedad es
prop_dispersaAdensa_densaAdispersa :: Densa -> Bool
prop_dispersaAdensa_densaAdispersa (Den xs) =
  dispersaAdensa (densaAdispersa xs) == xs

-- La comprobación es
--    λ> quickCheck prop_dispersaAdensa_densaAdispersa
--    +++ OK, passed 100 tests.

-- La segunda propiedad es
prop_densaAdispersa_dispersaAdensa :: Dispersa -> Bool
prop_densaAdispersa_dispersaAdensa (Dis ps) =
  densaAdispersa (dispersaAdensa ps) == ps

-- La comprobación es
--    λ> quickCheck prop_densaAdispersa_dispersaAdensa
--    +++ OK, passed 100 tests.

from itertools import dropwhile
from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

A = TypeVar('A', int, float, complex)

# 1ª definición de densaAdispersa
# ===============================

def densaAdispersa(xs: list[A]) -> list[tuple[int, A]]:
    n = len(xs)
    return [(m, a) for (m, a) in zip(range(n-1, -1, -1),  xs) if a != 0]

# 2ª definición de densaAdispersa
# ===============================

def densaAdispersa2(xs: list[A]) -> list[tuple[int, A]]:
    def aux(xs: list[A], n: int) -> list[tuple[int, A]]:
        if not xs:
            return []
        if xs[0] == 0:
            return aux(xs[1:], n + 1)
        return [(n, xs[0])] + aux(xs[1:], n + 1)

    return list(reversed(aux(list(reversed(xs)), 0)))

# 3ª definición de densaAdispersa
# ===============================

def densaAdispersa3(xs: list[A]) -> list[tuple[int, A]]:
    r = []
    n = len(xs) - 1
    for x in xs:
        if x != 0:
            r.append((n, x))
        n -= 1
    return r

# Comprobación de equivalencia de densaAdispersa
# ==============================================

# normalDensa(ps) es la representación dispersa de un polinomio.
def normalDensa(xs: list[A]) -> list[A]:
    return list(dropwhile(lambda x: x == 0, xs))

# densaAleatoria() genera representaciones densas de polinomios
# aleatorios. Por ejemplo,
#    >>> densaAleatoria().example()
#    [-5, 9, -6, -5, 7, -5, -1, 9]
#    >>> densaAleatoria().example()
#    [-4, 9, -3, -3, -5, 0, 6, -8, 8, 6, 0, -9]
#    >>> densaAleatoria().example()
#    [-3, -1, 2, 0, -9]
def densaAleatoria() -> st.SearchStrategy[list[int]]:
    return st.lists(st.integers(min_value=-9, max_value=9))\
             .map(normalDensa)

# La propiedad es
@given(xs=densaAleatoria())
def test_densaADispersa(xs: list[int]) -> None:
    r = densaAdispersa(xs)
    assert densaAdispersa2(xs) == r
    assert densaAdispersa3(xs) == r

# 1ª definición de dispersaAdensa
# ===============================

def dispersaAdensa(ps: list[tuple[int, A]]) -> list[A]:
    if not ps:
        return []
    if len(ps) == 1:
        return [ps[0][1]] + [0] * ps[0][0]
    (n, a) = ps[0]
    (m, _) = ps[1]
    return [a] + [0] * (n-m-1) + dispersaAdensa(ps[1:])

# 2ª definición de dispersaAdensa
# ===============================

# coeficiente(ps, n) es el coeficiente del término de grado n en el
# polinomio cuya representación densa es ps. Por ejemplo,
#    coeficiente([(6, 9), (3, 5), (1, 4), (0, 7)], 3)  ==  5
#    coeficiente([(6, 9), (3, 5), (1, 4), (0, 7)], 4)  ==  0
def coeficiente(ps: list[tuple[int, A]], n: int) -> A:
    if not ps:
        return 0
    (m, a) = ps[0]
    if n > m:
        return 0
    if n == m:
        return a
    return coeficiente(ps[1:], n)

def dispersaAdensa2(ps: list[tuple[int, A]]) -> list[A]:
    if not ps:
        return []
    n = ps[0][0]
    return [coeficiente(ps, m) for m in range(n, -1, -1)]

# 3ª definición de dispersaAdensa
# ===============================

def dispersaAdensa3(ps: list[tuple[int, A]]) -> list[A]:
    if not ps:
        return []
    n = ps[0][0]
    r: list[A] = [0] * (n + 1)
    for (m, a) in ps:
        r[n-m] = a
    return r

# Comprobación de equivalencia de dispersaAdensa
# ==============================================

# normalDispersa(ps) es la representación dispersa de un polinomio.
def normalDispersa(ps: list[tuple[int, A]]) -> list[tuple[int, A]]:
    xs = sorted(list({p[0] for p in ps}), reverse=True)
    ys = [p[1] for p in ps]
    return [(x, y) for (x, y) in zip(xs, ys) if y != 0]

# dispersaAleatoria() genera representaciones densas de polinomios
# aleatorios. Por ejemplo,
#    >>> dispersaAleatoria().example()
#    [(5, -6), (2, -1), (0, 2)]
#    >>> dispersaAleatoria().example()
#    [(6, -7)]
#    >>> dispersaAleatoria().example()
#    [(7, 2), (4, 9), (3, 3), (0, -2)]
def dispersaAleatoria() -> st.SearchStrategy[list[tuple[int, int]]]:
    return st.lists(st.tuples(st.integers(min_value=0, max_value=9),
                              st.integers(min_value=-9, max_value=9)))\
             .map(normalDispersa)

# La propiedad es
@given(ps=dispersaAleatoria())
def test_dispersaAdensa(ps: list[tuple[int, int]]) -> None:
    r = dispersaAdensa(ps)
    assert dispersaAdensa2(ps) == r
    assert dispersaAdensa3(ps) == r

# Propiedad
# =========

# La primera propiedad es
@given(xs=densaAleatoria())
def test_dispersaAdensa_densaAdispersa(xs: list[int]) -> None:
    assert dispersaAdensa(densaAdispersa(xs)) == xs

# La segunda propiedad es
@given(ps=dispersaAleatoria())
def test_densaAdispersa_dispersaAdensa(ps: list[tuple[int, int]]) -> None:
    assert densaAdispersa(dispersaAdensa(ps)) == ps

# La comprobación es
#    > poetry run pytest -v Polinomios_Transformaciones_dispersa_y_densa.py
#    test_densaADispersa PASSED
#    test_dispersaAdensa PASSED
#    test_dispersaAdensa_densaAdispersa PASSED
#    test_densaAdispersa_dispersaAdensa PASSED