Polinomios

TAD de los polinomios: Construcción de términos

PorJosé A. Alonso 24-abril-202318-abril-2023

Usando el tipo abstracto de los polinomios, definir la función

   creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a

1	creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a

tal que (creaTermino n a) es el término a*x^n. Por ejemplo,

   creaTermino 2 5  ==  5*x^2

1	creaTermino 2 5 == 5*x^2

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, consPol)

creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a
creaTermino n a = consPol n a polCero

import TAD.Polinomio (Polinomio, polCero, consPol)

creaTermino :: (Num a, Eq a) => Int -> a -> Polinomio a

creaTermino n a = consPol n a polCero

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.TAD.Polinomio import (Polinomio, consPol, polCero)

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

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

def creaTermino(n: int, a: A) -> Polinomio[A]:
    return consPol(n, a, polCero())

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

def creaTermino2(n: int, a: A) -> Polinomio[A]:
    r: Polinomio[A] = polCero()
    return r.consPol(n, a)

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

# La propiedad es
@given(st.integers(min_value=0, max_value=9),
       st.integers(min_value=-9, max_value=9))
def test_creaTermino(n: int, a: int) -> None:
    assert creaTermino(n, a) == creaTermino2(n, a)

# La comprobación es
#    > poetry run pytest -q Pol_Crea_termino.py
#    1 passed in 0.21s

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.TAD.Polinomio import (Polinomio, consPol, polCero)

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

# 1ª solución

# ===========

def creaTermino(n: int, a: A) -> Polinomio[A]:

return consPol(n, a, polCero())

# 2ª solución

# ===========

def creaTermino2(n: int, a: A) -> Polinomio[A]:

r: Polinomio[A] = polCero()

return r.consPol(n, a)

# Equivalencia de las definiciones

# ================================

# La propiedad es

@given(st.integers(min_value=0, max_value=9),

st.integers(min_value=-9, max_value=9))

def test_creaTermino(n: int, a: int) -> None:

assert creaTermino(n, a) == creaTermino2(n, a)

# La comprobación es

# > poetry run pytest -q Pol_Crea_termino.py

# 1 passed in 0.21s

TAD de los polinomios: Transformaciones entre polinomios y listas densas

PorJosé A. Alonso 21-abril-202318-abril-2023

Utilizando el tipo abstracto de datos de los polinomios definir las funciones

   densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a
   polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a]

1 2	densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a]

tales que

densaApolinomio xs es el polinomio cuya representación densa es xs. Por ejemplo,

     λ> densaApolinomio [9,0,0,5,0,4,7]
     9*x^6 + 5*x^3 + 4*x + 7

1 2	λ> densaApolinomio [9,0,0,5,0,4,7] 9x^6 + 5x^3 + 4*x + 7

polinomioAdensa p es la representación densa del polinomio p. Por ejemplo,

     λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero)))
     λ> ejPol
     9*x^6 + 5*x^3 + 4*x + 7
     λ> polinomioAdensa ejPol
     [9,0,0,5,0,4,7]

λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero)))

λ> ejPol

9*x^6 + 5*x^3 + 4*x + 7

λ> polinomioAdensa ejPol

[9,0,0,5,0,4,7]

Comprobar con QuickCheck que ambas funciones son inversas.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, esPolCero, consPol, grado,
                      coefLider, restoPol)
import Polinomios_Transformaciones_dispersa_y_densa (densaAdispersa,
                                                     dispersaAdensa)
import Polinomios_Transformaciones_polinomios_dispersas (dispersaApolinomio,
                                                         polinomioAdispersa)
import Polinomios_Coeficiente (coeficiente)
import Data.List (sort, nub)
import Test.QuickCheck

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

densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a
densaApolinomio []     = polCero
densaApolinomio (x:xs) = consPol (length xs) x (densaApolinomio xs)

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

densaApolinomio2 :: (Num a, Eq a) => [a] -> Polinomio a
densaApolinomio2 = dispersaApolinomio . densaAdispersa

-- La función densaAdispersa está definida en el ejercicio
-- "Transformaciones entre las representaciones dispersa y densa" que se
-- encuentra en https://bit.ly/3GTyIqe

