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

3. Los polinomios en Python

3.1. El tipo abstracto de los polinomios en Python

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

__all__ = [
    'Polinomio',
    'polCero',
    'esPolCero',
    'consPol',
    'grado',
    'coefLider',
    'restoPol',
    'polinomioAleatorio'
]

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

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

__all__ = [

'Polinomio',

'polCero',

'esPolCero',

'consPol',

'grado',

'coefLider',

'restoPol',

'polinomioAleatorio'

]

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

grado, polCero, polinomioAleatorio, restoPol)

# from src.TAD.PolRepDispersa import (Polinomio, polCero, esPolCero,

# consPol, grado, coefLider,

# restoPol, polinomioAleatorio)

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

mediante listas densas y
mediante listas dispersas.

3.2. Implementación de los 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.

Se define la clase Polinomio con los siguientes métodos:

esPolCero() se verifica si es el polinomio cero.
consPol(n, b) es el polinomio obtenido añadiendo el térmiono bx^n
grado() es el grado del polinomio.
coefLider() es el coeficiente líder del polinomio.
restoPol() es el resto del polinomio.

Por ejemplo,

   >>> Polinomio()
   0
   >>> ejPol1 = Polinomio().consPol(0,3).consPol(2,-5).consPol(4,3)
   >>> ejPol1
   3*x^4 + -5*x^2 + 3
   >>> ejPol2 = Polinomio().consPol(1,4).consPol(2,5).consPol(5,1)
   >>> ejPol2
   x^5 + 5*x^2 + 4*x
   >>> ejPol3 = Polinomio().consPol(1,2).consPol(4,6)
   >>> ejPol3
   6*x^4 + 2*x
   >>> Polinomio().esPolCero()
   True
   >>> ejPol1.esPolCero()
   False
   >>> ejPol2
   x^5 + 5*x^2 + 4*x
   >>> ejPol2.consPol(3,0)
   x^5 + 5*x^2 + 4*x
   >>> Polinomio().consPol(3,2)
   2*x^3
   >>> ejPol2.consPol(6,7)
   7*x^6 + x^5 + 5*x^2 + 4*x
   >>> ejPol2.consPol(4,7)
   x^5 + 7*x^4 + 5*x^2 + 4*x
   >>> ejPol2.consPol(5,7)
   8*x^5 + 5*x^2 + 4*x
   >>> ejPol3
   6*x^4 + 2*x
   >>> ejPol3.grado()
   4
   >>> ejPol3.restoPol()
   2*x
   >>> ejPol2
   x^5 + 5*x^2 + 4*x
   >>> ejPol2.restoPol()
   5*x^2 + 4*x

>>> Polinomio()

>>> ejPol1 = Polinomio().consPol(0,3).consPol(2,-5).consPol(4,3)

>>> ejPol1

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

>>> ejPol2 = Polinomio().consPol(1,4).consPol(2,5).consPol(5,1)

>>> ejPol2

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

>>> ejPol3 = Polinomio().consPol(1,2).consPol(4,6)

>>> ejPol3

6*x^4 + 2*x

>>> Polinomio().esPolCero()

True

>>> ejPol1.esPolCero()

False

>>> ejPol2

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

>>> ejPol2.consPol(3,0)

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

>>> Polinomio().consPol(3,2)

2*x^3

>>> ejPol2.consPol(6,7)

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

>>> ejPol2.consPol(4,7)

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

>>> ejPol2.consPol(5,7)

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

>>> ejPol3

6*x^4 + 2*x

>>> ejPol3.grado()

>>> ejPol3.restoPol()

2*x

>>> ejPol2

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

>>> ejPol2.restoPol()

5*x^2 + 4*x

Además se definen las correspondientes funciones. Por ejemplo,

   >>> polCero()
   0
   >>> ejPol1a = consPol(4,3,consPol(2,-5,consPol(0,3,polCero())))
   >>> ejPol1a
   3*x^4 + -5*x^2 + 3
   >>> ejPol2a = consPol(5,1,consPol(2,5,consPol(1,4,polCero())))
   >>> ejPol2a
   x^5 + 5*x^2 + 4*x
   >>> ejPol3a = consPol(4,6,consPol(1,2,polCero()))
   >>> ejPol3a
   6*x^4 + 2*x
   >>> esPolCero(polCero())
   True
   >>> esPolCero(ejPol1a)
   False
   >>> ejPol2a
   x^5 + 5*x^2 + 4*x
   >>> consPol(3,9,ejPol2a)
   x^5 + 9*x^3 + 5*x^2 + 4*x
   >>> consPol(3,2,polCero())
   2*x^3
   >>> consPol(6,7,ejPol2a)
   7*x^6 + x^5 + 5*x^2 + 4*x
   >>> consPol(4,7,ejPol2a)
   x^5 + 7*x^4 + 5*x^2 + 4*x
   >>> consPol(5,7,ejPol2a)
   8*x^5 + 5*x^2 + 4*x
   >>> ejPol3a
   6*x^4 + 2*x
   >>> grado(ejPol3a)
   4
   >>> restoPol(ejPol3a)
   2*x
   >>> ejPol2a
   x^5 + 5*x^2 + 4*x
   >>> restoPol(ejPol2a)
   5*x^2 + 4*x

>>> polCero()

>>> ejPol1a = consPol(4,3,consPol(2,-5,consPol(0,3,polCero())))

>>> ejPol1a

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

>>> ejPol2a = consPol(5,1,consPol(2,5,consPol(1,4,polCero())))

>>> ejPol2a

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

>>> ejPol3a = consPol(4,6,consPol(1,2,polCero()))

>>> ejPol3a

6*x^4 + 2*x

>>> esPolCero(polCero())

True

>>> esPolCero(ejPol1a)

False

>>> ejPol2a

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

>>> consPol(3,9,ejPol2a)

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

>>> consPol(3,2,polCero())

2*x^3

>>> consPol(6,7,ejPol2a)

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

>>> consPol(4,7,ejPol2a)

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

>>> consPol(5,7,ejPol2a)

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

>>> ejPol3a

6*x^4 + 2*x

>>> grado(ejPol3a)

>>> restoPol(ejPol3a)

2*x

>>> ejPol2a

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

>>> restoPol(ejPol2a)

5*x^2 + 4*x

Finalmente, se define un generador aleatorio de polinomios y se comprueba que los polinomios cumplen las propiedades de su especificación.

La implementación se encuentra en el módulo PolRepDensa.py en el que se define la clase Conj con los siguientes métodos:

from __future__ import annotations

__all__ = [
    'Polinomio',
    'polCero',
    'esPolCero',
    'consPol',
    'grado',
    'coefLider',
    'restoPol',
    'polinomioAleatorio'
]

from dataclasses import dataclass, field
from itertools import dropwhile
from typing import Generic, TypeVar

from hypothesis import assume, given
from hypothesis import strategies as st

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

# Clase de los polinomios mediante listas densas
# ==============================================

@dataclass
class Polinomio(Generic[A]):
    _coeficientes: list[A] = field(default_factory=list)

    def esPolCero(self) -> bool:
        return not self._coeficientes

    def grado(self) -> int:
        if self.esPolCero():
            return 0
        return len(self._coeficientes) - 1

    def coefLider(self) -> A:
        if self.esPolCero():
            return 0
        return self._coeficientes[0]

    def restoPol(self) -> Polinomio[A]:
        xs = self._coeficientes
        if len(xs) <= 1:
            return Polinomio([])
        if xs[1] == 0:
            return Polinomio(list(dropwhile(lambda x: x == 0, xs[2:])))
        return Polinomio(xs[1:])

    def consPol(self, n: int, b: A) -> Polinomio[A]:
        m = self.grado()
        c = self.coefLider()
        xs = self._coeficientes
        if b == 0:
            return self
        if self.esPolCero():
            return Polinomio([b] + ([0] * n))
        if n > m:
            return Polinomio([b] + ([0] * (n-m-1)) + xs)
        if n < m:
            return self.restoPol().consPol(n, b).consPol(m, c)
        if b + c == 0:
            return Polinomio(list(dropwhile(lambda x: x == 0, xs[1:])))
        return Polinomio([b + c] + xs[1:])

    def __repr__(self) -> str:
        n = self.grado()
        a = self.coefLider()
        p = self.restoPol()
        if self.esPolCero():
            return "0"
        if n == 0 and p.esPolCero():
            return str(a)
        if n == 0:
            return str(a) + " + " + str(p)
        if n == 1 and p.esPolCero():
            return str(a) + "*x"
        if n == 1:
            return str(a) + "*x + " + str(p)
        if a == 1 and p.esPolCero():
            return "x^" + str(n)
        if p.esPolCero():
            return str(a) + "*x^" + str(n)
        if a == 1:
            return "x^" + str(n) + " + " + str(p)
        return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio
# ============================

def polCero() -> Polinomio[A]:
    return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:
    return p.esPolCero()

def grado(p: Polinomio[A]) -> int:
    return p.grado()

def coefLider(p: Polinomio[A]) -> A:
    return p.coefLider()

def restoPol(p: Polinomio[A]) -> Polinomio[A]:
    return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:
    return p.consPol(n, b)

# Generador de polinomios
# =======================

# normal(xs) es la lista obtenida eliminando los ceros iniciales de
# xs. Por ejmplo,
#    >>> normal([0,0,5,0])
#    [5, 0]
#    >>> normal([0,0,0,0])
#    []
def normal(xs: list[A]) -> list[A]:
    return list(dropwhile(lambda x: x == 0, xs))

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,
#    >>> polinomioAleatorio().example()
#    9*x^6 + -7*x^5 + 7*x^3 + x^2 + 7
#    >>> polinomioAleatorio().example()
#    -3*x^7 + 8*x^6 + 2*x^5 + x^4 + -1*x^3 + -6*x^2 + 8*x + -6
#    >>> polinomioAleatorio().example()
#    x^2 + 7*x + -1
def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:
    return st.lists(st.integers(min_value=-9, max_value=9), max_size=10)\
             .map(lambda xs: normal(xs))\
             .map(Polinomio)

# Comprobación de las propiedades de los polinomios
# =================================================

