abril 2023 – Exercitium

TAD de los polinomios: Valor de un polinomio en un punto

PorJosé A. Alonso 28-abril-202323-abril-2023

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

   valor :: (Num a, Eq a) => Polinomio a -> a -> a

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

tal que valor p c es el valor del polinomio p al sustituir su variable por c. Por ejemplo,

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

λ> ejPol = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

λ> ejPol

3*x^4 + -5*x^2 + 3

λ> valor ejPol 0

λ> valor ejPol 1

λ> valor ejPol (-2)

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)

valor :: (Num a, Eq a) => Polinomio a -> a -> a
valor p c
  | esPolCero p = 0
  | otherwise   =  b*c^n + valor r c
  where n = grado p
        b = coefLider p
        r = restoPol p

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

coefLider, restoPol)

valor :: (Num a, Eq a) => Polinomio a -> a -> a

valor p c

| esPolCero p = 0

| otherwise = b*c^n + valor r c

where n = grado p

b = coefLider p

r = restoPol p

Soluciones en Python

from typing import TypeVar

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

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

def valor(p: Polinomio[A], c: A) -> A:
    if esPolCero(p):
        return 0
    n = grado(p)
    b = coefLider(p)
    r = restoPol(p)
    return b*c**n + valor(r, c)

from typing import TypeVar

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

polCero, restoPol)

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

def valor(p: Polinomio[A], c: A) -> A:

if esPolCero(p):

return 0

n = grado(p)

b = coefLider(p)

r = restoPol(p)

return b*c**n + valor(r, c)

TAD de los polinomios: Producto de polinomios

PorJosé A. Alonso 27-abril-202320-abril-2023

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

   multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a

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

tal que multPol p q es el producto de los polinomios p y q. Por ejemplo,

   λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
   λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   3*x^4 + -5*x^2 + 3
   λ> ejPol2
   x^5 + 5*x^2 + 4*x
   λ> multPol ejPol1 ejPol2
   3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x

λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

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

λ> ejPol1

3*x^4 + -5*x^2 + 3

λ> ejPol2

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

λ> multPol ejPol1 ejPol2

3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x

Comprobar con QuickCheck las siguientes propiedades

El producto de polinomios es conmutativo.
El producto es distributivo respecto de la suma.

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 Pol_Termino_lider (termLider)
import Pol_Suma_de_polinomios (sumaPol)
import Test.QuickCheck

multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q
  | esPolCero p = polCero
  | otherwise    = sumaPol (multPorTerm (termLider p) q)
                           (multPol (restoPol p) q)

-- (multPorTerm t p) es el producto del término t por el polinomio
-- p. Por ejemplo,
--    ejTerm                     ==  4*x
--    ejPol2                     ==  x^5 + 5*x^2 + 4*x
--    multPorTerm ejTerm ejPol2  ==  4*x^6 + 20*x^3 + 16*x^2
multPorTerm :: (Num t, Eq t) => Polinomio t -> Polinomio t -> Polinomio t
multPorTerm term pol
  | esPolCero pol = polCero
  | otherwise     = consPol (n+m) (a*b) (multPorTerm term r)
  where n = grado term
        a = coefLider term
        m = grado pol
        b = coefLider pol
        r = restoPol pol

-- El producto de polinomios es conmutativo.
prop_conmutativaProducto :: Polinomio Int -> Polinomio Int -> Bool
prop_conmutativaProducto p q =
  multPol p q == multPol q p

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

-- El producto es distributivo respecto de la suma.
prop_distributivaProductoSuma :: Polinomio Int -> Polinomio Int
                                 -> Polinomio Int -> Bool
prop_distributivaProductoSuma p q r =
  multPol p (sumaPol q r) == sumaPol (multPol p q) (multPol p r)

-- Comprobación:
--    λ> quickCheck prop_distributivaProductoSuma
--    OK, passed 100 tests.

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

coefLider, restoPol)

import Pol_Termino_lider (termLider)

import Pol_Suma_de_polinomios (sumaPol)

import Test.QuickCheck

multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a

multPol p q

| esPolCero p = polCero

| otherwise = sumaPol (multPorTerm (termLider p) q)

(multPol (restoPol p) q)

-- (multPorTerm t p) es el producto del término t por el polinomio

-- p. Por ejemplo,

-- ejTerm == 4*x

-- ejPol2 == x^5 + 5*x^2 + 4*x

-- multPorTerm ejTerm ejPol2 == 4*x^6 + 20*x^3 + 16*x^2

multPorTerm :: (Num t, Eq t) => Polinomio t -> Polinomio t -> Polinomio t

multPorTerm term pol

| esPolCero pol = polCero

| otherwise = consPol (n+m) (a*b) (multPorTerm term r)

where n = grado term

a = coefLider term

m = grado pol

b = coefLider pol

r = restoPol pol

-- El producto de polinomios es conmutativo.

prop_conmutativaProducto :: Polinomio Int -> Polinomio Int -> Bool

prop_conmutativaProducto p q =

multPol p q == multPol q p

-- La comprobación es

-- λ> quickCheck prop_conmutativaProducto

-- OK, passed 100 tests.

-- El producto es distributivo respecto de la suma.

prop_distributivaProductoSuma :: Polinomio Int -> Polinomio Int

-> Polinomio Int -> Bool

prop_distributivaProductoSuma p q r =

multPol p (sumaPol q r) == sumaPol (multPol p q) (multPol p r)

-- Comprobación:

-- λ> quickCheck prop_distributivaProductoSuma

-- OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given

from src.Pol_Suma_de_polinomios import sumaPol
from src.Pol_Termino_lider import termLider
from src.TAD.Polinomio import (Polinomio, coefLider, consPol, esPolCero, grado,
                               polCero, polinomioAleatorio, restoPol)

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

# multPorTerm(t, p) es el producto del término t por el polinomio
# p. Por ejemplo,
#    ejTerm                     ==  4*x
#    ejPol2                     ==  x^5 + 5*x^2 + 4*x
#    multPorTerm ejTerm ejPol2  ==  4*x^6 + 20*x^3 + 16*x^2
def multPorTerm(term: Polinomio[A], pol: Polinomio[A]) -> Polinomio[A]:
    n = grado(term)
    a = coefLider(term)
    m = grado(pol)
    b = coefLider(pol)
    r = restoPol(pol)
    if esPolCero(pol):
        return polCero()
    return consPol(n + m, a * b, multPorTerm(term, r))

def multPol(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:
    if esPolCero(p):
        return polCero()
    return sumaPol(multPorTerm(termLider(p), q),
                   multPol(restoPol(p), q))

# El producto de polinomios es conmutativo.
@given(p=polinomioAleatorio(),
       q=polinomioAleatorio())
def test_conmutativaProducto(p: Polinomio[int], q: Polinomio[int]) -> None:
    assert multPol(p, q) == multPol(q, p)

# El producto es distributivo respecto de la suma.
@given(p=polinomioAleatorio(),
       q=polinomioAleatorio(),
       r=polinomioAleatorio())
def test_distributivaProductoSuma(p: Polinomio[int],
                                  q: Polinomio[int],
                                  r: Polinomio[int]) -> None:
    assert multPol(p, sumaPol(q, r)) == sumaPol(multPol(p, q), multPol(p, r))

# La comprobación es
#    > poetry run pytest -v Pol_Producto_polinomios.py
#    test_conmutativaProducto PASSED
#    test_distributivaProductoSuma PASSED

from typing import TypeVar

from hypothesis import given

from src.Pol_Suma_de_polinomios import sumaPol

from src.Pol_Termino_lider import termLider

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

polCero, polinomioAleatorio, restoPol)

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