-- La función dispersaApolinomio se encuentra en el ejercicio
-- "Transformaciones entre polinomios y listas dispersas" que se
-- encuentra en https://bit.ly/41GgQaB

-- Comprobación de equivalencia de densaApolinomio
-- ===============================================

-- La propiedad es
prop_densaApolinomio :: [Int] -> Bool
prop_densaApolinomio xs =
  densaApolinomio xs == densaApolinomio2 xs

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

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

polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a]
polinomioAdensa p
  | esPolCero p = []
  | otherwise   = [coeficiente k p | k <- [n,n-1..0]]
  where n = grado p

-- La función coeficiente está definida en el ejercicio
-- "Coeficiente del término de grado k" que se encuentra en
-- https://bit.ly/413l3oQ

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

polinomioAdensa2 :: (Num a, Eq a) => Polinomio a -> [a]
polinomioAdensa2 = dispersaAdensa . polinomioAdispersa

-- La función dispersaAdensa está definida en el ejercicio
-- "Transformaciones entre las representaciones dispersa y densa" que se
-- encuentra en https://bit.ly/3GTyIqe

-- La función polinomioAdispersa se encuentra en el ejercicio
-- "Transformaciones entre polinomios y listas dispersas" que se
-- encuentra en https://bit.ly/41GgQaB

-- Comprobación de equivalencia de polinomioAdensa
-- ===============================================

-- La propiedad es
prop_polinomioAdensa :: Polinomio Int -> Bool
prop_polinomioAdensa p =
  polinomioAdensa p == polinomioAdensa2 p

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

-- Propiedades de inversa
-- ======================