# Las propiedades son
def test_esPolCero1() -> None:
    assert esPolCero(polCero())

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())
def test_consPol(p: Polinomio[int]) -> None:
    assume(not esPolCero(p))
    assert consPol(grado(p), coefLider(p), restoPol(p)) == p

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_grado(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert restoPol(consPol(n, b, p)) == p

# La comprobación es
#    > poetry run pytest -v PolRepDensa.py
#
#    PolRepDensa.py::test_esPolCero1 PASSED
#    PolRepDensa.py::test_esPolCero2 PASSED
#    PolRepDensa.py::test_consPol PASSED
#    PolRepDensa.py::test_grado PASSED
#    PolRepDensa.py::test_coefLider PASSED
#    PolRepDensa.py::test_restoPol PASSED
#
#    === 6 passed in 1.64s ===

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

from __future__ import annotations

__all__ = [

'Polinomio',

'polCero',

'esPolCero',

'consPol',

'grado',

'coefLider',

'restoPol',

'polinomioAleatorio'

]

from dataclasses import dataclass, field

from itertools import dropwhile

from typing import Generic, TypeVar

from hypothesis import assume, given

from hypothesis import strategies as st

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

# Clase de los polinomios mediante listas densas

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

@dataclass

class Polinomio(Generic[A]):

_coeficientes: list[A] = field(default_factory=list)

def esPolCero(self) -> bool:

return not self._coeficientes

def grado(self) -> int:

if self.esPolCero():

return 0

return len(self._coeficientes) - 1

def coefLider(self) -> A:

if self.esPolCero():

return 0

return self._coeficientes[0]

def restoPol(self) -> Polinomio[A]:

xs = self._coeficientes

if len(xs) <= 1:

return Polinomio([])

if xs[1] == 0:

return Polinomio(list(dropwhile(lambda x: x == 0, xs[2:])))

return Polinomio(xs[1:])

def consPol(self, n: int, b: A) -> Polinomio[A]:

m = self.grado()

c = self.coefLider()

xs = self._coeficientes

if b == 0:

return self

if self.esPolCero():

return Polinomio([b] + ([0] * n))

if n > m:

return Polinomio([b] + ([0] * (n-m-1)) + xs)

if n < m:

return self.restoPol().consPol(n, b).consPol(m, c)

if b + c == 0:

return Polinomio(list(dropwhile(lambda x: x == 0, xs[1:])))

return Polinomio([b + c] + xs[1:])

def __repr__(self) -> str:

n = self.grado()

a = self.coefLider()

p = self.restoPol()

if self.esPolCero():

return "0"

if n == 0 and p.esPolCero():

return str(a)

if n == 0:

return str(a) + " + " + str(p)

if n == 1 and p.esPolCero():

return str(a) + "*x"

if n == 1:

return str(a) + "*x + " + str(p)

if a == 1 and p.esPolCero():

return "x^" + str(n)

if p.esPolCero():

return str(a) + "*x^" + str(n)

if a == 1:

return "x^" + str(n) + " + " + str(p)

return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio

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

def polCero() -> Polinomio[A]:

return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:

return p.esPolCero()

def grado(p: Polinomio[A]) -> int:

return p.grado()

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

return p.coefLider()

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

return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:

return p.consPol(n, b)

# Generador de polinomios

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

# normal(xs) es la lista obtenida eliminando los ceros iniciales de

# xs. Por ejmplo,

# >>> normal([0,0,5,0])

# [5, 0]

# >>> normal([0,0,0,0])

# []

def normal(xs: list[A]) -> list[A]:

return list(dropwhile(lambda x: x == 0, xs))

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,

# >>> polinomioAleatorio().example()

# 9*x^6 + -7*x^5 + 7*x^3 + x^2 + 7

# >>> polinomioAleatorio().example()

# -3*x^7 + 8*x^6 + 2*x^5 + x^4 + -1*x^3 + -6*x^2 + 8*x + -6

# >>> polinomioAleatorio().example()

# x^2 + 7*x + -1

def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:

return st.lists(st.integers(min_value=-9, max_value=9), max_size=10)\

.map(lambda xs: normal(xs))\

.map(Polinomio)

# Comprobación de las propiedades de los polinomios

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

# Las propiedades son

def test_esPolCero1() -> None:

assert esPolCero(polCero())

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())

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

assume(not esPolCero(p))

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

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_grado(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert restoPol(consPol(n, b, p)) == p

# La comprobación es

# > poetry run pytest -v PolRepDensa.py

# PolRepDensa.py::test_esPolCero1 PASSED

# PolRepDensa.py::test_esPolCero2 PASSED

# PolRepDensa.py::test_consPol PASSED

# PolRepDensa.py::test_grado PASSED

# PolRepDensa.py::test_coefLider PASSED

# PolRepDensa.py::test_restoPol PASSED

# === 6 passed in 1.64s ===

3.3. Implementación de los 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.py cuyo contenido es

from __future__ import annotations

__all__ = [
    'Polinomio',
    'polCero',
    'esPolCero',
    'consPol',
    'grado',
    'coefLider',
    'restoPol',
    'polinomioAleatorio'
]

from dataclasses import dataclass, field
from typing import Generic, TypeVar

from hypothesis import assume, given
from hypothesis import strategies as st

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

# Clase de los polinomios mediante listas densas
# ==============================================

@dataclass
class Polinomio(Generic[A]):
    _terminos: list[tuple[int, A]] = field(default_factory=list)

    def esPolCero(self) -> bool:
        return not self._terminos

    def grado(self) -> int:
        if self.esPolCero():
            return 0
        return self._terminos[0][0]

    def coefLider(self) -> A:
        if self.esPolCero():
            return 0
        return self._terminos[0][1]

    def restoPol(self) -> Polinomio[A]:
        xs = self._terminos
        if len(xs) <= 1:
            return Polinomio([])
        return Polinomio(xs[1:])

    def consPol(self, n: int, b: A) -> Polinomio[A]:
        m = self.grado()
        c = self.coefLider()
        xs = self._terminos
        if b == 0:
            return self
        if self.esPolCero():
            return Polinomio([(n, b)])
        if n > m:
            return Polinomio([(n, b)] + xs)
        if n < m:
            return Polinomio(xs[1:]).consPol(n, b).consPol(m, c)
        if b + c == 0:
            return Polinomio(xs[1:])
        return Polinomio([(n, b + c)] + xs[1:])

    def __repr__(self) -> str:
        n = self.grado()
        a = self.coefLider()
        p = self.restoPol()
        if self.esPolCero():
            return "0"
        if n == 0 and p.esPolCero():
            return str(a)
        if n == 0:
            return str(a) + " + " + str(p)
        if n == 1 and p.esPolCero():
            return str(a) + "*x"
        if n == 1:
            return str(a) + "*x + " + str(p)
        if a == 1 and p.esPolCero():
            return "x^" + str(n)
        if p.esPolCero():
            return str(a) + "*x^" + str(n)
        if a == 1:
            return "x^" + str(n) + " + " + str(p)
        return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio
# ============================

def polCero() -> Polinomio[A]:
    return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:
    return p.esPolCero()

def grado(p: Polinomio[A]) -> int:
    return p.grado()

def coefLider(p: Polinomio[A]) -> A:
    return p.coefLider()

def restoPol(p: Polinomio[A]) -> Polinomio[A]:
    return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:
    return p.consPol(n, b)

# Generador de polinomios
# =======================

# normal(ps) es la representación dispersa de un polinomio.
def normal(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]

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,
#    >>> polinomioAleatorio().example()
#    -4*x^8 + -5*x^7 + -4*x^6 + -4*x^5 + -8*x^3
#    >>> polinomioAleatorio().example()
#    -7*x^9 + -8*x^6 + -8*x^3 + 2*x^2 + -1*x + 4
def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:
    return st.lists(st.tuples(st.integers(min_value=0, max_value=9),
                              st.integers(min_value=-9, max_value=9)))\
             .map(lambda ps: normal(ps))\
             .map(Polinomio)

# Comprobación de las propiedades de los polinomios
# =================================================

# Las propiedades son
def test_esPolCero1() -> None:
    assert esPolCero(polCero())

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())
def test_consPol(p: Polinomio[int]) -> None:
    assume(not esPolCero(p))
    assert consPol(grado(p), coefLider(p), restoPol(p)) == p

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_grado(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),
       n=st.integers(min_value=0, max_value=10),
       b=st.integers())
def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:
    assume(n > grado(p) and b != 0)
    assert restoPol(consPol(n, b, p)) == p

# La comprobación es
#    > poetry run pytest -v PolRepDispersa.py
#
#    PolRepDispersa.py::test_esPolCero1 PASSED
#    PolRepDispersa.py::test_esPolCero2 PASSED
#    PolRepDispersa.py::test_consPol PASSED
#    PolRepDispersa.py::test_grado PASSED
#    PolRepDispersa.py::test_coefLider PASSED
#    PolRepDispersa.py::test_restoPol PASSED
#
#    === 6 passed in 1.74s ===

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

from __future__ import annotations

__all__ = [

'Polinomio',

'polCero',

'esPolCero',

'consPol',

'grado',

'coefLider',

'restoPol',

'polinomioAleatorio'

]

from dataclasses import dataclass, field

from typing import Generic, TypeVar

from hypothesis import assume, given

from hypothesis import strategies as st

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

# Clase de los polinomios mediante listas densas

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

@dataclass

class Polinomio(Generic[A]):

_terminos: list[tuple[int, A]] = field(default_factory=list)

def esPolCero(self) -> bool:

return not self._terminos

def grado(self) -> int:

if self.esPolCero():

return 0

return self._terminos[0][0]

def coefLider(self) -> A:

if self.esPolCero():

return 0

return self._terminos[0][1]

def restoPol(self) -> Polinomio[A]:

xs = self._terminos

if len(xs) <= 1:

return Polinomio([])

return Polinomio(xs[1:])

def consPol(self, n: int, b: A) -> Polinomio[A]:

m = self.grado()

c = self.coefLider()

xs = self._terminos

if b == 0:

return self

if self.esPolCero():

return Polinomio([(n, b)])