# multPorTerm(t, p) es el producto del término t por el polinomio

# p. Por ejemplo,

# ejTerm == 4*x

# ejPol2 == x^5 + 5*x^2 + 4*x

# multPorTerm ejTerm ejPol2 == 4*x^6 + 20*x^3 + 16*x^2

def multPorTerm(term: Polinomio[A], pol: Polinomio[A]) -> Polinomio[A]:

n = grado(term)

a = coefLider(term)

m = grado(pol)

b = coefLider(pol)

r = restoPol(pol)

if esPolCero(pol):

return polCero()

return consPol(n + m, a * b, multPorTerm(term, r))

def multPol(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:

if esPolCero(p):

return polCero()

return sumaPol(multPorTerm(termLider(p), q),

multPol(restoPol(p), q))

# El producto de polinomios es conmutativo.

@given(p=polinomioAleatorio(),

q=polinomioAleatorio())

def test_conmutativaProducto(p: Polinomio[int], q: Polinomio[int]) -> None:

assert multPol(p, q) == multPol(q, p)

# El producto es distributivo respecto de la suma.

@given(p=polinomioAleatorio(),

q=polinomioAleatorio(),

r=polinomioAleatorio())

def test_distributivaProductoSuma(p: Polinomio[int],

q: Polinomio[int],

r: Polinomio[int]) -> None:

assert multPol(p, sumaPol(q, r)) == sumaPol(multPol(p, q), multPol(p, r))

# La comprobación es

# > poetry run pytest -v Pol_Producto_polinomios.py

# test_conmutativaProducto PASSED

# test_distributivaProductoSuma PASSED

TAD de los polinomios: Suma de polinomios

PorJosé A. Alonso 26-abril-202319-abril-2023

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

   sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a

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

tal que (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,

   λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
   λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
   λ> ejPol1
   3*x^4 + -5*x^2 + 3
   λ> ejPol2
   x^5 + 5*x^2 + 4*x
   λ> sumaPol ejPol1 ejPol2
   x^5 + 3*x^4 + 4*x + 3

λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

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

λ> ejPol1

3*x^4 + -5*x^2 + 3

λ> ejPol2

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

λ> sumaPol ejPol1 ejPol2

x^5 + 3*x^4 + 4*x + 3

Comprobar con QuickCheck las siguientes propiedades:

polCero es el elemento neutro de la suma.
la suma es conmutativa.

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 Test.QuickCheck

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q
  | esPolCero p = q
  | esPolCero q = p
  | n1 > n2      = consPol n1 a1 (sumaPol r1 q)
  | n1 < n2      = consPol n2 a2 (sumaPol p r2)
  | otherwise    = consPol n1 (a1+a2) (sumaPol r1 r2)
  where (n1, a1, r1) = (grado p, coefLider p, restoPol p)
        (n2, a2, r2) = (grado q, coefLider q, restoPol q)

-- Propiedad. El polinomio cero es el elemento neutro de la suma.
prop_neutroSumaPol :: Polinomio Int -> Bool
prop_neutroSumaPol p =
  sumaPol polCero p == p

-- Comprobación con QuickCheck.
--    λ> quickCheck prop_neutroSumaPol
--    OK, passed 100 tests.

-- Propiedad. La suma es conmutativa.
prop_conmutativaSuma :: Polinomio Int -> Polinomio Int -> Bool
prop_conmutativaSuma p q =
  sumaPol p q == sumaPol q p

-- Comprobación:
--    λ> quickCheck prop_conmutativaSuma
--    OK, passed 100 tests.

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

coefLider, restoPol)

import Test.QuickCheck

sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a

sumaPol p q

| esPolCero p = q

| esPolCero q = p

| n1 > n2 = consPol n1 a1 (sumaPol r1 q)

| n1 < n2 = consPol n2 a2 (sumaPol p r2)

| otherwise = consPol n1 (a1+a2) (sumaPol r1 r2)

where (n1, a1, r1) = (grado p, coefLider p, restoPol p)

(n2, a2, r2) = (grado q, coefLider q, restoPol q)

-- Propiedad. El polinomio cero es el elemento neutro de la suma.

prop_neutroSumaPol :: Polinomio Int -> Bool

prop_neutroSumaPol p =

sumaPol polCero p == p

-- Comprobación con QuickCheck.

-- λ> quickCheck prop_neutroSumaPol

-- OK, passed 100 tests.

-- Propiedad. La suma es conmutativa.

prop_conmutativaSuma :: Polinomio Int -> Polinomio Int -> Bool

prop_conmutativaSuma p q =

sumaPol p q == sumaPol q p

-- Comprobación:

-- λ> quickCheck prop_conmutativaSuma

-- OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given

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

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

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

def sumaPol(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:
    if esPolCero(p):
        return q
    if esPolCero(q):
        return p
    n1, a1, r1 = grado(p), coefLider(p), restoPol(p)
    n2, a2, r2 = grado(q), coefLider(q), restoPol(q)
    if n1 > n2:
        return consPol(n1, a1, sumaPol(r1, q))
    if n1 < n2:
        return consPol(n2, a2, sumaPol(p, r2))
    return consPol(n1, a1 + a2, sumaPol(r1, r2))

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

def sumaPol2(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:
    if p.esPolCero():
        return q
    if q.esPolCero():
        return p
    n1, a1, r1 = p.grado(), p.coefLider(), p.restoPol()
    n2, a2, r2 = q.grado(), q.coefLider(), q.restoPol()
    if n1 > n2:
        return sumaPol(r1, q).consPol(n1, a1)
    if n1 < n2:
        return sumaPol(p, r2).consPol(n2, a2)
    return sumaPol(r1, r2).consPol(n1, a1 + a2)

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

# La propiedad es
@given(p=polinomioAleatorio(), q=polinomioAleatorio())
def test_sumaPol(p: Polinomio[int], q: Polinomio[int]) -> None:
    assert sumaPol(p, q) == sumaPol2(p,q)

# Propiedad. El polinomio cero es el elemento neutro de la suma.
@given(p=polinomioAleatorio())
def test_neutroSumaPol(p: Polinomio[int]) -> None:
    assert sumaPol(polCero(), p) == p
    assert sumaPol(p, polCero()) == p

# -- Propiedad. La suma es conmutativa.
@given(p=polinomioAleatorio(), q=polinomioAleatorio())
def test_conmutativaSuma(p: Polinomio[int], q: Polinomio[int]) -> None:
    assert sumaPol(p, q) == sumaPol(q, p)

# La comprobación es
#    > poetry run pytest -v Pol_Suma_de_polinomios.py
#    test_sumaPol PASSED
#    test_neutroSumaPol PASSED
#    test_conmutativaSuma PASSED

from typing import TypeVar

from hypothesis import given

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

polCero, polinomioAleatorio, restoPol)

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

# 1ª solución

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

def sumaPol(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:

if esPolCero(p):

return q

if esPolCero(q):

return p

n1, a1, r1 = grado(p), coefLider(p), restoPol(p)

n2, a2, r2 = grado(q), coefLider(q), restoPol(q)

if n1 > n2:

return consPol(n1, a1, sumaPol(r1, q))

if n1 < n2:

return consPol(n2, a2, sumaPol(p, r2))

return consPol(n1, a1 + a2, sumaPol(r1, r2))

# 2ª solución

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

def sumaPol2(p: Polinomio[A], q: Polinomio[A]) -> Polinomio[A]:

if p.esPolCero():

return q

if q.esPolCero():

return p

n1, a1, r1 = p.grado(), p.coefLider(), p.restoPol()

n2, a2, r2 = q.grado(), q.coefLider(), q.restoPol()

if n1 > n2:

return sumaPol(r1, q).consPol(n1, a1)

if n1 < n2:

return sumaPol(p, r2).consPol(n2, a2)

return sumaPol(r1, r2).consPol(n1, a1 + a2)

# Equivalencia de las definiciones

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

# La propiedad es

@given(p=polinomioAleatorio(), q=polinomioAleatorio())

def test_sumaPol(p: Polinomio[int], q: Polinomio[int]) -> None:

assert sumaPol(p, q) == sumaPol2(p,q)

# Propiedad. El polinomio cero es el elemento neutro de la suma.

@given(p=polinomioAleatorio())

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

assert sumaPol(polCero(), p) == p

assert sumaPol(p, polCero()) == p

# -- Propiedad. La suma es conmutativa.

@given(p=polinomioAleatorio(), q=polinomioAleatorio())

def test_conmutativaSuma(p: Polinomio[int], q: Polinomio[int]) -> None:

assert sumaPol(p, q) == sumaPol(q, p)

# La comprobación es

# > poetry run pytest -v Pol_Suma_de_polinomios.py

# test_sumaPol PASSED

# test_neutroSumaPol PASSED

# test_conmutativaSuma PASSED

TAD de los polinomios: Término líder de un polinomio

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

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

   termLider :: (Num a, Eq a) => Polinomio a -> Polinomio a

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

tal que termLider p es el término líder del polinomio p. Por ejemplo,

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

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

λ> ejPol

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

λ> termLider ejPol

x^5

Soluciones

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

Soluciones en Haskell

import TAD.Polinomio (Polinomio, coefLider, grado, polCero, consPol)
import Pol_Crea_termino (creaTermino)

termLider :: (Num a, Eq a) => Polinomio a -> Polinomio a
termLider p = creaTermino (grado p) (coefLider p)

-- La función creaTermino está definida en el ejercicio
-- "Construcción de términos" que se encuentra en
-- https://bit.ly/3GXteuH

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

import Pol_Crea_termino (creaTermino)

termLider :: (Num a, Eq a) => Polinomio a -> Polinomio a

termLider p = creaTermino (grado p) (coefLider p)

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

-- "Construcción de términos" que se encuentra en

-- https://bit.ly/3GXteuH

Soluciones en Python

from typing import TypeVar

from hypothesis import given

from src.Pol_Crea_termino import creaTermino
from src.TAD.Polinomio import (Polinomio, coefLider, consPol, grado, polCero,
                               polinomioAleatorio)

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

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

def termLider(p: Polinomio[A]) -> Polinomio[A]:
    return creaTermino(grado(p), coefLider(p))

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

def termLider2(p: Polinomio[A]) -> Polinomio[A]:
    return creaTermino(p.grado(), p.coefLider())

# La función creaTermino está definida en el ejercicio
# "Construcción de términos" que se encuentra en
# https://bit.ly/3GXteuH

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

# La propiedad es
@given(p=polinomioAleatorio())
def test_termLider(p: Polinomio[int]) -> None:
    assert termLider(p) == termLider2(p)

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

from typing import TypeVar

from hypothesis import given

from src.Pol_Crea_termino import creaTermino

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

polinomioAleatorio)

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

# 1ª solución

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

def termLider(p: Polinomio[A]) -> Polinomio[A]:

return creaTermino(grado(p), coefLider(p))

# 2ª solución

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

def termLider2(p: Polinomio[A]) -> Polinomio[A]:

return creaTermino(p.grado(), p.coefLider())

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

# "Construcción de términos" que se encuentra en

# https://bit.ly/3GXteuH

# Equivalencia de las definiciones

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

# La propiedad es

@given(p=polinomioAleatorio())

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

assert termLider(p) == termLider2(p)

# La comprobación es

# > poetry run pytest -q Pol_Termino_lider.py

# 1 passed in 0.21s

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

El tipo abstracto de datos de los polinomios

PorJosé A. Alonso 17-abril-20232-mayo-2023

1. El tipo abstracto de datos de los polinomios

Un polinomio es una expresión matemática compuesta por una suma de términos, donde cada término es el producto de un coeficiente y una variable elevada a una potencia. Por ejemplo, el polinomio 3x^2+2x-1 tiene un término de segundo grado (3x^2), un término de primer grado (2x) y un término constante (-1).

Las operaciones que definen al tipo abstracto de datos (TAD) de los polinomios (cuyos coeficientes son del tipo a) son las siguientes:

   polCero   :: Polinomio a
   esPolCero :: Polinomio a -> Bool
   consPol   :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
   grado     :: Polinomio a -> Int
   coefLider :: Num a => Polinomio a -> a
   restoPol  :: (Num a, Eq a) => Polinomio a -> Polinomio a

polCero :: Polinomio a

esPolCero :: Polinomio a -> Bool

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

grado :: Polinomio a -> Int

coefLider :: Num a => Polinomio a -> a

restoPol :: (Num a, Eq a) => Polinomio a -> Polinomio a

tales que

polCero es el polinomio cero.
(esPolCero p) se verifica si p es el polinomio cero.
(consPol n b p) es el polinomio bx^n+p
(grado p) es el grado del polinomio p.
(coefLider p) es el coeficiente líder del polinomio p.
(restoPol p) es el resto del polinomio p.

Por ejemplo, el polinomio

   3*x^4 + -5*x^2 + 3

1	3x^4 + -5x^2 + 3

se representa por

   consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

1	consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

Las operaciones tienen que verificar las siguientes propiedades:

esPolCero polCero
n > grado p && b /= 0 ==> not (esPolCero (consPol n b p))
consPol (grado p) (coefLider p) (restoPol p) == p
n > grado p && b /= 0 ==> grado (consPol n b p) == n
n > grado p && b /= 0 ==> coefLider (consPol n b p) == b
n > grado p && b /= 0 ==> restoPol (consPol n b p) == p

2. Los polinomios en Haskell

2.1. El tipo abstracto de datos de los polinomios en Haskell

El TAD de los polinomios se encuentra en el módulo Polinomio.hs cuyo contenido es el siguiente:

module TAD.Polinomio
  ( Polinomio,
    polCero,   -- Polinomio a
    esPolCero, -- Polinomio a -> Bool
    consPol,   -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
    grado,     -- Polinomio a -> Int
    coefLider, -- Num a => Polinomio a -> a
    restoPol   -- (Num a, Eq a) => Polinomio a -> Polinomio a
  ) where

import TAD.PolRepTDA
-- import TAD.PolRepDensa
-- import TAD.PolRepDispersa

module TAD.Polinomio

( Polinomio,

polCero, -- Polinomio a

esPolCero, -- Polinomio a -> Bool

consPol, -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a

grado, -- Polinomio a -> Int

coefLider, -- Num a => Polinomio a -> a

restoPol -- (Num a, Eq a) => Polinomio a -> Polinomio a

) where

import TAD.PolRepTDA

-- import TAD.PolRepDensa

-- import TAD.PolRepDispersa

Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos las siguientes:

mediante tipo de dato algebraico,
mediante listas densas y
mediante listas dispersas.

Hay que elegir la que se desee utilizar, descomentándola y comentando las otras.

2.2. Implementación de los polinomios mediante tipos de datos algebraicos

Representamos un polinomio mediante los constructores ConsPol y
PolCero. Por ejemplo, el polinomio

   6x^4 -5x^2 + 4x -7

1	6x^4 -5x^2 + 4x -7

se representa por

   ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))

