19-abril-2023 – Exercitium

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

Día: 19-abril-2023

TAD de los polinomios: Transformaciones entre polinomios y listas dispersas

Entradas recientes

Buscar

Correo electrónico