if n > m:

return Polinomio([(n, b)] + xs)

if n < m:

return Polinomio(xs[1:]).consPol(n, b).consPol(m, c)

if b + c == 0:

return Polinomio(xs[1:])

return Polinomio([(n, b + c)] + xs[1:])

def __repr__(self) -> str:

n = self.grado()

a = self.coefLider()

p = self.restoPol()

if self.esPolCero():

return "0"

if n == 0 and p.esPolCero():

return str(a)

if n == 0:

return str(a) + " + " + str(p)

if n == 1 and p.esPolCero():

return str(a) + "*x"

if n == 1:

return str(a) + "*x + " + str(p)

if a == 1 and p.esPolCero():

return "x^" + str(n)

if p.esPolCero():

return str(a) + "*x^" + str(n)

if a == 1:

return "x^" + str(n) + " + " + str(p)

return str(a) + "*x^" + str(n) + " + " + str(p)

# Funciones del tipo polinomio

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

def polCero() -> Polinomio[A]:

return Polinomio([])

def esPolCero(p: Polinomio[A]) -> bool:

return p.esPolCero()

def grado(p: Polinomio[A]) -> int:

return p.grado()

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

return p.coefLider()

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

return p.restoPol()

def consPol(n: int, b: A, p: Polinomio[A]) -> Polinomio[A]:

return p.consPol(n, b)

# Generador de polinomios

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

# normal(ps) es la representación dispersa de un polinomio.

def normal(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]

# polinomioAleatorio() genera polinomios aleatorios. Por ejemplo,

# >>> polinomioAleatorio().example()

# -4*x^8 + -5*x^7 + -4*x^6 + -4*x^5 + -8*x^3

# >>> polinomioAleatorio().example()

# -7*x^9 + -8*x^6 + -8*x^3 + 2*x^2 + -1*x + 4

def polinomioAleatorio() -> st.SearchStrategy[Polinomio[int]]:

return st.lists(st.tuples(st.integers(min_value=0, max_value=9),

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

.map(lambda ps: normal(ps))\

.map(Polinomio)

# Comprobación de las propiedades de los polinomios

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

# Las propiedades son

def test_esPolCero1() -> None:

assert esPolCero(polCero())

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_esPolCero2(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert not esPolCero(consPol(n, b, p))

@given(p=polinomioAleatorio())

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

assume(not esPolCero(p))

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

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_grado(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert grado(consPol(n, b, p)) == n

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_coefLider(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert coefLider(consPol(n, b, p)) == b

@given(p=polinomioAleatorio(),

n=st.integers(min_value=0, max_value=10),

b=st.integers())

def test_restoPol(p: Polinomio[int], n: int, b: int) -> None:

assume(n > grado(p) and b != 0)

assert restoPol(consPol(n, b, p)) == p

# La comprobación es

# > poetry run pytest -v PolRepDispersa.py

# PolRepDispersa.py::test_esPolCero1 PASSED

# PolRepDispersa.py::test_esPolCero2 PASSED

# PolRepDispersa.py::test_consPol PASSED

# PolRepDispersa.py::test_grado PASSED

# PolRepDispersa.py::test_coefLider PASSED

# PolRepDispersa.py::test_restoPol PASSED

# === 6 passed in 1.74s ===

Clausura transitiva

PorJosé A. Alonso 14-abril-202314-abril-2023

Usando el tipo de las relaciones binarias, definir la función

   clausuraTransitiva :: Eq a => Rel a -> Rel a

1	clausuraTransitiva :: Eq a => Rel a -> Rel a

tal que clausuraTransitiva r es la clausura transitiva de r; es decir, la menor relación transitiva que contiene a r. Por ejemplo,

   λ> clausuraTransitiva (R ([1..6],[(1,2),(2,5),(5,6)]))
   R ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)])

1 2	λ> clausuraTransitiva (R ([1..6],[(1,2),(2,5),(5,6)])) R ([1,2,3,4,5,6],[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)])

Comprobar con QuickCheck que clausuraTransitiva es transitiva.

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Relaciones_transitivas (transitiva)
import Data.List (union)
import Test.QuickCheck

--  1ª solución
--  ===========

clausuraTransitiva :: Ord a => Rel a -> Rel a
clausuraTransitiva (R (u,g)) = R (u, aux g)
  where
    aux u' | cerradoTr u' = u'
           | otherwise    = aux (u' `union` comp u' u')
    cerradoTr r       = subconjunto (comp r r) r
    comp r s          = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']
    subconjunto xs ys = all (`elem` ys) xs

-- 2ª solución
-- ===========

clausuraTransitiva2 :: Ord a => Rel a -> Rel a
clausuraTransitiva2 (R (u,g)) =
  R (u, until cerradoTr (\r -> r `union` comp r r) g)
  where
    cerradoTr r       = subconjunto (comp r r) r
    comp r s          = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']
    subconjunto xs ys = all (`elem` ys) xs


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

-- La propiedad es
prop_clausuraTransitiva :: Rel Int -> Bool
prop_clausuraTransitiva r =
  clausuraTransitiva r == clausuraTransitiva2 r

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

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

-- La propiedad es
prop_clausuraTransitivaEsTransitiva :: Rel Int -> Bool
prop_clausuraTransitivaEsTransitiva r =
  transitiva (clausuraTransitiva r)

-- La función transitiva está definida en el ejercicio
-- "Relaciones transitivas" que se encuentra en
-- https://bit.ly/42WRPJv

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

import Relaciones_binarias (Rel(R))

import Relaciones_transitivas (transitiva)

import Data.List (union)

import Test.QuickCheck

-- 1ª solución

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

clausuraTransitiva :: Ord a => Rel a -> Rel a

clausuraTransitiva (R (u,g)) = R (u, aux g)

where

aux u' | cerradoTr u' = u'

| otherwise = aux (u' `union` comp u' u')

cerradoTr r = subconjunto (comp r r) r

comp r s = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']

subconjunto xs ys = all (`elem` ys) xs

-- 2ª solución

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

clausuraTransitiva2 :: Ord a => Rel a -> Rel a

clausuraTransitiva2 (R (u,g)) =

R (u, until cerradoTr (\r -> r `union` comp r r) g)

where

cerradoTr r = subconjunto (comp r r) r

comp r s = [(x,z) | (x,y) <- r, (y',z) <- s, y == y']

subconjunto xs ys = all (`elem` ys) xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_clausuraTransitiva :: Rel Int -> Bool

prop_clausuraTransitiva r =

clausuraTransitiva r == clausuraTransitiva2 r

-- La comprobación es

-- λ> quickCheck prop_clausuraTransitiva

-- +++ OK, passed 100 tests.

-- Propiedad

-- =========

-- La propiedad es

prop_clausuraTransitivaEsTransitiva :: Rel Int -> Bool

prop_clausuraTransitivaEsTransitiva r =

transitiva (clausuraTransitiva r)

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

-- "Relaciones transitivas" que se encuentra en

-- https://bit.ly/42WRPJv

-- La comprobación es

-- λ> quickCheck prop_clausuraTransitivaEsTransitiva

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria
from src.Relaciones_transitivas import transitiva

A = TypeVar('A')

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

def clausuraTransitiva(r: Rel[A]) -> Rel[A]:
    (u, g) = r

    def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:
        return set(xs) <= set(ys)

    def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})

    def cerradoTr(r: list[tuple[A, A]]) -> bool:
        return subconjunto(comp(r, r), r)

    def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return xs + [y for y in ys if y not in xs]

    def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:
        if cerradoTr(u1):
            return u1
        return aux(union(u1, comp(u1, u1)))

    return (u, aux(g))

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

def clausuraTransitiva2(r: Rel[A]) -> Rel[A]:
    (u, g) = r

    def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:
        return set(xs) <= set(ys)

    def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})

    def cerradoTr(r: list[tuple[A, A]]) -> bool:
        return subconjunto(comp(r, r), r)

    def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:
        return xs + [y for y in ys if y not in xs]

    def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:
        if cerradoTr(u1):
            return u1
        return aux(union(u1, comp(u1, u1)))

    g1: list[tuple[A, A]] = g
    while not cerradoTr(g1):
        g1 = union(g1, comp(g1, g1))
    return (u, g1)

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

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_clausuraTransitiva(n: int) -> None:
    r = relacionArbitraria(n)
    assert clausuraTransitiva(r) == clausuraTransitiva2(r)

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

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_cla(n: int) -> None:
    r = relacionArbitraria(n)
    assert transitiva(clausuraTransitiva(r))

# La función transitiva está definida en el ejercicio
# "Relaciones transitivas" que se encuentra en
# https://bit.ly/42WRPJv

# La comprobación es
#    > poetry run pytest -q Clausura_transitiva.py
#    2 passed in 0.16s

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

from src.Relaciones_transitivas import transitiva

A = TypeVar('A')

# 1ª solución

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

def clausuraTransitiva(r: Rel[A]) -> Rel[A]:

(u, g) = r

def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:

return set(xs) <= set(ys)

def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:

return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})

def cerradoTr(r: list[tuple[A, A]]) -> bool:

return subconjunto(comp(r, r), r)

def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:

return xs + [y for y in ys if y not in xs]

def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:

if cerradoTr(u1):

return u1

return aux(union(u1, comp(u1, u1)))

return (u, aux(g))

# 2ª solución

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

def clausuraTransitiva2(r: Rel[A]) -> Rel[A]:

(u, g) = r