1	ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))

La implementación se encuentra en el módulo PolRepTDA.hs cuyo contenido es el siguiente:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.PolRepTDA
  ( Polinomio,
    polCero,   -- Polinomio a
    esPolCero, -- Polinomio a -> Bool
    consPol,   -- (Num a, Eq a)) => Int -> a -> Polinomio a -> Polinomio a
    grado,     -- Polinomio a -> Int
    coefLider, -- Num t => Polinomio t -> t
    restoPol   -- Polinomio t -> Polinomio t
  ) where

import Test.QuickCheck

-- Polinomio como tipo de dato algebra
data Polinomio a = PolCero
                 | ConsPol Int a (Polinomio a)
  deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por
-- ejemplo,
--    λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))
--    "3*x^4 + -5*x^2 + 3"
escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String
escribePol PolCero               = "0"
escribePol (ConsPol 0 b PolCero) = show b
escribePol (ConsPol 0 b p)       = concat [show b, " + ", escribePol p]
escribePol (ConsPol 1 b PolCero) = show b ++ "*x"
escribePol (ConsPol 1 b p)       = concat [show b, "*x + ", escribePol p]
escribePol (ConsPol n 1 PolCero) = "x^" ++ show n
escribePol (ConsPol n b PolCero) = concat [show b, "*x^", show n]
escribePol (ConsPol n 1 p)       = concat ["x^", show n, " + ", escribePol p]
escribePol (ConsPol n b p)       = concat [show b, "*x^", show n, " + ", escribePol p]