-- La primera propiedad es
prop_polinomioAdensa_densaApolinomio :: [Int] -> Bool
prop_polinomioAdensa_densaApolinomio xs =
  polinomioAdensa (densaApolinomio xs') == xs'
  where xs' = dropWhile (== 0) xs

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

-- La segunda propiedad es
prop_densaApolinomio_polinomioAdensa :: Polinomio Int -> Bool
prop_densaApolinomio_polinomioAdensa p =
   densaApolinomio (polinomioAdensa p) == p

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

100

101

102

103

import TAD.Polinomio (Polinomio, polCero, esPolCero, consPol, grado,

coefLider, restoPol)

import Polinomios_Transformaciones_dispersa_y_densa (densaAdispersa,

dispersaAdensa)

import Polinomios_Transformaciones_polinomios_dispersas (dispersaApolinomio,

polinomioAdispersa)

import Polinomios_Coeficiente (coeficiente)

import Data.List (sort, nub)

import Test.QuickCheck

-- 1ª definición de densaApolinomio

-- ================================

densaApolinomio :: (Num a, Eq a) => [a] -> Polinomio a

densaApolinomio [] = polCero

densaApolinomio (x:xs) = consPol (length xs) x (densaApolinomio xs)

-- 2ª definición de densaApolinomio

-- ================================

densaApolinomio2 :: (Num a, Eq a) => [a] -> Polinomio a

densaApolinomio2 = dispersaApolinomio . densaAdispersa

-- La función densaAdispersa está definida en el ejercicio

-- "Transformaciones entre las representaciones dispersa y densa" que se

-- encuentra en https://bit.ly/3GTyIqe

-- La función dispersaApolinomio se encuentra en el ejercicio

-- "Transformaciones entre polinomios y listas dispersas" que se

-- encuentra en https://bit.ly/41GgQaB

-- Comprobación de equivalencia de densaApolinomio

-- ===============================================

-- La propiedad es

prop_densaApolinomio :: [Int] -> Bool

prop_densaApolinomio xs =

densaApolinomio xs == densaApolinomio2 xs

-- La comprobación es

-- λ> quickCheck prop_densaApolinomio

-- +++ OK, passed 100 tests.

-- 1ª definición de polinomioAdensa

-- ================================

polinomioAdensa :: (Num a, Eq a) => Polinomio a -> [a]

polinomioAdensa p

| esPolCero p = []

| otherwise = [coeficiente k p | k <- [n,n-1..0]]

where n = grado p

-- La función coeficiente está definida en el ejercicio

-- "Coeficiente del término de grado k" que se encuentra en

-- https://bit.ly/413l3oQ

-- 2ª definición de polinomioAdensa

-- ================================

polinomioAdensa2 :: (Num a, Eq a) => Polinomio a -> [a]

polinomioAdensa2 = dispersaAdensa . polinomioAdispersa

-- La función dispersaAdensa está definida en el ejercicio

-- "Transformaciones entre las representaciones dispersa y densa" que se

-- encuentra en https://bit.ly/3GTyIqe

-- La función polinomioAdispersa se encuentra en el ejercicio

-- "Transformaciones entre polinomios y listas dispersas" que se

-- encuentra en https://bit.ly/41GgQaB

-- Comprobación de equivalencia de polinomioAdensa

-- ===============================================

-- La propiedad es

prop_polinomioAdensa :: Polinomio Int -> Bool

prop_polinomioAdensa p =

polinomioAdensa p == polinomioAdensa2 p

-- La comprobación es

-- λ> quickCheck prop_polinomioAdensa

-- +++ OK, passed 100 tests.

-- Propiedades de inversa

-- ======================

-- La primera propiedad es

prop_polinomioAdensa_densaApolinomio :: [Int] -> Bool

prop_polinomioAdensa_densaApolinomio xs =

polinomioAdensa (densaApolinomio xs') == xs'

where xs' = dropWhile (== 0) xs

-- La comprobación es

-- λ> quickCheck prop_polinomioAdensa_densaApolinomio

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_densaApolinomio_polinomioAdensa :: Polinomio Int -> Bool

prop_densaApolinomio_polinomioAdensa p =

densaApolinomio (polinomioAdensa p) == p

-- La comprobación es

-- λ> quickCheck prop_densaApolinomio_polinomioAdensa

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given

from src.Polinomios_Coeficiente import coeficiente
from src.Polinomios_Transformaciones_dispersa_y_densa import (densaAdispersa,
                                                              densaAleatoria,
                                                              dispersaAdensa)
from src.Polinomios_Transformaciones_polinomios_dispersas import (
    dispersaApolinomio, polinomioAdispersa)
from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,
                               polCero, polinomioAleatorio, restoPol)

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

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

def densaApolinomio(xs: list[A]) -> Polinomio[A]:
    if not xs:
        return polCero()
    return consPol(len(xs[1:]), xs[0], densaApolinomio(xs[1:]))

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

def densaApolinomio2(xs: list[A]) -> Polinomio[A]:
    return dispersaApolinomio(densaAdispersa(xs))

# La función densaAdispersa está definida en el ejercicio
# "Transformaciones entre las representaciones dispersa y densa" que se
# encuentra en https://bit.ly/3GTyIqe

# La función dispersaApolinomio se encuentra en el ejercicio
# "Transformaciones entre polinomios y listas dispersas" que se
# encuentra en https://bit.ly/41GgQaB

# Comprobación de equivalencia de densaApolinomio
# ===============================================

# La propiedad es
@given(xs=densaAleatoria())
def test_densaApolinomio(xs: list[int]) -> None:
    assert densaApolinomio(xs) == densaApolinomio2(xs)

# La función densaAleatoria está definida en el ejercicio
# "Transformaciones entre las representaciones dispersa y densa" que se
# encuentra en https://bit.ly/3GTyIqe

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

def polinomioAdensa(p: Polinomio[A]) -> list[A]:
    if esPolCero(p):
        return []
    n = grado(p)
    return [coeficiente(k, p) for k in range(n, -1, -1)]

# La función coeficiente está definida en el ejercicio
# "Coeficiente del término de grado k" que se encuentra en
# https://bit.ly/413l3oQ

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

def polinomioAdensa2(p: Polinomio[A]) -> list[A]:
    return dispersaAdensa(polinomioAdispersa(p))

# La función dispersaAdensa está definida en el ejercicio
# "Transformaciones entre las representaciones dispersa y densa" que se
# encuentra en https://bit.ly/3GTyIqe

# La función polinomioAdispersa se encuentra en el ejercicio
# "Transformaciones entre polinomios y listas dispersas" que se
# encuentra en https://bit.ly/41GgQaB

# Comprobación de equivalencia de polinomioAdensa
# ===============================================

# La propiedad es
@given(p=polinomioAleatorio())
def test_polinomioAdensa(p: Polinomio[int]) -> None:
    assert polinomioAdensa(p) == polinomioAdensa2(p)

# Propiedades de inversa
# ======================

# La primera propiedad es
@given(xs=densaAleatoria())
def test_polinomioAdensa_densaApolinomio(xs: list[int]) -> None:
    assert polinomioAdensa(densaApolinomio(xs)) == xs

# La segunda propiedad es
@given(p=polinomioAleatorio())
def test_densaApolinomio_polinomioAdensa(p: Polinomio[int]) -> None:
    assert densaApolinomio(polinomioAdensa(p)) == p

# La comprobación es
#    > poetry run pytest -v Polinomios_Transformaciones_polinomios_densas.py
#    test_densaApolinomio PASSED
#    test_polinomioAdensa PASSED
#    test_polinomioAdensa_densaApolinomio PASSED
#    test_densaApolinomio_polinomioAdensa PASSED

100

101

102

103

from typing import TypeVar

from hypothesis import given

from src.Polinomios_Coeficiente import coeficiente

from src.Polinomios_Transformaciones_dispersa_y_densa import (densaAdispersa,

densaAleatoria,

dispersaAdensa)

from src.Polinomios_Transformaciones_polinomios_dispersas import (

dispersaApolinomio, polinomioAdispersa)

from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,

polCero, polinomioAleatorio, restoPol)

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