def subconjunto(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> bool:

return set(xs) <= set(ys)

def comp(r: list[tuple[A, A]], s: list[tuple[A, A]]) -> list[tuple[A, A]]:

return list({(x, z) for (x, y) in r for (y1, z) in s if y == y1})

def cerradoTr(r: list[tuple[A, A]]) -> bool:

return subconjunto(comp(r, r), r)

def union(xs: list[tuple[A, A]], ys: list[tuple[A, A]]) -> list[tuple[A, A]]:

return xs + [y for y in ys if y not in xs]

def aux(u1: list[tuple[A, A]]) -> list[tuple[A, A]]:

if cerradoTr(u1):

return u1

return aux(union(u1, comp(u1, u1)))

g1: list[tuple[A, A]] = g

while not cerradoTr(g1):

g1 = union(g1, comp(g1, g1))

return (u, g1)

# Comprobación de equivalencia

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

# La propiedad es

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

def test_clausuraTransitiva(n: int) -> None:

r = relacionArbitraria(n)

assert clausuraTransitiva(r) == clausuraTransitiva2(r)

# Propiedad

# =========

# La propiedad es

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

def test_cla(n: int) -> None:

r = relacionArbitraria(n)

assert transitiva(clausuraTransitiva(r))

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

# "Relaciones transitivas" que se encuentra en

# https://bit.ly/42WRPJv

# La comprobación es

# > poetry run pytest -q Clausura_transitiva.py

# 2 passed in 0.16s

Clausura simétrica

PorJosé A. Alonso 13-abril-202330-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   clausuraSimetrica :: Eq a => Rel a -> Rel a

1	clausuraSimetrica :: Eq a => Rel a -> Rel a

tal que clausuraSimetrica r es la clausura simétrica de r; es decir, la menor relación simétrica que contiene a r. Por ejemplo,

   λ> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)]))
   R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)])

1 2	λ> clausuraSimetrica (R ([1,3,5],[(1,1),(3,1),(1,5)])) R ([1,3,5],[(1,1),(3,1),(1,5),(1,3),(5,1)])

Comprobar con QuickCheck que clausuraSimetrica es simétrica.

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Data.List (union)
import Relaciones_simetricas (simetrica)
import Test.QuickCheck

clausuraSimetrica :: Eq a => Rel a -> Rel a
clausuraSimetrica (R (u,g)) =
  R (u, g `union` [(y,x) | (x,y) <- g])

-- La propiedad es
prop_ClausuraSimetrica :: Rel Int -> Bool
prop_ClausuraSimetrica r =
  simetrica (clausuraSimetrica r)

-- La función simetrica está definida en el ejercicio
-- "Relaciones simétricas" que se encuentra en
-- https://bit.ly/3zlO2rH

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

import Relaciones_binarias (Rel(R))

import Data.List (union)

import Relaciones_simetricas (simetrica)

import Test.QuickCheck

clausuraSimetrica :: Eq a => Rel a -> Rel a

clausuraSimetrica (R (u,g)) =

R (u, g `union` [(y,x) | (x,y) <- g])

-- La propiedad es

prop_ClausuraSimetrica :: Rel Int -> Bool

prop_ClausuraSimetrica r =

simetrica (clausuraSimetrica r)

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

-- "Relaciones simétricas" que se encuentra en

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

-- La comprobación es

-- λ> quickCheck prop_ClausuraSimetrica

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria
from src.Relaciones_simetricas import simetrica

A = TypeVar('A')

def clausuraSimetrica(r: Rel[A]) -> Rel[A]:
    (u, g) = r
    return (u, list(set(g) | {(y, x) for (x,y) in g}))

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

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_irreflexiva(n: int) -> None:
    r = relacionArbitraria(n)
    assert simetrica(clausuraSimetrica(r))

# La función simetrica está definida en el ejercicio
# "Relaciones simétricas" que se encuentra en
# https://bit.ly/3zlO2rH

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

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

from src.Relaciones_simetricas import simetrica

A = TypeVar('A')

def clausuraSimetrica(r: Rel[A]) -> Rel[A]:

(u, g) = r

return (u, list(set(g) | {(y, x) for (x,y) in g}))

# Comprobación de equivalencia

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

# La propiedad es

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

def test_irreflexiva(n: int) -> None:

r = relacionArbitraria(n)

assert simetrica(clausuraSimetrica(r))

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

# "Relaciones simétricas" que se encuentra en

# https://bit.ly/3zlO2rH

# La comprobación es

# > poetry run pytest -q Clausura_simetrica.py

# 1 passed in 0.12s

Clausura reflexiva

PorJosé A. Alonso 12-abril-202329-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   clausuraReflexiva :: Eq a => Rel a -> Rel a

1	clausuraReflexiva :: Eq a => Rel a -> Rel a

tal que clausuraReflexiva r es la clausura reflexiva de r; es decir, la menor relación reflexiva que contiene a r. Por ejemplo,

   λ> clausuraReflexiva (R ([1,3],[(1,1),(3,1)]))
   R ([1,3],[(1,1),(3,1),(3,3)])

1 2	λ> clausuraReflexiva (R ([1,3],[(1,1),(3,1)])) R ([1,3],[(1,1),(3,1),(3,3)])

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Data.List (union)
import Test.QuickCheck (quickCheck)

clausuraReflexiva :: Eq a => Rel a -> Rel a
clausuraReflexiva (R (u,g)) =
  R (u, g `union` [(x,x) | x <- u])

import Relaciones_binarias (Rel(R))

import Data.List (union)

import Test.QuickCheck (quickCheck)

clausuraReflexiva :: Eq a => Rel a -> Rel a

clausuraReflexiva (R (u,g)) =

R (u, g `union` [(x,x) | x <- u])

Soluciones en Python

from typing import TypeVar

from src.Relaciones_binarias import Rel

A = TypeVar('A')

def clausuraReflexiva(r: Rel[A]) -> Rel[A]:
    (u, g) = r
    return (u, list(set(g) | {(x, x) for x in u}))

from typing import TypeVar

from src.Relaciones_binarias import Rel

A = TypeVar('A')

def clausuraReflexiva(r: Rel[A]) -> Rel[A]:

(u, g) = r

return (u, list(set(g) | {(x, x) for x in u}))

Relaciones totales

PorJosé A. Alonso 11-abril-202323-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   total :: Eq a => Rel a -> Bool

1	total :: Eq a => Rel a -> Bool

tal que total r se verifica si la relación r es total; es decir, si para cualquier par x, y de elementos del universo de r, se tiene que x está relacionado con y o y está relacionado con x. Por ejemplo,

   total (R ([1,3],[(1,1),(3,1),(3,3)]))  ==  True
   total (R ([1,3],[(1,1),(3,1)]))        ==  False
   total (R ([1,3],[(1,1),(3,3)]))        ==  False

total (R ([1,3],[(1,1),(3,1),(3,3)])) == True

total (R ([1,3],[(1,1),(3,1)])) == False

total (R ([1,3],[(1,1),(3,3)])) == False

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck (quickCheck)

-- 1ª solución
-- ===========

total :: Eq a => Rel a -> Bool
total (R (u,g)) =
  and [(x,y) `elem` g || (y,x) `elem` g | x <- u, y <- u]

-- 2ª solución
-- ===========

total2 :: Eq a => Rel a -> Bool
total2 (R (u,g)) =
  all (relacionados g) (producto u u)

-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,
--    λ> producto [2,5] [1,4,6]
--    [(2,1),(2,4),(2,6),(5,1),(5,4),(5,6)]
producto :: [a] -> [a] -> [(a,a)]
producto xs ys =
  [(x,y) | x <- xs, y <- ys]

-- (relacionados g (x,y)) se verifica si los elementos x e y están
-- relacionados por la relación de grafo g. Por ejemplo,
--    relacionados [(2,3),(3,1)] (2,3)  ==  True
--    relacionados [(2,3),(3,1)] (3,2)  ==  True
--    relacionados [(2,3),(3,1)] (1,2)  ==  False
relacionados :: Eq a => [(a,a)] -> (a,a) -> Bool
relacionados g (x,y) =
  (x,y) `elem` g || (y,x) `elem` g

-- 3ª solución
-- ===========

total3 :: Eq a => Rel a -> Bool
total3 (R (u,g)) = aux1 u
  where aux1 []       = True
        aux1 (x:xs)   = aux2 x u && aux1 xs
        aux2 _ []     = True
        aux2 x (y:ys) = relacionados g (x,y) && aux2 x ys

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

-- La propiedad es
prop_total :: Rel Int -> Bool
prop_total r =
  all (== total r)
      [total2 r,
       total3 r]

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

import Relaciones_binarias (Rel(R))

import Test.QuickCheck (quickCheck)

-- 1ª solución

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

total :: Eq a => Rel a -> Bool

total (R (u,g)) =

and [(x,y) `elem` g || (y,x) `elem` g | x <- u, y <- u]

-- 2ª solución

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

total2 :: Eq a => Rel a -> Bool

total2 (R (u,g)) =

all (relacionados g) (producto u u)

-- (producto xs ys) es el producto cartesiano de xs e ys. Por ejemplo,

-- λ> producto [2,5] [1,4,6]

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

producto :: [a] -> [a] -> [(a,a)]

producto xs ys =

[(x,y) | x <- xs, y <- ys]

-- (relacionados g (x,y)) se verifica si los elementos x e y están

-- relacionados por la relación de grafo g. Por ejemplo,

-- relacionados [(2,3),(3,1)] (2,3) == True

-- relacionados [(2,3),(3,1)] (3,2) == True

-- relacionados [(2,3),(3,1)] (1,2) == False

relacionados :: Eq a => [(a,a)] -> (a,a) -> Bool

relacionados g (x,y) =

(x,y) `elem` g || (y,x) `elem` g

-- 3ª solución

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

total3 :: Eq a => Rel a -> Bool

total3 (R (u,g)) = aux1 u

where aux1 [] = True

aux1 (x:xs) = aux2 x u && aux1 xs

aux2 _ [] = True

aux2 x (y:ys) = relacionados g (x,y) && aux2 x ys

-- Comprobación de equivalencia

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

-- La propiedad es

prop_total :: Rel Int -> Bool

prop_total r =

all (== total r)

[total2 r,

total3 r]

-- La comprobación es

-- λ> quickCheck prop_total

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

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

def total(r: Rel[A]) -> bool:
    (u, g) = r
    return all(((x, y) in g or (y, x) in g for x in u for y in u))

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

# producto(xs, ys) es el producto cartesiano de xs e ys. Por ejemplo,
#    >>> producto([2, 5], [1, 4, 6])
#    [(2, 1), (2, 4), (2, 6), (5, 1), (5, 4), (5, 6)]
def producto(xs: list[A], ys: list[A]) -> list[tuple[A,A]]:
    return [(x, y) for x in xs for y in ys]