-- Procedimiento de escritura de polinomios.
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
  show = escribePol

-- Ejemplos de polinomios con coeficientes enteros:
ejPol1, ejPol2, ejPol3 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)

-- Comprobación de escritura:
--    > ejPol1
--    3*x^4 + -5*x^2 + 3
--    > ejPol2
--    x^5 + 5*x^2 + 4*x
--    > ejPol3
--    6*x^4 + 2*x

-- polCero es el polinomio cero. Por ejemplo,
--    > polCero
--    0
polCero :: Polinomio a
polCero = PolCero

-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,
--    esPolCero polCero  ==  True
--    esPolCero ejPol1   ==  False
esPolCero :: Polinomio a -> Bool
esPolCero PolCero = True
esPolCero _       = False

-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,
--    ejPol2               ==  x^5 + 5*x^2 + 4*x
--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x
--    consPol 3 2 polCero  ==  2*x^3
--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x
--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x
--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x
consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
consPol _ 0 p = p
consPol n b PolCero = ConsPol n b PolCero
consPol n b (ConsPol m c p)
  | n > m      = ConsPol n b (ConsPol m c p)
  | n < m      = ConsPol m c (consPol n b p)
  | b+c == 0   = p
  | otherwise  = ConsPol n (b+c) p

-- (grado p) es el grado del polinomio p. Por ejemplo,
--    ejPol3        ==  6*x^4 + 2*x
--    grado ejPol3  ==  4
grado :: Polinomio a -> Int
grado PolCero         = 0
grado (ConsPol n _ _) = n

-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,
--    ejPol3            ==  6*x^4 + 2*x
--    coefLider ejPol3  ==  6
coefLider :: Num t => Polinomio t -> t
coefLider PolCero         = 0
coefLider (ConsPol _ b _) = b

-- (restoPol p) es el resto del polinomio p. Por ejemplo,
--    ejPol3           ==  6*x^4 + 2*x
--    restoPol ejPol3  ==  2*x
--    ejPol2           ==  x^5 + 5*x^2 + 4*x
--    restoPol ejPol2  ==  5*x^2 + 4*x
restoPol :: Polinomio t -> Polinomio t
restoPol PolCero         = PolCero
restoPol (ConsPol _ _ p) = p

-- Generador de polinomios                                          --
-- =======================

-- genPolinomio es un generador de polinomios. Por ejemplo,
--    λ> sample (genPol 1)
--    7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10
--    -4*x^8 + 2*x
--    -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x
--    -9*x^9 + x^5 + -7
--    8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2
--    7*x^10 + 5*x^9 + -5
--    -8*x^10 + -7
--    -5*x
--    5*x^10 + 4*x^4 + -3
--    3*x^3 + -4
--    10*x
genPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)
genPol 0 = return polCero
genPol _ = do
  n <- choose (0,10)
  b <- arbitrary
  p <- genPol (div n 2)
  return (consPol n b p)

instance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where
  arbitrary = sized genPol

-- Propiedades de los polinomios
-- =============================

-- polCero es el polinomio cero.
prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
  esPolCero polCero

-- Si n es mayor que el grado de p y b no es cero, entonces
-- (consPol n b p) es un polinomio distinto del cero.
prop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property
prop_consPol_no_cero n b p =
  n > grado p && b /= 0  ==>
  not (esPolCero (consPol n b p))

-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.
prop_consPol :: Polinomio Int -> Bool
prop_consPol p =
  consPol (grado p) (coefLider p) (restoPol p) == p

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el grado de (consPol n b p) es n.
prop_grado :: Int -> Int -> Polinomio Int -> Property
prop_grado n b p =
  n > grado p && b /= 0 ==>
  grado (consPol n b p) == n

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el coeficiente líder de (consPol n b p) es b.
prop_coefLider :: Int -> Int -> Polinomio Int -> Property
prop_coefLider n b p =
  n > grado p && b /= 0 ==>
  coefLider (consPol n b p) == b

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el resto de (consPol n b p) es p.
prop_restoPol :: Int -> Int -> Polinomio Int -> Property
prop_restoPol n b p =
  n > grado p && b /= 0 ==>
  restoPol (consPol n b p) == p

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

return []

verificaPol :: IO Bool
verificaPol = $quickCheckAll

-- La verificación es
--    λ> verificaPol
--    === prop_polCero_es_cero from PolPropiedades.hs:53 ===
--    +++ OK, passed 1 test.
--
--    === prop_consPol_no_cero from PolPropiedades.hs:63 ===
--    +++ OK, passed 100 tests; 251 discarded.
--
--    === prop_consPol from PolPropiedades.hs:73 ===
--    +++ OK, passed 100 tests.
--
--    === prop_grado from PolPropiedades.hs:83 ===
--    +++ OK, passed 100 tests; 321 discarded.
--
--    === prop_coefLider from PolPropiedades.hs:94 ===
--    +++ OK, passed 100 tests; 340 discarded.
--
--    === prop_restoPol from PolPropiedades.hs:105 ===
--    +++ OK, passed 100 tests; 268 discarded.
--
--    True

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

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

{-# LANGUAGE TemplateHaskell #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.PolRepTDA

( Polinomio,

polCero, -- Polinomio a

esPolCero, -- Polinomio a -> Bool

consPol, -- (Num a, Eq a)) => Int -> a -> Polinomio a -> Polinomio a

grado, -- Polinomio a -> Int

coefLider, -- Num t => Polinomio t -> t

restoPol -- Polinomio t -> Polinomio t

) where

import Test.QuickCheck

-- Polinomio como tipo de dato algebra

data Polinomio a = PolCero

| ConsPol Int a (Polinomio a)

deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por

-- ejemplo,

-- λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))

-- "3*x^4 + -5*x^2 + 3"

escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String

escribePol PolCero = "0"

escribePol (ConsPol 0 b PolCero) = show b

escribePol (ConsPol 0 b p) = concat [show b, " + ", escribePol p]

escribePol (ConsPol 1 b PolCero) = show b ++ "*x"

escribePol (ConsPol 1 b p) = concat [show b, "*x + ", escribePol p]

escribePol (ConsPol n 1 PolCero) = "x^" ++ show n

escribePol (ConsPol n b PolCero) = concat [show b, "*x^", show n]

escribePol (ConsPol n 1 p) = concat ["x^", show n, " + ", escribePol p]

escribePol (ConsPol n b p) = concat [show b, "*x^", show n, " + ", escribePol p]