# 1ª definición de densaApolinomio

# ================================

def densaApolinomio(xs: list[A]) -> Polinomio[A]:

if not xs:

return polCero()

return consPol(len(xs[1:]), xs[0], densaApolinomio(xs[1:]))

# 2ª definición de densaApolinomio

# ================================

def densaApolinomio2(xs: list[A]) -> Polinomio[A]:

return dispersaApolinomio(densaAdispersa(xs))

# La función densaAdispersa está definida en el ejercicio

# "Transformaciones entre las representaciones dispersa y densa" que se

# encuentra en https://bit.ly/3GTyIqe

# La función dispersaApolinomio se encuentra en el ejercicio

# "Transformaciones entre polinomios y listas dispersas" que se

# encuentra en https://bit.ly/41GgQaB

# Comprobación de equivalencia de densaApolinomio

# ===============================================

# La propiedad es

@given(xs=densaAleatoria())

def test_densaApolinomio(xs: list[int]) -> None:

assert densaApolinomio(xs) == densaApolinomio2(xs)

# La función densaAleatoria está definida en el ejercicio

# "Transformaciones entre las representaciones dispersa y densa" que se

# encuentra en https://bit.ly/3GTyIqe

# 1ª definición de polinomioAdensa

# ================================

def polinomioAdensa(p: Polinomio[A]) -> list[A]:

if esPolCero(p):

return []

n = grado(p)

return [coeficiente(k, p) for k in range(n, -1, -1)]

# La función coeficiente está definida en el ejercicio

# "Coeficiente del término de grado k" que se encuentra en

# https://bit.ly/413l3oQ

# 2ª definición de polinomioAdensa

# ================================

def polinomioAdensa2(p: Polinomio[A]) -> list[A]:

return dispersaAdensa(polinomioAdispersa(p))

# La función dispersaAdensa está definida en el ejercicio

# "Transformaciones entre las representaciones dispersa y densa" que se

# encuentra en https://bit.ly/3GTyIqe

# La función polinomioAdispersa se encuentra en el ejercicio

# "Transformaciones entre polinomios y listas dispersas" que se

# encuentra en https://bit.ly/41GgQaB

# Comprobación de equivalencia de polinomioAdensa

# ===============================================

# La propiedad es

@given(p=polinomioAleatorio())

def test_polinomioAdensa(p: Polinomio[int]) -> None:

assert polinomioAdensa(p) == polinomioAdensa2(p)

# Propiedades de inversa

# ======================

# La primera propiedad es

@given(xs=densaAleatoria())

def test_polinomioAdensa_densaApolinomio(xs: list[int]) -> None:

assert polinomioAdensa(densaApolinomio(xs)) == xs

# La segunda propiedad es

@given(p=polinomioAleatorio())

def test_densaApolinomio_polinomioAdensa(p: Polinomio[int]) -> None:

assert densaApolinomio(polinomioAdensa(p)) == p

# La comprobación es

# > poetry run pytest -v Polinomios_Transformaciones_polinomios_densas.py

# test_densaApolinomio PASSED

# test_polinomioAdensa PASSED