# relacionados(g, (x, y)) se verifica si los elementos x e y están
# relacionados por la relación de grafo g. Por ejemplo,
#    relacionados([(2, 3), (3, 1)], (2, 3))  ==  True
#    relacionados([(2, 3), (3, 1)], (3, 2))  ==  True
#    relacionados([(2, 3), (3, 1)], (1, 2))  ==  False
def relacionados(g: list[tuple[A,A]], p: tuple[A,A]) -> bool:
    (x, y) = p
    return (x, y) in g or (y, x) in g

def total2(r: Rel[A]) -> bool:
    (u, g) = r
    return all(relacionados(g, p) for p in producto(u, u))

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

def total3(r: Rel[A]) -> bool:
    u, g = r
    return all(relacionados(g, (x, y)) for x in u for y in u)

# 4ª solución
# ===========

def total4(r: Rel[A]) -> bool:
    (u, g) = r
    def aux2(x: A, ys: list[A]) -> bool:
        if not ys:
            return True
        return relacionados(g, (x, ys[0])) and aux2(x, ys[1:])

    def aux1(xs: list[A]) -> bool:
        if not xs:
            return True
        return aux2(xs[0], u) and aux1(xs[1:])

    return aux1(u)

# 5ª solución
# ===========

def total5(r: Rel[A]) -> bool:
    (u, g) = r
    for x in u:
        for y in u:
            if not relacionados(g, (x, y)):
                return False
    return True

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

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_total(n: int) -> None:
    r = relacionArbitraria(n)
    res = total(r)
    assert total2(r) == res
    assert total3(r) == res
    assert total4(r) == res
    assert total5(r) == res

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

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

# 1ª solución

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

def total(r: Rel[A]) -> bool:

(u, g) = r

return all(((x, y) in g or (y, x) in g for x in u for y in u))

# 2ª solución

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

# producto(xs, ys) es el producto cartesiano de xs e ys. Por ejemplo,

# >>> producto([2, 5], [1, 4, 6])

# [(2, 1), (2, 4), (2, 6), (5, 1), (5, 4), (5, 6)]

def producto(xs: list[A], ys: list[A]) -> list[tuple[A,A]]:

return [(x, y) for x in xs for y in ys]

# relacionados(g, (x, y)) se verifica si los elementos x e y están

# relacionados por la relación de grafo g. Por ejemplo,

# relacionados([(2, 3), (3, 1)], (2, 3)) == True

# relacionados([(2, 3), (3, 1)], (3, 2)) == True

# relacionados([(2, 3), (3, 1)], (1, 2)) == False

def relacionados(g: list[tuple[A,A]], p: tuple[A,A]) -> bool:

(x, y) = p

return (x, y) in g or (y, x) in g

def total2(r: Rel[A]) -> bool:

(u, g) = r

return all(relacionados(g, p) for p in producto(u, u))

# 3ª solución

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

def total3(r: Rel[A]) -> bool:

u, g = r

return all(relacionados(g, (x, y)) for x in u for y in u)

# 4ª solución

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

def total4(r: Rel[A]) -> bool:

(u, g) = r

def aux2(x: A, ys: list[A]) -> bool:

if not ys:

return True

return relacionados(g, (x, ys[0])) and aux2(x, ys[1:])

def aux1(xs: list[A]) -> bool:

if not xs:

return True

return aux2(xs[0], u) and aux1(xs[1:])

return aux1(u)

# 5ª solución

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

def total5(r: Rel[A]) -> bool:

(u, g) = r

for x in u:

for y in u:

if not relacionados(g, (x, y)):

return False

return True

# Comprobación de equivalencia

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

# La propiedad es

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

def test_total(n: int) -> None:

r = relacionArbitraria(n)

res = total(r)

assert total2(r) == res

assert total3(r) == res

assert total4(r) == res

assert total5(r) == res

# La comprobación es

# > poetry run pytest -q Relaciones_totales.py

# 1 passed in 0.11s

Relaciones antisimétricas

PorJosé A. Alonso 10-abril-202322-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   antisimetrica :: Eq a => Rel a -> Bool

1	antisimetrica :: Eq a => Rel a -> Bool

tal que antisimetrica r se verifica si la relación r es antisimétrica; es decir, si (x,y) e (y,x) están relacionado, entonces x=y. Por ejemplo,

   antisimetrica (R ([1,2],[(1,2)]))        ==  True
   antisimetrica (R ([1,2],[(1,2),(2,1)]))  ==  False
   antisimetrica (R ([1,2],[(1,1),(2,1)]))  ==  True

antisimetrica (R ([1,2],[(1,2)])) == True

antisimetrica (R ([1,2],[(1,2),(2,1)])) == False

antisimetrica (R ([1,2],[(1,1),(2,1)])) == True

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck

-- 1ª solución
-- ===========

antisimetrica :: Eq a => Rel a -> Bool
antisimetrica (R (_,g)) =
  null [(x,y) | (x,y) <- g, x /= y, (y,x) `elem` g]

-- 2ª solución
-- ===========

antisimetrica2 :: Eq a => Rel a -> Bool
antisimetrica2 (R (_,g)) =
  and [(y,x) `notElem` g | (x,y) <- g, x /= y]


-- 3ª solución
-- ===========

antisimetrica3 :: Eq a => Rel a -> Bool
antisimetrica3 (R (_,g)) =
  all (\(x, y) -> (y,x) `notElem` g || x == y) g


-- 4ª solución
-- ===========

antisimetrica4 :: Eq a => Rel a -> Bool
antisimetrica4 (R (u,g)) =
  and [((x,y) `elem` g && (y,x) `elem` g) --> (x == y)
       | x <- u, y <- u]
  where p --> q = not p || q

-- 5ª solución
-- ===========