-- Procedimiento de escritura de polinomios.

instance (Num a, Show a, Eq a) => Show (Polinomio a) where

show = escribePol

-- Ejemplos de polinomios con coeficientes enteros:

ejPol1, ejPol2, ejPol3 :: Polinomio Int

ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

ejPol3 = consPol 4 6 (consPol 1 2 polCero)

-- Comprobación de escritura:

-- > ejPol1

-- 3*x^4 + -5*x^2 + 3

-- > ejPol2

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

-- > ejPol3

-- 6*x^4 + 2*x

-- polCero es el polinomio cero. Por ejemplo,

-- > polCero

-- 0

polCero :: Polinomio a

polCero = PolCero

-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,

-- esPolCero polCero == True

-- esPolCero ejPol1 == False

esPolCero :: Polinomio a -> Bool

esPolCero PolCero = True

esPolCero _ = False

-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,

-- ejPol2 == x^5 + 5*x^2 + 4*x

-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x

-- consPol 3 2 polCero == 2*x^3

-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x

-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x

-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x

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

consPol _ 0 p = p

consPol n b PolCero = ConsPol n b PolCero

consPol n b (ConsPol m c p)

| n > m = ConsPol n b (ConsPol m c p)

| n < m = ConsPol m c (consPol n b p)

| b+c == 0 = p

| otherwise = ConsPol n (b+c) p

-- (grado p) es el grado del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- grado ejPol3 == 4

grado :: Polinomio a -> Int

grado PolCero = 0

grado (ConsPol n _ _) = n

-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- coefLider ejPol3 == 6

coefLider :: Num t => Polinomio t -> t

coefLider PolCero = 0

coefLider (ConsPol _ b _) = b

-- (restoPol p) es el resto del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- restoPol ejPol3 == 2*x

-- ejPol2 == x^5 + 5*x^2 + 4*x

-- restoPol ejPol2 == 5*x^2 + 4*x

restoPol :: Polinomio t -> Polinomio t

restoPol PolCero = PolCero

restoPol (ConsPol _ _ p) = p

-- Generador de polinomios --

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

-- genPolinomio es un generador de polinomios. Por ejemplo,

-- λ> sample (genPol 1)

-- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10

-- -4*x^8 + 2*x

-- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x

-- -9*x^9 + x^5 + -7

-- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2

-- 7*x^10 + 5*x^9 + -5

-- -8*x^10 + -7

-- -5*x

-- 5*x^10 + 4*x^4 + -3

-- 3*x^3 + -4

-- 10*x

genPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)

genPol 0 = return polCero

genPol _ = do

n <- choose (0,10)

b <- arbitrary

p <- genPol (div n 2)

return (consPol n b p)

instance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where

arbitrary = sized genPol

-- Propiedades de los polinomios

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

-- polCero es el polinomio cero.

prop_polCero_es_cero :: Bool

prop_polCero_es_cero =

esPolCero polCero

-- Si n es mayor que el grado de p y b no es cero, entonces

-- (consPol n b p) es un polinomio distinto del cero.

prop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property

prop_consPol_no_cero n b p =

n > grado p && b /= 0 ==>

not (esPolCero (consPol n b p))

-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.

prop_consPol :: Polinomio Int -> Bool

prop_consPol p =

consPol (grado p) (coefLider p) (restoPol p) == p

-- Si n es mayor que el grado de p y b no es cero, entonces

-- el grado de (consPol n b p) es n.

prop_grado :: Int -> Int -> Polinomio Int -> Property

prop_grado n b p =

n > grado p && b /= 0 ==>

grado (consPol n b p) == n

-- Si n es mayor que el grado de p y b no es cero, entonces

-- el coeficiente líder de (consPol n b p) es b.

prop_coefLider :: Int -> Int -> Polinomio Int -> Property

prop_coefLider n b p =

n > grado p && b /= 0 ==>

coefLider (consPol n b p) == b

-- Si n es mayor que el grado de p y b no es cero, entonces

-- el resto de (consPol n b p) es p.

prop_restoPol :: Int -> Int -> Polinomio Int -> Property

prop_restoPol n b p =

n > grado p && b /= 0 ==>

restoPol (consPol n b p) == p

-- Verificación

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

return []

verificaPol :: IO Bool

verificaPol = $quickCheckAll

-- La verificación es

-- λ> verificaPol

-- === prop_polCero_es_cero from PolPropiedades.hs:53 ===

-- +++ OK, passed 1 test.

-- === prop_consPol_no_cero from PolPropiedades.hs:63 ===

-- +++ OK, passed 100 tests; 251 discarded.

-- === prop_consPol from PolPropiedades.hs:73 ===

-- +++ OK, passed 100 tests.

-- === prop_grado from PolPropiedades.hs:83 ===

-- +++ OK, passed 100 tests; 321 discarded.

-- === prop_coefLider from PolPropiedades.hs:94 ===

-- +++ OK, passed 100 tests; 340 discarded.

-- === prop_restoPol from PolPropiedades.hs:105 ===

-- +++ OK, passed 100 tests; 268 discarded.

-- True

2.3. Implementación de polinomios mediante listas densas

Representaremos un polinomio por la lista de sus coeficientes ordenados en orden decreciente según el grado. Por ejemplo, el polinomio

   6x^4 -5x^2 + 4x -7

1	6x^4 -5x^2 + 4x -7

se representa por

   [6,0,-2,4,-7]

1	[6,0,-2,4,-7]

En la representación se supone que, si la lista no es vacía, su primer elemento es distinto de cero.

La implementación se encuentra en el módulo PolRepDensa.hs cuyo contenido es el siguiente:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.PolRepDensa
  ( Polinomio,
    polCero,   -- Polinomio a
    esPolCero, -- Polinomio a -> Bool
    consPol,   -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
    grado,     -- Polinomio a -> Int
    coefLider, -- Num a => Polinomio a -> a
    restoPol   -- (Num a, Eq a) => Polinomio a -> Polinomio a
  ) where

import Test.QuickCheck

newtype Polinomio a = Pol [a]
  deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por
-- ejemplo,
--    λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))
--    "3*x^4 + -5*x^2 + 3"
escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String
escribePol pol
  | esPolCero pol         = "0"
  | n == 0 && esPolCero p = show a
  | n == 0                = concat [show a, " + ", escribePol p]
  | n == 1 && esPolCero p = show a ++ "*x"
  | n == 1                = concat [show a, "*x + ", escribePol p]
  | a == 1 && esPolCero p = "x^" ++ show n
  | esPolCero p           = concat [show a, "*x^", show n]
  | a == 1                = concat ["x^", show n, " + ", escribePol p]
  | otherwise             = concat [show a, "*x^", show n, " + ", escribePol p]
  where n = grado pol
        a = coefLider pol
        p = restoPol pol

-- Procedimiento de escritura de polinomios.
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
  show = escribePol

-- Ejemplos de polinomios con coeficientes enteros:
ejPol1, ejPol2, ejPol3 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)

-- Comprobación de escritura:
--    > ejPol1
--    3*x^4 + -5*x^2 + 3
--    > ejPol2
--    x^5 + 5*x^2 + 4*x
--    > ejPol3
--    6*x^4 + 2*x

-- polCero es el polinomio cero. Por ejemplo,
--    λ> polCero
--    0
polCero :: Polinomio a
polCero = Pol []

-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,
--    esPolCero polCero  ==  True
--    esPolCero ejPol1   ==  False
esPolCero :: Polinomio a -> Bool
esPolCero (Pol []) = True
esPolCero _        = False