# test_polinomioAdensa_densaApolinomio PASSED

# test_densaApolinomio_polinomioAdensa PASSED

TAD de los polinomios: Coeficiente del término de grado k

PorJosé A. Alonso 20-abril-202313-abril-2023

Utilizando el tipo abstracto de datos de los polinomios definir la función

   coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a

1	coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a

tal que coeficiente k p es el coeficiente del término de grado k del polinomio p. Por ejemplo,

   λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol
   x^5 + 5*x^2 + 4*x
   λ> coeficiente 2 ejPol
   5
   λ> coeficiente 3 ejPol
   0

λ> ejPol = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

λ> ejPol

x^5 + 5*x^2 + 4*x

λ> coeficiente 2 ejPol

λ> coeficiente 3 ejPol

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Polinomio (Polinomio, coefLider, grado, restoPol,
                      consPol, polCero)

coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a
coeficiente k p | k == n                 = coefLider p
                | k > grado (restoPol p) = 0
                | otherwise              = coeficiente k (restoPol p)
  where n = grado p

import TAD.Polinomio (Polinomio, coefLider, grado, restoPol,

consPol, polCero)

coeficiente :: (Num a, Eq a) => Int -> Polinomio a -> a

coeficiente k p | k == n = coefLider p

| k > grado (restoPol p) = 0

| otherwise = coeficiente k (restoPol p)

where n = grado p

Soluciones en Python

from typing import TypeVar

from src.TAD.Polinomio import (Polinomio, coefLider, consPol, grado, polCero,
                               restoPol)

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

def coeficiente(k: int, p: Polinomio[A]) -> A:
    if k == grado(p):
        return coefLider(p)
    if k > grado(restoPol(p)):
        return 0
    return coeficiente(k, restoPol(p))

from typing import TypeVar

from src.TAD.Polinomio import (Polinomio, coefLider, consPol, grado, polCero,

restoPol)

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

def coeficiente(k: int, p: Polinomio[A]) -> A:

if k == grado(p):

return coefLider(p)

if k > grado(restoPol(p)):

return 0

return coeficiente(k, restoPol(p))

TAD de los polinomios: Transformaciones entre polinomios y listas dispersas

PorJosé A. Alonso 19-abril-202313-abril-2023

Utilizando el tipo abstracto de datos de los polinomios definir las funciones

   dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
   polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]

1 2	dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]

tales que

dispersaApolinomio ps es el polinomiocuya representación dispersa es ps. Por ejemplo,

     λ> dispersaApolinomio [(6,9),(3,5),(1,4),(0,7)]
     9*x^6 + 5*x^3 + 4*x + 7

1 2	λ> dispersaApolinomio [(6,9),(3,5),(1,4),(0,7)] 9x^6 + 5x^3 + 4*x + 7

polinomioAdispersa p es la representación dispersa del polinomio p. Por ejemplo,

     λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero)))
     λ> ejPol
     9*x^6 + 5*x^3 + 4*x + 7
     λ> polinomioAdispersa ejPol
     [(6,9),(3,5),(1,4),(0,7)]

λ> ejPol = consPol 6 9 (consPol 3 5 (consPol 1 4 (consPol 0 7 polCero)))

λ> ejPol

9*x^6 + 5*x^3 + 4*x + 7

λ> polinomioAdispersa ejPol

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

Comprobar con QuickCheck que ambas funciones son inversas.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

import TAD.Polinomio (Polinomio, polCero, esPolCero, consPol, grado,
                      coefLider, restoPol)
import Data.List (sort, nub)
import Test.QuickCheck

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

dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
dispersaApolinomio []         = polCero
dispersaApolinomio ((n,a):ps) = consPol n a (dispersaApolinomio ps)

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

dispersaApolinomio2 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
dispersaApolinomio2 = foldr (\(x,y) -> consPol x y) polCero


-- 3ª definición de dispersaApolinomio
-- ===================================

dispersaApolinomio3 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a
dispersaApolinomio3 = foldr (uncurry consPol) polCero

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

-- 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_dispersaApolinomio :: Dispersa -> Bool
prop_dispersaApolinomio (Dis ps) =
  all (== dispersaApolinomio ps)
      [dispersaApolinomio2 ps,
       dispersaApolinomio3 ps]