antisimetrica5 :: Eq a => Rel a -> Bool
antisimetrica5 (R (_,g)) = aux g
  where aux []         = True
        aux ((x,y):g') = ((y,x) `notElem` g || x == y) && aux g'

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

-- La propiedad es
prop_antisimetrica :: Rel Int -> Bool
prop_antisimetrica r =
  all (== antisimetrica r)
      [antisimetrica2 r,
       antisimetrica3 r,
       antisimetrica4 r,
       antisimetrica5 r]

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

import Relaciones_binarias (Rel(R))

import Test.QuickCheck

-- 1ª solución

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

antisimetrica :: Eq a => Rel a -> Bool

antisimetrica (R (_,g)) =

null [(x,y) | (x,y) <- g, x /= y, (y,x) `elem` g]

-- 2ª solución

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

antisimetrica2 :: Eq a => Rel a -> Bool

antisimetrica2 (R (_,g)) =

and [(y,x) `notElem` g | (x,y) <- g, x /= y]

-- 3ª solución

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

antisimetrica3 :: Eq a => Rel a -> Bool

antisimetrica3 (R (_,g)) =

all (\(x, y) -> (y,x) `notElem` g || x == y) g

-- 4ª solución

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

antisimetrica4 :: Eq a => Rel a -> Bool

antisimetrica4 (R (u,g)) =

and [((x,y) `elem` g && (y,x) `elem` g) --> (x == y)

| x <- u, y <- u]

where p --> q = not p || q

-- 5ª solución

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

antisimetrica5 :: Eq a => Rel a -> Bool

antisimetrica5 (R (_,g)) = aux g

where aux [] = True

aux ((x,y):g') = ((y,x) `notElem` g || x == y) && aux g'

-- Comprobación de equivalencia

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

-- La propiedad es

prop_antisimetrica :: Rel Int -> Bool

prop_antisimetrica r =

all (== antisimetrica r)

[antisimetrica2 r,

antisimetrica3 r,

antisimetrica4 r,

antisimetrica5 r]

-- La comprobación es

-- λ> quickCheck prop_antisimetrica

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

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

def antisimetrica(r: Rel[A]) -> bool:
    (u, g) = r
    return [(x, y) for (x, y) in g if x != y and (y, x) in g] == []

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

def antisimetrica2(r: Rel[A]) -> bool:
    (u, g) = r
    return all(((y, x) not in g for (x, y) in g if x != y))

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

def antisimetrica3(r: Rel[A]) -> bool:
    (u, g) = r
    return all ((not ((x, y) in g and (y, x) in g) or x == y
                 for x in u for y in u))

# 4ª solución
# ===========

def antisimetrica4(r: Rel[A]) -> bool:
    (u, g) = r
    def aux(xys: list[tuple[A, A]]) -> bool:
        if not xys:
            return True
        (x, y) = xys[0]
        return ((y, x) not in g or x == y) and aux(xys[1:])

    return aux(g)

# 5ª solución
# ===========

def antisimetrica5(r: Rel[A]) -> bool:
    (u, g) = r
    for (x, y) in g:
        if (y, x) in g and x != y:
            return False
    return True

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

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_antisimetrica(n: int) -> None:
    r = relacionArbitraria(n)
    res = antisimetrica(r)
    assert antisimetrica2(r) == res
    assert antisimetrica3(r) == res
    assert antisimetrica4(r) == res
    assert antisimetrica5(r) == res

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

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

# 1ª solución

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

def antisimetrica(r: Rel[A]) -> bool:

(u, g) = r

return [(x, y) for (x, y) in g if x != y and (y, x) in g] == []

# 2ª solución

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

def antisimetrica2(r: Rel[A]) -> bool:

(u, g) = r

return all(((y, x) not in g for (x, y) in g if x != y))

# 3ª solución

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

def antisimetrica3(r: Rel[A]) -> bool:

(u, g) = r

return all ((not ((x, y) in g and (y, x) in g) or x == y

for x in u for y in u))

# 4ª solución

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

def antisimetrica4(r: Rel[A]) -> bool:

(u, g) = r

def aux(xys: list[tuple[A, A]]) -> bool:

if not xys:

return True

(x, y) = xys[0]

return ((y, x) not in g or x == y) and aux(xys[1:])

return aux(g)

# 5ª solución

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

def antisimetrica5(r: Rel[A]) -> bool:

(u, g) = r

for (x, y) in g:

if (y, x) in g and x != y:

return False

return True

# Comprobación de equivalencia

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

# La propiedad es

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

def test_antisimetrica(n: int) -> None:

r = relacionArbitraria(n)

res = antisimetrica(r)

assert antisimetrica2(r) == res

assert antisimetrica3(r) == res

assert antisimetrica4(r) == res

assert antisimetrica5(r) == res

# La comprobación es

# > poetry run pytest -q Relaciones_antisimetricas.py

# 1 passed in 0.13s

Relaciones irreflexivas

PorJosé A. Alonso 7-abril-202318-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   irreflexiva :: Eq a => Rel a -> Bool

1	irreflexiva :: Eq a => Rel a -> Bool

tal que irreflexiva r se verifica si la relación r es irreflexiva; es decir, si ningún elemento de su universo está relacionado con él mismo. Por ejemplo,

   irreflexiva (R ([1,2,3],[(1,2),(2,1),(2,3)]))  ==  True
   irreflexiva (R ([1,2,3],[(1,2),(2,1),(3,3)]))  ==  False

1 2	irreflexiva (R ([1,2,3],[(1,2),(2,1),(2,3)])) == True irreflexiva (R ([1,2,3],[(1,2),(2,1),(3,3)])) == False

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck

-- 1ª solución
-- ===========

irreflexiva :: Eq a => Rel a -> Bool
irreflexiva (R (u,g)) = and [(x,x) `notElem` g | x <- u]

-- 2ª solución
-- ===========

irreflexiva2 :: Eq a => Rel a -> Bool
irreflexiva2 (R(u,g)) = all (\x -> (x,x) `notElem` g) u

-- 3ª solución
-- ===========

irreflexiva3 :: Eq a => Rel a -> Bool
irreflexiva3 (R(u,g)) = aux u
  where aux []     = True
        aux (x:xs) = (x,x) `notElem` g && aux xs


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

-- La propiedad es
prop_irreflexiva :: Rel Int -> Bool
prop_irreflexiva r =
  all (== irreflexiva r)
      [irreflexiva2 r,
       irreflexiva3 r]

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

import Relaciones_binarias (Rel(R))

import Test.QuickCheck

-- 1ª solución

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

irreflexiva :: Eq a => Rel a -> Bool

irreflexiva (R (u,g)) = and [(x,x) `notElem` g | x <- u]

-- 2ª solución

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

irreflexiva2 :: Eq a => Rel a -> Bool

irreflexiva2 (R(u,g)) = all (\x -> (x,x) `notElem` g) u

-- 3ª solución

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

irreflexiva3 :: Eq a => Rel a -> Bool

irreflexiva3 (R(u,g)) = aux u

where aux [] = True

aux (x:xs) = (x,x) `notElem` g && aux xs

-- Comprobación de equivalencia

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

-- La propiedad es

prop_irreflexiva :: Rel Int -> Bool

prop_irreflexiva r =

all (== irreflexiva r)

[irreflexiva2 r,

irreflexiva3 r]

-- La comprobación es

-- λ> quickCheck prop_irreflexiva

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

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

def irreflexiva(r: Rel[A]) -> bool:
    (u, g) = r
    return all(((x, x) not in g for x in u))

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

def irreflexiva2(r: Rel[A]) -> bool:
    (u, g) = r
    def aux(xs: list[A]) -> bool:
        if not xs:
            return True
        return (xs[0], xs[0]) not in g and aux(xs[1:])

    return aux(u)

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

def irreflexiva3(r: Rel[A]) -> bool:
    (u, g) = r
    for x in u:
        if (x, x) in g:
            return False
    return True

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

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_irreflexiva(n: int) -> None:
    r = relacionArbitraria(n)
    res = irreflexiva(r)
    assert irreflexiva2(r) == res
    assert irreflexiva3(r) == res

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

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

# 1ª solución

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

def irreflexiva(r: Rel[A]) -> bool:

(u, g) = r

return all(((x, x) not in g for x in u))

# 2ª solución

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

def irreflexiva2(r: Rel[A]) -> bool:

(u, g) = r

def aux(xs: list[A]) -> bool:

if not xs:

return True

return (xs[0], xs[0]) not in g and aux(xs[1:])

return aux(u)

# 3ª solución

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

def irreflexiva3(r: Rel[A]) -> bool:

(u, g) = r

for x in u:

if (x, x) in g:

return False

return True

# Comprobación de equivalencia

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

# La propiedad es

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

def test_irreflexiva(n: int) -> None:

r = relacionArbitraria(n)

res = irreflexiva(r)

assert irreflexiva2(r) == res

assert irreflexiva3(r) == res

# La comprobación es

# > poetry run pytest -q Relaciones_irreflexivas.py

# 1 passed in 0.12s

Relaciones de equivalencia

PorJosé A. Alonso 6-abril-202318-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   esEquivalencia :: Ord a => Rel a -> Bool

1	esEquivalencia :: Ord a => Rel a -> Bool

tal que esEquivalencia r se verifica si la relación r es de equivalencia. Por ejemplo,

   λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))
   True
   λ> esEquivalencia (R ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))
   False
   λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,3),(5,5)]))
   False

λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))

True

λ> esEquivalencia (R ([1,2,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)]))

False

λ> esEquivalencia (R ([1,3,5],[(1,1),(1,3),(3,3),(5,5)]))

False

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Relaciones_reflexivas (reflexiva)
import Relaciones_simetricas (simetrica)
import Relaciones_transitivas (transitiva)

esEquivalencia :: Ord a => Rel a -> Bool
esEquivalencia r = reflexiva r && simetrica r && transitiva r

import Relaciones_binarias (Rel(R))

import Relaciones_reflexivas (reflexiva)

import Relaciones_simetricas (simetrica)

import Relaciones_transitivas (transitiva)

esEquivalencia :: Ord a => Rel a -> Bool

esEquivalencia r = reflexiva r && simetrica r && transitiva r

Soluciones en Python

from typing import TypeVar

from src.Relaciones_binarias import Rel, relacionArbitraria
from src.Relaciones_reflexivas import reflexiva
from src.Relaciones_simetricas import simetrica
from src.Relaciones_transitivas import transitiva

A = TypeVar('A')

def esEquivalencia(r: Rel[A]) -> bool:
    return reflexiva(r) and simetrica(r) and transitiva(r)

from typing import TypeVar

from src.Relaciones_binarias import Rel, relacionArbitraria

from src.Relaciones_reflexivas import reflexiva

from src.Relaciones_simetricas import simetrica

from src.Relaciones_transitivas import transitiva

A = TypeVar('A')

def esEquivalencia(r: Rel[A]) -> bool:

return reflexiva(r) and simetrica(r) and transitiva(r)

Relaciones transitivas

PorJosé A. Alonso 5-abril-202313-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   transitiva :: Ord a => Rel a -> Bool

1	transitiva :: Ord a => Rel a -> Bool

tal que transitiva r se verifica si la relación r es transitiva. Por ejemplo,

   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) == True
   transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(5,5)]))       == False

1 2	transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(3,3),(5,5)])) == True transitiva (R ([1,3,5],[(1,1),(1,3),(3,1),(5,5)])) == False

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Reconocimiento_de_subconjunto (subconjunto)
import Universo_y_grafo_de_una_relacion_binaria (grafo)
import Composicion_de_relaciones_binarias_v2 (composicion)
import Test.QuickCheck

-- 1ª solución
-- ===========

transitiva1 :: Ord a => Rel a -> Bool
transitiva1 r@(R (_,g)) = subconjunto (grafo (composicion r r)) g

-- La función subconjunto está definida en el ejercicio
-- "Reconocimiento de subconjunto" que se encuentra en
-- https://bit.ly/427Tyeq
--
-- La función grafo está definida en el ejercicio
-- "Universo y grafo de una relación binaria" que se encuentra en
-- https://bit.ly/3J35mpC
--
-- La función composición está definida en el ejercicio
-- "Composición de relaciones binarias" que se encuentra en
-- https://bit.ly/3JyJrs7

-- 2ª solución
-- ===========

transitiva2 :: Ord a => Rel a -> Bool
transitiva2 (R (_,g)) = aux g
  where
    aux [] = True
    aux ((x,y):g') = and [(x,z) `elem` g | (u,z) <- g, u == y] && aux g'

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

-- La propiedad es
prop_transitiva :: Rel Int -> Bool
prop_transitiva r =
  transitiva1 r == transitiva2 r

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

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

-- La comparación es
--    λ> transitiva1 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))
--    False
--    (3.15 secs, 898,932,776 bytes)
--    λ> transitiva2 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))
--    False
--    (0.01 secs, 1,396,720 bytes)
--
--    λ> transitiva1 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))
--    True
--    (2.71 secs, 852,578,456 bytes)
--    λ> transitiva2 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))
--    True
--    (9.13 secs, 777,080,288 bytes)

-- En lo sucesivo, usaremos la 1ª definición
transitiva :: Ord a => Rel a -> Bool
transitiva = transitiva1

import Relaciones_binarias (Rel(R))

import Reconocimiento_de_subconjunto (subconjunto)

import Universo_y_grafo_de_una_relacion_binaria (grafo)

import Composicion_de_relaciones_binarias_v2 (composicion)

import Test.QuickCheck

-- 1ª solución

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

transitiva1 :: Ord a => Rel a -> Bool

transitiva1 r@(R (_,g)) = subconjunto (grafo (composicion r r)) g

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

-- "Reconocimiento de subconjunto" que se encuentra en

-- https://bit.ly/427Tyeq

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

-- "Universo y grafo de una relación binaria" que se encuentra en

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

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

-- "Composición de relaciones binarias" que se encuentra en

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

-- 2ª solución

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

transitiva2 :: Ord a => Rel a -> Bool

transitiva2 (R (_,g)) = aux g

where

aux [] = True

aux ((x,y):g') = and [(x,z) `elem` g | (u,z) <- g, u == y] && aux g'

-- Comprobación de equivalencia

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

-- La propiedad es

prop_transitiva :: Rel Int -> Bool

prop_transitiva r =

transitiva1 r == transitiva2 r

-- La comprobación es

-- λ> quickCheck prop_transitiva

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> transitiva1 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))