-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,
--    ejPol2               ==  x^5 + 5*x^2 + 4*x
--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x
--    consPol 3 2 polCero  ==  2*x^3
--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x
--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x
--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x
consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
consPol _ 0 p = p
consPol n b p@(Pol xs)
    | esPolCero p = Pol (b : replicate n 0)
    | n > m       = Pol (b : replicate (n-m-1) 0 ++ xs)
    | n < m       = consPol m c (consPol n b (restoPol p))
    | b+c == 0    = Pol (dropWhile (==0) (tail xs))
    | otherwise   = Pol ((b+c):tail xs)
    where
      c = coefLider p
      m = grado p

-- (grado p) es el grado del polinomio p. Por ejemplo,
--    ejPol3        ==  6*x^4 + 2*x
--    grado ejPol3  ==  4
grado :: Polinomio a -> Int
grado (Pol []) = 0
grado (Pol xs) = length xs - 1

-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,
--    ejPol3            ==  6*x^4 + 2*x
--    coefLider ejPol3  ==  6
coefLider :: Num t => Polinomio t -> t
coefLider (Pol [])    = 0
coefLider (Pol (a:_)) = a

-- (restoPol p) es el resto del polinomio p. Por ejemplo,
--    ejPol3           ==  6*x^4 + 2*x
--    restoPol ejPol3  ==  2*x
--    ejPol2           ==  x^5 + 5*x^2 + 4*x
--    restoPol ejPol2  ==  5*x^2 + 4*x
restoPol :: (Num t, Eq t) => Polinomio t -> Polinomio t
restoPol (Pol [])     = polCero
restoPol (Pol [_])    = polCero
restoPol (Pol (_:b:as))
  | b == 0    = Pol (dropWhile (==0) as)
  | otherwise = Pol (b:as)

-- Generador de polinomios
-- =======================

-- genPolinomio es un generador de polinomios. Por ejemplo,
--    λ> sample (genPol 1)
--    7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10
--    -4*x^8 + 2*x
--    -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x
--    -9*x^9 + x^5 + -7
--    8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2
--    7*x^10 + 5*x^9 + -5
--    -8*x^10 + -7
--    -5*x
--    5*x^10 + 4*x^4 + -3
--    3*x^3 + -4
--    10*x
genPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)
genPol 0 = return polCero
genPol _ = do
  n <- choose (0,10)
  b <- arbitrary
  p <- genPol (div n 2)
  return (consPol n b p)

instance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where
  arbitrary = sized genPol

-- Propiedades de los polinomios
-- =============================

-- polCero es el polinomio cero.
prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
  esPolCero polCero

-- Si n es mayor que el grado de p y b no es cero, entonces
-- (consPol n b p) es un polinomio distinto del cero.
prop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property
prop_consPol_no_cero n b p =
  n > grado p && b /= 0  ==>
  not (esPolCero (consPol n b p))

-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.
prop_consPol :: Polinomio Int -> Bool
prop_consPol p =
  consPol (grado p) (coefLider p) (restoPol p) == p

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el grado de (consPol n b p) es n.
prop_grado :: Int -> Int -> Polinomio Int -> Property
prop_grado n b p =
  n > grado p && b /= 0 ==>
  grado (consPol n b p) == n

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el coeficiente líder de (consPol n b p) es b.
prop_coefLider :: Int -> Int -> Polinomio Int -> Property
prop_coefLider n b p =
  n > grado p && b /= 0 ==>
  coefLider (consPol n b p) == b

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el resto de (consPol n b p) es p.
prop_restoPol :: Int -> Int -> Polinomio Int -> Property
prop_restoPol n b p =
  n > grado p && b /= 0 ==>
  restoPol (consPol n b p) == p

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

return []

verificaPol :: IO Bool
verificaPol = $quickCheckAll

-- La verificación es
--    λ> verificaPol
--    === prop_polCero_es_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:157 ===
--    +++ OK, passed 1 test.
--
--    === prop_consPol_no_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:163 ===
--    +++ OK, passed 100 tests; 274 discarded.
--
--    === prop_consPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:169 ===
--    +++ OK, passed 100 tests.
--
--    === prop_grado from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:175 ===
--    +++ OK, passed 100 tests; 297 discarded.
--
--    === prop_coefLider from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:182 ===
--    +++ OK, passed 100 tests; 248 discarded.
--
--    === prop_restoPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:189 ===
--    +++ OK, passed 100 tests; 322 discarded.
--
--    True

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

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

{-# LANGUAGE TemplateHaskell #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.PolRepDensa

( Polinomio,

polCero, -- Polinomio a

esPolCero, -- Polinomio a -> Bool

consPol, -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a

grado, -- Polinomio a -> Int

coefLider, -- Num a => Polinomio a -> a

restoPol -- (Num a, Eq a) => Polinomio a -> Polinomio a

) where

import Test.QuickCheck

newtype Polinomio a = Pol [a]

deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por

-- ejemplo,

-- λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))

-- "3*x^4 + -5*x^2 + 3"

escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String

escribePol pol

| esPolCero pol = "0"

| n == 0 && esPolCero p = show a

| n == 0 = concat [show a, " + ", escribePol p]

| n == 1 && esPolCero p = show a ++ "*x"

| n == 1 = concat [show a, "*x + ", escribePol p]

| a == 1 && esPolCero p = "x^" ++ show n

| esPolCero p = concat [show a, "*x^", show n]

| a == 1 = concat ["x^", show n, " + ", escribePol p]

| otherwise = concat [show a, "*x^", show n, " + ", escribePol p]

where n = grado pol

a = coefLider pol

p = restoPol pol

-- Procedimiento de escritura de polinomios.

instance (Num a, Show a, Eq a) => Show (Polinomio a) where

show = escribePol

-- Ejemplos de polinomios con coeficientes enteros:

ejPol1, ejPol2, ejPol3 :: Polinomio Int

ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

ejPol3 = consPol 4 6 (consPol 1 2 polCero)

-- Comprobación de escritura:

-- > ejPol1

-- 3*x^4 + -5*x^2 + 3

-- > ejPol2

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

-- > ejPol3

-- 6*x^4 + 2*x

-- polCero es el polinomio cero. Por ejemplo,

-- λ> polCero

-- 0

polCero :: Polinomio a

polCero = Pol []

-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,

-- esPolCero polCero == True

-- esPolCero ejPol1 == False

esPolCero :: Polinomio a -> Bool

esPolCero (Pol []) = True

esPolCero _ = False

-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,

-- ejPol2 == x^5 + 5*x^2 + 4*x

-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x

-- consPol 3 2 polCero == 2*x^3

-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x

-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x

-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x

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

consPol _ 0 p = p

consPol n b p@(Pol xs)

| esPolCero p = Pol (b : replicate n 0)

| n > m = Pol (b : replicate (n-m-1) 0 ++ xs)

| n < m = consPol m c (consPol n b (restoPol p))

| b+c == 0 = Pol (dropWhile (==0) (tail xs))

| otherwise = Pol ((b+c):tail xs)

where

c = coefLider p

m = grado p

-- (grado p) es el grado del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- grado ejPol3 == 4

grado :: Polinomio a -> Int

grado (Pol []) = 0

grado (Pol xs) = length xs - 1

-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- coefLider ejPol3 == 6

coefLider :: Num t => Polinomio t -> t

coefLider (Pol []) = 0

coefLider (Pol (a:_)) = a

-- (restoPol p) es el resto del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- restoPol ejPol3 == 2*x

-- ejPol2 == x^5 + 5*x^2 + 4*x

-- restoPol ejPol2 == 5*x^2 + 4*x

restoPol :: (Num t, Eq t) => Polinomio t -> Polinomio t

restoPol (Pol []) = polCero

restoPol (Pol [_]) = polCero

restoPol (Pol (_:b:as))