-- Definición de polinomioAdispersa
-- ================================

polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]
polinomioAdispersa p
  | esPolCero p = []
  | otherwise   = (grado p, coefLider p) : polinomioAdispersa (restoPol p)

-- Propiedad de ser inversas
-- =========================

-- La primera propiedad es
prop_polinomioAdispersa_dispersaApolinomio :: Dispersa -> Bool
prop_polinomioAdispersa_dispersaApolinomio (Dis ps) =
  polinomioAdispersa (dispersaApolinomio ps) == ps

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

-- La segunda propiedad es
prop_dispersaApolinomio_polinomioAdispersa :: Polinomio Int -> Bool
prop_dispersaApolinomio_polinomioAdispersa p =
  dispersaApolinomio (polinomioAdispersa p) == p

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

import TAD.Polinomio (Polinomio, polCero, esPolCero, consPol, grado,

coefLider, restoPol)

import Data.List (sort, nub)

import Test.QuickCheck

-- 1ª definición de dispersaApolinomio

-- ===================================

dispersaApolinomio :: (Num a, Eq a) => [(Int,a)] -> Polinomio a

dispersaApolinomio [] = polCero

dispersaApolinomio ((n,a):ps) = consPol n a (dispersaApolinomio ps)

-- 2ª definición de dispersaApolinomio

-- ===================================

dispersaApolinomio2 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a

dispersaApolinomio2 = foldr (\(x,y) -> consPol x y) polCero

-- 3ª definición de dispersaApolinomio

-- ===================================

dispersaApolinomio3 :: (Num a, Eq a) => [(Int,a)] -> Polinomio a

dispersaApolinomio3 = foldr (uncurry consPol) polCero

-- Comprobación de equivalencia

-- ============================

-- 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 [(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_dispersaApolinomio :: Dispersa -> Bool

prop_dispersaApolinomio (Dis ps) =

all (== dispersaApolinomio ps)

[dispersaApolinomio2 ps,

dispersaApolinomio3 ps]

-- Definición de polinomioAdispersa

-- ================================

polinomioAdispersa :: (Num a, Eq a) => Polinomio a -> [(Int,a)]

polinomioAdispersa p

| esPolCero p = []

| otherwise = (grado p, coefLider p) : polinomioAdispersa (restoPol p)

-- Propiedad de ser inversas

-- =========================

-- La primera propiedad es

prop_polinomioAdispersa_dispersaApolinomio :: Dispersa -> Bool

prop_polinomioAdispersa_dispersaApolinomio (Dis ps) =

polinomioAdispersa (dispersaApolinomio ps) == ps

-- La comprobación es

-- λ> quickCheck prop_polinomioAdispersa_dispersaApolinomio

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_dispersaApolinomio_polinomioAdispersa :: Polinomio Int -> Bool

prop_dispersaApolinomio_polinomioAdispersa p =

dispersaApolinomio (polinomioAdispersa p) == p

-- La comprobación es

-- λ> quickCheck prop_dispersaApolinomio_polinomioAdispersa

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given

from src.Polinomios_Transformaciones_dispersa_y_densa import dispersaAleatoria
from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,
                               polCero, polinomioAleatorio, restoPol)

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


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

def dispersaApolinomio(ps: list[tuple[int, A]]) -> Polinomio[A]:
    if not ps:
        return polCero()
    (n, a) = ps[0]
    return consPol(n, a, dispersaApolinomio(ps[1:]))

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

def dispersaApolinomio2(ps: list[tuple[int, A]]) -> Polinomio[A]:
    r: Polinomio[A] = polCero()
    for (n, a) in reversed(ps):
        r = consPol(n, a, r)
    return r

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

# La propiedad es
@given(ps=dispersaAleatoria())
def test_dispersaApolinomio(ps: list[tuple[int, int]]) -> None:
    assert dispersaApolinomio(ps) == dispersaApolinomio2(ps)

# El generador dispersaAleatoria está definido en el ejercicio
# "Transformaciones entre las representaciones dispersa y densa" que se
# encuentra en https://bit.ly/402UpuT

# Definición de polinomioAdispersa
# ================================

def polinomioAdispersa(p: Polinomio[A]) -> list[tuple[int, A]]:
    if esPolCero(p):
        return []
    return [(grado(p), coefLider(p))] + polinomioAdispersa(restoPol(p))

# Propiedad de ser inversas
# =========================

# La primera propiedad es
@given(ps=dispersaAleatoria())
def test_polinomioAdispersa_dispersaApolinomio(ps: list[tuple[int,
                                                              int]]) -> None:
    assert polinomioAdispersa(dispersaApolinomio(ps)) == ps

# La segunda propiedad es
@given(p=polinomioAleatorio())
def test_dispersaApolinomio_polinomioAdispersa(p: Polinomio[int]) -> None:
    assert dispersaApolinomio(polinomioAdispersa(p)) == p

# La comprobación es
#    > poetry run pytest -v Polinomios_Transformaciones_polinomios_dispersas.py
#    test_dispersaApolinomio PASSED
#    test_polinomioAdispersa_dispersaApolinomio PASSED
#    test_dispersaApolinomio_polinomioAdispersa PASSED

from typing import TypeVar

from hypothesis import given

from src.Polinomios_Transformaciones_dispersa_y_densa import dispersaAleatoria

from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,

polCero, polinomioAleatorio, restoPol)

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