-- False

-- (3.15 secs, 898,932,776 bytes)

-- λ> transitiva2 (R ([1..4001],[(x,x+1) | x <- [1..4000]]))

-- False

-- (0.01 secs, 1,396,720 bytes)

-- λ> transitiva1 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))

-- True

-- (2.71 secs, 852,578,456 bytes)

-- λ> transitiva2 (R ([1..60], [(x,y) | x <- [1..60], y <- [1..60]]))

-- True

-- (9.13 secs, 777,080,288 bytes)

-- En lo sucesivo, usaremos la 1ª definición

transitiva :: Ord a => Rel a -> Bool

transitiva = transitiva1

Soluciones en Python

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

from hypothesis import given
from hypothesis import strategies as st

from src.Composicion_de_relaciones_binarias_v2 import composicion
from src.Reconocimiento_de_subconjunto import subconjunto
from src.Relaciones_binarias import Rel, relacionArbitraria
from src.Universo_y_grafo_de_una_relacion_binaria import grafo

setrecursionlimit(10**6)

A = TypeVar('A')

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

def transitiva1(r: Rel[A]) -> bool:
    g = grafo(r)
    return subconjunto(grafo(composicion(r, r)), g)

# La función subconjunto está definida en el ejercicio
# "Reconocimiento de subconjunto" que se encuentra en
# https://bit.ly/427Tyeq
#
# La función grafo está definida en el ejercicio
# "Universo y grafo de una relación binaria" que se encuentra en
# https://bit.ly/3J35mpC
#
# La función composición está definida en el ejercicio
# "Composición de relaciones binarias" que se encuentra en
# https://bit.ly/3JyJrs7

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

def transitiva2(r: Rel[A]) -> bool:
    g = grafo(r)
    def aux(g1: list[tuple[A,A]]) -> bool:
        if not g1:
            return True
        (x, y) = g1[0]
        return all(((x, z) in g for (u,z) in g if u == y)) and aux(g1[1:])

    return aux(g)

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

def transitiva3(r: Rel[A]) -> bool:
    g = grafo(r)
    g1 = list(g)
    for (x, y) in g1:
        if not all(((x, z) in g for (u,z) in g if u == y)):
            return False
    return True


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

# La propiedad es
@given(st.integers(min_value=0, max_value=10))
def test_simetrica(n: int) -> None:
    r = relacionArbitraria(n)
    res = transitiva1(r)
    assert transitiva2(r) == res
    assert transitiva3(r) == res

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

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

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

# La comparación es
#    >>> u1 = range(6001)
#    >>> g1 = [(x, x+1) for x in range(6000)]
#    >>> tiempo("transitiva1((u1, g1))")
#    1.04 segundos
#    >>> tiempo("transitiva2((u1, g1))")
#    0.00 segundos
#    >>> tiempo("transitiva3((u1, g1))")
#    0.00 segundos
#
#    >>> u2 = range(60)
#    >>> g2 = [(x, y) for x in u2 for y in u2]
#    >>> tiempo("transitiva1((u2, g2))")
#    0.42 segundos
#    >>> tiempo("transitiva2((u2, g2))")
#    5.24 segundos
#    >>> tiempo("transitiva3((u2, g2))")
#    4.83 segundos

# En lo sucesivo usaremos la 1ª definición
transitiva = transitiva1

100

101

102

103

104

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Composicion_de_relaciones_binarias_v2 import composicion

from src.Reconocimiento_de_subconjunto import subconjunto

from src.Relaciones_binarias import Rel, relacionArbitraria

from src.Universo_y_grafo_de_una_relacion_binaria import grafo

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

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

def transitiva1(r: Rel[A]) -> bool:

g = grafo(r)

return subconjunto(grafo(composicion(r, r)), g)

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

# "Reconocimiento de subconjunto" que se encuentra en

# https://bit.ly/427Tyeq

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

# "Universo y grafo de una relación binaria" que se encuentra en

# https://bit.ly/3J35mpC

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

# "Composición de relaciones binarias" que se encuentra en

# https://bit.ly/3JyJrs7

# 2ª solución

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

def transitiva2(r: Rel[A]) -> bool:

g = grafo(r)

def aux(g1: list[tuple[A,A]]) -> bool:

if not g1:

return True

(x, y) = g1[0]

return all(((x, z) in g for (u,z) in g if u == y)) and aux(g1[1:])

return aux(g)

# 3ª solución

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

def transitiva3(r: Rel[A]) -> bool:

g = grafo(r)

g1 = list(g)

for (x, y) in g1:

if not all(((x, z) in g for (u,z) in g if u == y)):

return False

return True

# Comprobación de equivalencia

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

# La propiedad es

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

def test_simetrica(n: int) -> None:

r = relacionArbitraria(n)

res = transitiva1(r)

assert transitiva2(r) == res

assert transitiva3(r) == res

# La comprobación es

# > poetry run pytest -q Relaciones_transitivas.py

# 1 passed in 0.12s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> u1 = range(6001)

# >>> g1 = [(x, x+1) for x in range(6000)]

# >>> tiempo("transitiva1((u1, g1))")

# 1.04 segundos

# >>> tiempo("transitiva2((u1, g1))")

# 0.00 segundos

# >>> tiempo("transitiva3((u1, g1))")

# 0.00 segundos

# >>> u2 = range(60)

# >>> g2 = [(x, y) for x in u2 for y in u2]

# >>> tiempo("transitiva1((u2, g2))")

# 0.42 segundos

# >>> tiempo("transitiva2((u2, g2))")

# 5.24 segundos

# >>> tiempo("transitiva3((u2, g2))")

# 4.83 segundos

# En lo sucesivo usaremos la 1ª definición

transitiva = transitiva1

Reconocimiento de subconjunto

PorJosé A. Alonso 4-abril-202312-marzo-2023

Definir la función

   subconjunto :: Ord a => [a] -> [a] -> Bool

1	subconjunto :: Ord a => [a] -> [a] -> Bool

tal que subconjunto xs ys se verifica si xs es un subconjunto de ys. Por ejemplo,

   subconjunto [3,2,3] [2,5,3,5]  ==  True
   subconjunto [3,2,3] [2,5,6,5]  ==  False

1 2	subconjunto [3,2,3] [2,5,3,5] == True subconjunto [3,2,3] [2,5,6,5] == False

Soluciones

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

Soluciones en Haskell

module Reconocimiento_de_subconjunto where

import Data.List (nub, sort)
import Data.Set (fromList, isSubsetOf)
import Test.QuickCheck

-- 1ª solución
-- ===========

subconjunto1 :: Ord a => [a] -> [a] -> Bool
subconjunto1 xs ys =
  [x | x <- xs, x `elem` ys] == xs

-- 2ª solución
-- ===========

subconjunto2 :: Ord a => [a] -> [a] -> Bool
subconjunto2 []     _  = True
subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys

-- 3ª solución
-- ===========

subconjunto3 :: Ord a => [a] -> [a] -> Bool
subconjunto3 xs ys =
  all (`elem` ys) xs

-- 4ª solución
-- ===========

subconjunto4 :: Ord a => [a] -> [a] -> Bool
subconjunto4 xs ys =
  fromList xs `isSubsetOf` fromList ys

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

-- La propiedad es
prop_subconjunto :: [Int] -> [Int] -> Bool
prop_subconjunto xs ys =
  all (== subconjunto1 xs ys)
      [subconjunto2 xs ys,
       subconjunto3 xs ys,
       subconjunto4 xs ys]

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

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

-- La comparación es
--    λ> subconjunto1 [1..2*10^4] [1..2*10^4]
--    True
--    (1.81 secs, 5,992,448 bytes)
--    λ> subconjunto2 [1..2*10^4] [1..2*10^4]
--    True
--    (1.83 secs, 6,952,200 bytes)
--    λ> subconjunto3 [1..2*10^4] [1..2*10^4]
--    True
--    (1.75 secs, 4,712,304 bytes)
--    λ> subconjunto4 [1..2*10^4] [1..2*10^4]
--    True
--    (0.04 secs, 6,312,056 bytes)

-- En lo sucesivo, usaremos la 4ª definición
subconjunto :: Ord a => [a] -> [a] -> Bool
subconjunto = subconjunto4

module Reconocimiento_de_subconjunto where

import Data.List (nub, sort)

import Data.Set (fromList, isSubsetOf)

import Test.QuickCheck

-- 1ª solución

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

subconjunto1 :: Ord a => [a] -> [a] -> Bool

subconjunto1 xs ys =

[x | x <- xs, x `elem` ys] == xs

-- 2ª solución

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

subconjunto2 :: Ord a => [a] -> [a] -> Bool

subconjunto2 [] _ = True

subconjunto2 (x:xs) ys = x `elem` ys && subconjunto2 xs ys

-- 3ª solución

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

subconjunto3 :: Ord a => [a] -> [a] -> Bool

subconjunto3 xs ys =

all (`elem` ys) xs

-- 4ª solución

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

subconjunto4 :: Ord a => [a] -> [a] -> Bool

subconjunto4 xs ys =

fromList xs `isSubsetOf` fromList ys

-- Comprobación de equivalencia

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

-- La propiedad es

prop_subconjunto :: [Int] -> [Int] -> Bool

prop_subconjunto xs ys =

all (== subconjunto1 xs ys)

[subconjunto2 xs ys,

subconjunto3 xs ys,

subconjunto4 xs ys]

-- La comprobación es

-- λ> quickCheck prop_subconjunto

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> subconjunto1 [1..2*10^4] [1..2*10^4]

-- True

-- (1.81 secs, 5,992,448 bytes)

-- λ> subconjunto2 [1..2*10^4] [1..2*10^4]

-- True

-- (1.83 secs, 6,952,200 bytes)

-- λ> subconjunto3 [1..2*10^4] [1..2*10^4]

-- True

-- (1.75 secs, 4,712,304 bytes)

-- λ> subconjunto4 [1..2*10^4] [1..2*10^4]

-- True

-- (0.04 secs, 6,312,056 bytes)

-- En lo sucesivo, usaremos la 4ª definición

subconjunto :: Ord a => [a] -> [a] -> Bool