| b == 0 = Pol (dropWhile (==0) as)

| otherwise = Pol (b:as)

-- Generador de polinomios

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

-- genPolinomio es un generador de polinomios. Por ejemplo,

-- λ> sample (genPol 1)

-- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10

-- -4*x^8 + 2*x

-- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x

-- -9*x^9 + x^5 + -7

-- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2

-- 7*x^10 + 5*x^9 + -5

-- -8*x^10 + -7

-- -5*x

-- 5*x^10 + 4*x^4 + -3

-- 3*x^3 + -4

-- 10*x

genPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)

genPol 0 = return polCero

genPol _ = do

n <- choose (0,10)

b <- arbitrary

p <- genPol (div n 2)

return (consPol n b p)

instance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where

arbitrary = sized genPol

-- Propiedades de los polinomios

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

-- polCero es el polinomio cero.

prop_polCero_es_cero :: Bool

prop_polCero_es_cero =

esPolCero polCero

-- Si n es mayor que el grado de p y b no es cero, entonces

-- (consPol n b p) es un polinomio distinto del cero.

prop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property

prop_consPol_no_cero n b p =

n > grado p && b /= 0 ==>

not (esPolCero (consPol n b p))

-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.

prop_consPol :: Polinomio Int -> Bool

prop_consPol p =

consPol (grado p) (coefLider p) (restoPol p) == p

-- Si n es mayor que el grado de p y b no es cero, entonces

-- el grado de (consPol n b p) es n.

prop_grado :: Int -> Int -> Polinomio Int -> Property

prop_grado n b p =

n > grado p && b /= 0 ==>

grado (consPol n b p) == n

-- Si n es mayor que el grado de p y b no es cero, entonces

-- el coeficiente líder de (consPol n b p) es b.

prop_coefLider :: Int -> Int -> Polinomio Int -> Property

prop_coefLider n b p =

n > grado p && b /= 0 ==>

coefLider (consPol n b p) == b

-- Si n es mayor que el grado de p y b no es cero, entonces

-- el resto de (consPol n b p) es p.

prop_restoPol :: Int -> Int -> Polinomio Int -> Property

prop_restoPol n b p =

n > grado p && b /= 0 ==>

restoPol (consPol n b p) == p

-- Verificación

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

return []

verificaPol :: IO Bool

verificaPol = $quickCheckAll

-- La verificación es

-- λ> verificaPol

-- === prop_polCero_es_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:157 ===

-- +++ OK, passed 1 test.

-- === prop_consPol_no_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:163 ===

-- +++ OK, passed 100 tests; 274 discarded.

-- === prop_consPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:169 ===

-- +++ OK, passed 100 tests.

-- === prop_grado from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:175 ===

-- +++ OK, passed 100 tests; 297 discarded.

-- === prop_coefLider from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:182 ===

-- +++ OK, passed 100 tests; 248 discarded.

-- === prop_restoPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDensa.hs:189 ===

-- +++ OK, passed 100 tests; 322 discarded.

-- True

2.4. Implementación de polinomios mediante listas dispersas

Representaremos un polinomio mediante una lista de pares (grado,coef),
ordenados en orden decreciente según el grado. Por ejemplo, el polinomio

   6x^4 -5x^2 + 4x -7

1	6x^4 -5x^2 + 4x -7

se representa por

   [(4,6),(2,-5),(1,4),(0,-7)]

1	[(4,6),(2,-5),(1,4),(0,-7)]

En la representación se supone que los primeros elementos de los pares forman una sucesión estrictamente decreciente y que los segundos elementos son distintos de cero.

La implementación se encuentra en el módulo PolRepDispersa.hs cuyo contenido es el siguiente:

{-# LANGUAGE TemplateHaskell #-}
{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.PolRepDispersa
  ( Polinomio,
    polCero,   -- Polinomio a
    esPolCero, -- Num a =>  Polinomio a -> Bool
    consPol,   -- Num a => Int -> a -> Polinomio a -> Polinomio a
    grado,     -- Polinomio a -> Int
    coefLider, -- Num a => Polinomio a -> a
    restoPol   -- Polinomio a -> Polinomio a
  ) where

import Test.QuickCheck

newtype Polinomio a = Pol [(Int,a)]
  deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por
-- ejemplo,
--    λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))
--    "3*x^4 + -5*x^2 + 3"
escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String
escribePol pol
  | esPolCero pol         = "0"
  | n == 0 && esPolCero p = show a
  | n == 0                = concat [show a, " + ", escribePol p]
  | n == 1 && esPolCero p = show a ++ "*x"
  | n == 1                = concat [show a, "*x + ", escribePol p]
  | a == 1 && esPolCero p = "x^" ++ show n
  | esPolCero p           = concat [show a, "*x^", show n]
  | a == 1                = concat ["x^", show n, " + ", escribePol p]
  | otherwise             = concat [show a, "*x^", show n, " + ", escribePol p]
  where n = grado pol
        a = coefLider pol
        p = restoPol pol

-- Procedimiento de escritura de polinomios.
instance (Num a, Show a, Eq a) => Show (Polinomio a) where
  show = escribePol

-- Ejemplos de polinomios con coeficientes enteros:
ejPol1, ejPol2, ejPol3 :: Polinomio Int
ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
ejPol3 = consPol 4 6 (consPol 1 2 polCero)

-- Comprobación de escritura:
--    > ejPol1
--    3*x^4 + -5*x^2 + 3
--    > ejPol2
--    x^5 + 5*x^2 + 4*x
--    > ejPol3
--    6*x^4 + 2*x

-- polCero es el polinomio cero. Por ejemplo,
--    λ> polCero
--    0
polCero :: Num a => Polinomio a
polCero = Pol []

-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,
--    esPolCero polCero  ==  True
--    esPolCero ejPol1   ==  False
esPolCero :: Num a => Polinomio a -> Bool
esPolCero (Pol []) = True
esPolCero _        = False

-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,
--    ejPol2               ==  x^5 + 5*x^2 + 4*x
--    consPol 3 0 ejPol2   ==  x^5 + 5*x^2 + 4*x
--    consPol 3 2 polCero  ==  2*x^3
--    consPol 6 7 ejPol2   ==  7*x^6 + x^5 + 5*x^2 + 4*x
--    consPol 4 7 ejPol2   ==  x^5 + 7*x^4 + 5*x^2 + 4*x
--    consPol 5 7 ejPol2   ==  8*x^5 + 5*x^2 + 4*x
consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a
consPol _ 0 p = p
consPol n b p@(Pol xs)
    | esPolCero p = Pol [(n,b)]
    | n > m       = Pol ((n,b):xs)
    | n < m       = consPol m c (consPol n b (Pol (tail xs)))
    | b+c == 0    = Pol (tail xs)
    | otherwise   = Pol ((n,b+c) : tail xs)
    where
      c = coefLider p
      m = grado p

-- (grado p) es el grado del polinomio p. Por ejemplo,
--    ejPol3        ==  6*x^4 + 2*x
--    grado ejPol3  ==  4
grado :: Polinomio a -> Int
grado (Pol [])        = 0
grado (Pol ((n,_):_)) = n

-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,
--    ejPol3            ==  6*x^4 + 2*x
--    coefLider ejPol3  ==  6
coefLider :: Num t => Polinomio t -> t
coefLider (Pol [])        = 0
coefLider (Pol ((_,b):_)) = b

-- (restoPol p) es el resto del polinomio p. Por ejemplo,
--    ejPol3           ==  6*x^4 + 2*x
--    restoPol ejPol3  ==  2*x
--    ejPol2           ==  x^5 + 5*x^2 + 4*x
--    restoPol ejPol2  ==  5*x^2 + 4*x
restoPol :: Num t => Polinomio t -> Polinomio t
restoPol (Pol [])     = polCero
restoPol (Pol [_])    = polCero
restoPol (Pol (_:xs)) = Pol xs