# 1ª definición de dispersaApolinomio

# ===================================

def dispersaApolinomio(ps: list[tuple[int, A]]) -> Polinomio[A]:

if not ps:

return polCero()

(n, a) = ps[0]

return consPol(n, a, dispersaApolinomio(ps[1:]))

# 2ª definición de dispersaApolinomio

# ===================================

def dispersaApolinomio2(ps: list[tuple[int, A]]) -> Polinomio[A]:

r: Polinomio[A] = polCero()

for (n, a) in reversed(ps):

r = consPol(n, a, r)

return r

# Comprobación de equivalencia

# ============================

# La propiedad es

@given(ps=dispersaAleatoria())

def test_dispersaApolinomio(ps: list[tuple[int, int]]) -> None:

assert dispersaApolinomio(ps) == dispersaApolinomio2(ps)

# El generador dispersaAleatoria está definido en el ejercicio

# "Transformaciones entre las representaciones dispersa y densa" que se

# encuentra en https://bit.ly/402UpuT

# Definición de polinomioAdispersa

# ================================

def polinomioAdispersa(p: Polinomio[A]) -> list[tuple[int, A]]:

if esPolCero(p):

return []

return [(grado(p), coefLider(p))] + polinomioAdispersa(restoPol(p))

# Propiedad de ser inversas

# =========================

# La primera propiedad es

@given(ps=dispersaAleatoria())

def test_polinomioAdispersa_dispersaApolinomio(ps: list[tuple[int,

int]]) -> None:

assert polinomioAdispersa(dispersaApolinomio(ps)) == ps

# La segunda propiedad es

@given(p=polinomioAleatorio())

def test_dispersaApolinomio_polinomioAdispersa(p: Polinomio[int]) -> None:

assert dispersaApolinomio(polinomioAdispersa(p)) == p

# La comprobación es

# > poetry run pytest -v Polinomios_Transformaciones_polinomios_dispersas.py

# test_dispersaApolinomio PASSED

# test_polinomioAdispersa_dispersaApolinomio PASSED

# test_dispersaApolinomio_polinomioAdispersa PASSED

TAD de los polinomios: Transformaciones entre las representaciones dispersa y densa

PorJosé A. Alonso 18-abril-202313-abril-2023

Definir las funciones

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

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

tales que

densaAdispersa xs es la representación dispersa del polinomio cuya representación densa es xs. Por ejemplo,

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

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

dispersaAdensa ps es la representación densa del polinomio cuya representación dispersa es ps. Por ejemplo,

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

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

Comprobar con QuickCheck que las funciones densaAdispersa y dispersaAdensa son inversas.

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.

Soluciones en Haskell

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.

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

158

159

160

161

162

163

164

165

166

167

168

169

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 [(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 [-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.

Soluciones en Python

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

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

158

159

160

161

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

TAD de los polinomios: Construcción de términos

TAD de los polinomios: Transformaciones entre polinomios y listas densas

TAD de los polinomios: Coeficiente del término de grado k

TAD de los polinomios: Transformaciones entre polinomios y listas dispersas

TAD de los polinomios: Transformaciones entre las representaciones dispersa y densa

Entradas recientes

Buscar

Correo electrónico