subconjunto = subconjunto4

Soluciones en Python

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

from hypothesis import given
from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

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

def subconjunto1(xs: list[A], ys: list[A]) -> bool:
    return [x for x in xs if x in ys] == xs

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

def subconjunto2(xs: list[A], ys: list[A]) -> bool:
    if not xs:
        return True
    return xs[0] in ys and subconjunto2(xs[1:], ys)

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

def subconjunto3(xs: list[A], ys: list[A]) -> bool:
    return all(elem in ys for elem in xs)

# 4ª solución
# ===========

def subconjunto4(xs: list[A], ys: list[A]) -> bool:
    return set(xs) <= set(ys)

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

# La propiedad es
@given(st.lists(st.integers()),
       st.lists(st.integers()))
def test_filtraAplica(xs: list[int], ys: list[int]) -> None:
    r = subconjunto1(xs, ys)
    assert subconjunto2(xs, ys) == r
    assert subconjunto3(xs, ys) == r
    assert subconjunto4(xs, ys) == r

# La comprobación es
#    src> poetry run pytest -q Reconocimiento_de_subconjunto.py
#    1 passed in 0.31s

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

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

# La comparación es
#    >>> xs = list(range(2*10**4))
#    >>> tiempo("subconjunto1(xs, xs)")
#    1.15 segundos
#    >>> tiempo("subconjunto2(xs, xs)")
#    2.27 segundos
#    >>> tiempo("subconjunto3(xs, xs)")
#    1.14 segundos
#    >>> tiempo("subconjunto4(xs, xs)")
#    0.00 segundos

# En lo sucesivo usaremos la cuarta definición
subconjunto = subconjunto4

from sys import setrecursionlimit

from timeit import Timer, default_timer

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

setrecursionlimit(10**6)

A = TypeVar('A')

# 1ª solución

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

def subconjunto1(xs: list[A], ys: list[A]) -> bool:

return [x for x in xs if x in ys] == xs

# 2ª solución

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

def subconjunto2(xs: list[A], ys: list[A]) -> bool:

if not xs:

return True

return xs[0] in ys and subconjunto2(xs[1:], ys)

# 3ª solución

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

def subconjunto3(xs: list[A], ys: list[A]) -> bool:

return all(elem in ys for elem in xs)

# 4ª solución

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

def subconjunto4(xs: list[A], ys: list[A]) -> bool:

return set(xs) <= set(ys)

# Comprobación de equivalencia

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

# La propiedad es

@given(st.lists(st.integers()),

st.lists(st.integers()))

def test_filtraAplica(xs: list[int], ys: list[int]) -> None:

r = subconjunto1(xs, ys)

assert subconjunto2(xs, ys) == r

assert subconjunto3(xs, ys) == r

assert subconjunto4(xs, ys) == r

# La comprobación es

# src> poetry run pytest -q Reconocimiento_de_subconjunto.py

# 1 passed in 0.31s

# Comparación de eficiencia

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

def tiempo(e: str) -> None:

"""Tiempo (en segundos) de evaluar la expresión e."""

t = Timer(e, "", default_timer, globals()).timeit(1)

print(f"{t:0.2f} segundos")

# La comparación es

# >>> xs = list(range(2*10**4))

# >>> tiempo("subconjunto1(xs, xs)")

# 1.15 segundos

# >>> tiempo("subconjunto2(xs, xs)")

# 2.27 segundos

# >>> tiempo("subconjunto3(xs, xs)")

# 1.14 segundos

# >>> tiempo("subconjunto4(xs, xs)")

# 0.00 segundos

# En lo sucesivo usaremos la cuarta definición

subconjunto = subconjunto4

Composición de relaciones binarias

PorJosé A. Alonso 3-abril-202311-marzo-2023

Usando el tipo de las relaciones binarias, definir la función

   composicion :: Eq a => Rel a -> Rel a -> Rel a

1	composicion :: Eq a => Rel a -> Rel a -> Rel a

tal que composicion r s es la composición de las relaciones r y s. Por ejemplo,

   λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)]))
   R ([1,2],[(1,1),(2,1)])

1 2	λ> composicion (R ([1,2],[(1,2),(2,2)])) (R ([1,2],[(2,1)])) R ([1,2],[(1,1),(2,1)])

Soluciones

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

Soluciones en Haskell

import Relaciones_binarias (Rel(R))
import Test.QuickCheck

-- 1ª solución
-- ===========

composicion :: Eq a => Rel a -> Rel a -> Rel a
composicion (R (u1,g1)) (R (_,g2)) =
  R (u1,[(x,z) | (x,y) <- g1, (y',z) <- g2, y == y'])

-- 2ª solución
-- ===========

composicion2 :: Eq a => Rel a -> Rel a -> Rel a
composicion2 (R (u1,g1)) (R (_,g2)) =
  R (u1, aux g1)
  where aux [] = []
        aux ((x,y):g1') = [(x,z) | (y',z) <- g2, y == y'] ++ aux g1'

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

-- La propiedad es
prop_composicion :: Rel Int -> Rel Int -> Bool
prop_composicion r1 r2 =
  composicion r1 r2 == composicion2 r1 r2

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

import Relaciones_binarias (Rel(R))

import Test.QuickCheck

-- 1ª solución

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

composicion :: Eq a => Rel a -> Rel a -> Rel a

composicion (R (u1,g1)) (R (_,g2)) =

R (u1,[(x,z) | (x,y) <- g1, (y',z) <- g2, y == y'])

-- 2ª solución

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

composicion2 :: Eq a => Rel a -> Rel a -> Rel a

composicion2 (R (u1,g1)) (R (_,g2)) =

R (u1, aux g1)

where aux [] = []

aux ((x,y):g1') = [(x,z) | (y',z) <- g2, y == y'] ++ aux g1'

-- Comprobación de equivalencia

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

-- La propiedad es

prop_composicion :: Rel Int -> Rel Int -> Bool

prop_composicion r1 r2 =

composicion r1 r2 == composicion2 r1 r2

-- La comprobación es

-- λ> quickCheck prop_composicion

-- +++ OK, passed 100 tests.

Soluciones en Python

from typing import TypeVar

from hypothesis import given
from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

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

def composicion(r1: Rel[A], r2: Rel[A]) -> Rel[A]:
    (u1, g1) = r1
    (_,  g2) = r2
    return (u1, [(x, z) for (x, y) in g1 for (u, z) in g2 if y == u])

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

def composicion2(r1: Rel[A], r2: Rel[A]) -> Rel[A]:
    (u1, g1) = r1
    (_,  g2) = r2
    def aux(g: list[tuple[A, A]]) -> list[tuple[A, A]]:
        if not g:
            return []
        (x, y) = g[0]
        return [(x, z) for (u, z) in g2 if y == u] + aux(g[1:])

    return (u1, aux(g1))

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

def composicion3(r1: Rel[A], r2: Rel[A]) -> Rel[A]:
    (u1, g1) = r1
    (_,  g2) = r2
    r: list[tuple[A, A]] = []
    for (x, y) in g1:
        r = r + [(x, z) for (u, z) in g2 if y == u]
    return (u1, r)

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

# La propiedad es
@given(st.integers(min_value=0, max_value=10),
       st.integers(min_value=0, max_value=10))
def test_simetrica(n: int, m: int) -> None:
    r1 = relacionArbitraria(n)
    r2 = relacionArbitraria(m)
    res = composicion(r1, r2)
    assert composicion2(r1, r2) == res
    assert composicion2(r1, r2) == res

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

from typing import TypeVar

from hypothesis import given

from hypothesis import strategies as st

from src.Relaciones_binarias import Rel, relacionArbitraria

A = TypeVar('A')

# 1ª solución

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

def composicion(r1: Rel[A], r2: Rel[A]) -> Rel[A]:

(u1, g1) = r1

(_, g2) = r2

return (u1, [(x, z) for (x, y) in g1 for (u, z) in g2 if y == u])

# 2ª solución

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

def composicion2(r1: Rel[A], r2: Rel[A]) -> Rel[A]:

(u1, g1) = r1

(_, g2) = r2

def aux(g: list[tuple[A, A]]) -> list[tuple[A, A]]:

if not g:

return []

(x, y) = g[0]

return [(x, z) for (u, z) in g2 if y == u] + aux(g[1:])

return (u1, aux(g1))

# 2ª solución

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

def composicion3(r1: Rel[A], r2: Rel[A]) -> Rel[A]:

(u1, g1) = r1

(_, g2) = r2

r: list[tuple[A, A]] = []

for (x, y) in g1:

r = r + [(x, z) for (u, z) in g2 if y == u]

return (u1, r)

# Comprobación de equivalencia

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

# La propiedad es

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

st.integers(min_value=0, max_value=10))

def test_simetrica(n: int, m: int) -> None:

r1 = relacionArbitraria(n)

r2 = relacionArbitraria(m)

res = composicion(r1, r2)

assert composicion2(r1, r2) == res

# La comprobación es

# > poetry run pytest -q Composicion_de_relaciones_binarias_v2.py

# 1 passed in 0.19s

Meses: abril 2023

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

TAD de los polinomios: Producto de polinomios

TAD de los polinomios: Suma de polinomios

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

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

TAD de los polinomios: Transformaciones entre polinomios y listas densas

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

TAD de los polinomios: Transformaciones entre polinomios y listas dispersas

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

El tipo abstracto de datos de los polinomios

1. El tipo abstracto de datos de los polinomios

2. Los polinomios en Haskell

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

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

2.3. Implementación de polinomios mediante listas densas

2.4. Implementación de polinomios mediante listas dispersas

3. Los polinomios en Python

3.1. El tipo abstracto de los polinomios en Python

3.2. Implementación de los polinomios mediante listas densas

3.3. Implementación de los polinomios mediante listas dispersas

Clausura transitiva

Clausura simétrica

Clausura reflexiva

Relaciones totales

Relaciones antisimétricas

Relaciones irreflexivas

Relaciones de equivalencia

Relaciones transitivas

Reconocimiento de subconjunto

Composición de relaciones binarias

Entradas recientes

Buscar

Correo electrónico