-- Generador de polinomios                                          --
-- =======================

-- genPolinomio es un generador de polinomios. Por ejemplo,
--    λ> sample (genPol 1)
--    7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10
--    -4*x^8 + 2*x
--    -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x
--    -9*x^9 + x^5 + -7
--    8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2
--    7*x^10 + 5*x^9 + -5
--    -8*x^10 + -7
--    -5*x
--    5*x^10 + 4*x^4 + -3
--    3*x^3 + -4
--    10*x
genPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)
genPol 0 = return polCero
genPol _ = do
  n <- choose (0,10)
  b <- arbitrary
  p <- genPol (div n 2)
  return (consPol n b p)

instance (Num a, Arbitrary a, Eq a) => Arbitrary (Polinomio a) where
  arbitrary = sized genPol

-- Propiedades de los polinomios
-- =============================

-- polCero es el polinomio cero.
prop_polCero_es_cero :: Bool
prop_polCero_es_cero =
  esPolCero polCero

-- Si n es mayor que el grado de p y b no es cero, entonces
-- (consPol n b p) es un polinomio distinto del cero.
prop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property
prop_consPol_no_cero n b p =
  n > grado p && b /= 0  ==>
  not (esPolCero (consPol n b p))

-- (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.
prop_consPol :: Polinomio Int -> Bool
prop_consPol p =
  consPol (grado p) (coefLider p) (restoPol p) == p

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el grado de (consPol n b p) es n.
prop_grado :: Int -> Int -> Polinomio Int -> Property
prop_grado n b p =
  n > grado p && b /= 0 ==>
  grado (consPol n b p) == n

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el coeficiente líder de (consPol n b p) es b.
prop_coefLider :: Int -> Int -> Polinomio Int -> Property
prop_coefLider n b p =
  n > grado p && b /= 0 ==>
  coefLider (consPol n b p) == b

-- Si n es mayor que el grado de p y b no es cero, entonces
-- el resto de (consPol n b p) es p.
prop_restoPol :: Int -> Int -> Polinomio Int -> Property
prop_restoPol n b p =
  n > grado p && b /= 0 ==>
  restoPol (consPol n b p) == p

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

return []

verificaPol :: IO Bool
verificaPol = $quickCheckAll

-- La verificación es
--    λ> verificaPol
--    === prop_polCero_es_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:156 ===
--    +++ OK, passed 1 test.
--
--    === prop_consPol_no_cero from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:162 ===
--    +++ OK, passed 100 tests; 264 discarded.
--
--    === prop_consPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:168 ===
--    +++ OK, passed 100 tests.
--
--    === prop_grado from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:174 ===
--    +++ OK, passed 100 tests; 266 discarded.
--
--    === prop_coefLider from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:181 ===
--    +++ OK, passed 100 tests; 251 discarded.
--
--    === prop_restoPol from /home/jalonso/alonso/estudio/Exercitium/Exercitium/src/TAD/PolRepDispersa.hs:188 ===
--    +++ OK, passed 100 tests; 254 discarded.
--
--    True

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

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

{-# LANGUAGE TemplateHaskell #-}

{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}

module TAD.PolRepDispersa

( Polinomio,

polCero, -- Polinomio a

esPolCero, -- Num a => Polinomio a -> Bool

consPol, -- Num a => Int -> a -> Polinomio a -> Polinomio a

grado, -- Polinomio a -> Int

coefLider, -- Num a => Polinomio a -> a

restoPol -- Polinomio a -> Polinomio a

) where

import Test.QuickCheck

newtype Polinomio a = Pol [(Int,a)]

deriving Eq

-- (escribePol p) es la cadena correspondiente al polinomio p. Por

-- ejemplo,

-- λ> escribePol (consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero)))

-- "3*x^4 + -5*x^2 + 3"

escribePol :: (Num a, Show a, Eq a) => Polinomio a -> String

escribePol pol

| esPolCero pol = "0"

| n == 0 && esPolCero p = show a

| n == 0 = concat [show a, " + ", escribePol p]

| n == 1 && esPolCero p = show a ++ "*x"

| n == 1 = concat [show a, "*x + ", escribePol p]

| a == 1 && esPolCero p = "x^" ++ show n

| esPolCero p = concat [show a, "*x^", show n]

| a == 1 = concat ["x^", show n, " + ", escribePol p]

| otherwise = concat [show a, "*x^", show n, " + ", escribePol p]

where n = grado pol

a = coefLider pol

p = restoPol pol

-- Procedimiento de escritura de polinomios.

instance (Num a, Show a, Eq a) => Show (Polinomio a) where

show = escribePol

-- Ejemplos de polinomios con coeficientes enteros:

ejPol1, ejPol2, ejPol3 :: Polinomio Int

ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))

ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))

ejPol3 = consPol 4 6 (consPol 1 2 polCero)

-- Comprobación de escritura:

-- > ejPol1

-- 3*x^4 + -5*x^2 + 3

-- > ejPol2

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

-- > ejPol3

-- 6*x^4 + 2*x

-- polCero es el polinomio cero. Por ejemplo,

-- λ> polCero

-- 0

polCero :: Num a => Polinomio a

polCero = Pol []

-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,

-- esPolCero polCero == True

-- esPolCero ejPol1 == False

esPolCero :: Num a => Polinomio a -> Bool

esPolCero (Pol []) = True

esPolCero _ = False

-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,

-- ejPol2 == x^5 + 5*x^2 + 4*x

-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x

-- consPol 3 2 polCero == 2*x^3

-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x

-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x

-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x

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

consPol _ 0 p = p

consPol n b p@(Pol xs)

| esPolCero p = Pol [(n,b)]

| n > m = Pol ((n,b):xs)

| n < m = consPol m c (consPol n b (Pol (tail xs)))

| b+c == 0 = Pol (tail xs)

| otherwise = Pol ((n,b+c) : tail xs)

where

c = coefLider p

m = grado p

-- (grado p) es el grado del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- grado ejPol3 == 4

grado :: Polinomio a -> Int

grado (Pol []) = 0

grado (Pol ((n,_):_)) = n

-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- coefLider ejPol3 == 6

coefLider :: Num t => Polinomio t -> t

coefLider (Pol []) = 0

coefLider (Pol ((_,b):_)) = b

-- (restoPol p) es el resto del polinomio p. Por ejemplo,

-- ejPol3 == 6*x^4 + 2*x

-- restoPol ejPol3 == 2*x

-- ejPol2 == x^5 + 5*x^2 + 4*x

-- restoPol ejPol2 == 5*x^2 + 4*x

restoPol :: Num t => Polinomio t -> Polinomio t

restoPol (Pol []) = polCero

restoPol (Pol [_]) = polCero

restoPol (Pol (_:xs)) = Pol xs

-- Generador de polinomios --

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

-- genPolinomio es un generador de polinomios. Por ejemplo,

-- λ> sample (genPol 1)

-- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10

-- -4*x^8 + 2*x

-- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x

-- -9*x^9 + x^5 + -7

-- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2

-- 7*x^10 + 5*x^9 + -5

-- -8*x^10 + -7

-- -5*x

-- 5*x^10 + 4*x^4 + -3

-- 3*x^3 + -4

-- 10*x

genPol :: (Num a, Arbitrary a, Eq a) => Int -> Gen (Polinomio a)

genPol 0 = return polCero

genPol _ = do

n <- choose (0,10)

b <- arbitrary

p <- genPol (div n 2)

return (consPol n b p)

instance (Num a, Arbitrary