Menu Close

I1M2011: Operaciones con el TAD de los polinomios en Haskell (2)

En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos continuado estudiando la implementación en Haskell de operaciones con los polinomios utilizando las implementaciones del TAD de los polinomios estudiadas en las clases anteriores.

En los ejercicios se usan las siguientes libretrías:

  • PolRepTDA: Implementación de los polinomios mediante tipos de datos algebraicos.
  • PolRepDispersa: Implementación de los polinomios mediante listas dispersas.
  • PolRepDensa: Implementación de los polinomios mediante listas densas.
  • PolOperaciones: Operaciones con el TAD de los polinomios.

Los ejercicios, y sus soluciones, se muestran a continuación.

-- ---------------------------------------------------------------------
-- Importación de librerías                                           --
-- ---------------------------------------------------------------------
 
import PolOperaciones
import Test.QuickCheck
import Data.Ratio
 
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función
--    creaPolDispersa :: Num a => [a] -> Polinomio a
-- tal que (creaPolDispersa xs) es el polinomio cuya representación
-- dispersa es xs. Por ejemplo,
--    creaPolDispersa [7,0,0,4,0,3]  ==  7*x^5 + 4*x^2 + 3
-- ---------------------------------------------------------------------
 
creaPolDispersa :: Num a => [a] -> Polinomio a
creaPolDispersa []     = polCero
creaPolDispersa (x:xs) = consPol (length xs) x (creaPolDispersa xs)
 
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    creaPolDensa :: Num a => [(Int,a)] -> Polinomio a
-- tal que (creaPolDensa xs) es el polinomio cuya representación
-- densa es xs. Por ejemplo,
--    creaPolDensa [(5,7),(4,2),(3,0)]  ==  7*x^5 + 2*x^4
-- ---------------------------------------------------------------------
 
creaPolDensa :: Num a => [(Int,a)] -> Polinomio a
creaPolDensa [] = polCero
creaPolDensa ((n,a):ps) = consPol n a (creaPolDensa ps)
 
-- ---------------------------------------------------------------------
-- Nota. En el resto de la sucesión se usará en los ejemplos los
-- los polinomios que se definen a continuación.
-- ---------------------------------------------------------------------
 
pol1, pol2, pol3 :: Num a => Polinomio a
pol1 = creaPolDensa [(5,1),(2,5),(1,4)]
pol2 = creaPolDispersa [2,3]
pol3 = creaPolDensa [(7,2),(4,5),(2,5)]
 
pol4, pol5, pol6 :: Polinomio Rational 
pol4 = creaPolDensa [(4,3),(2,5),(0,3)]
pol5 = creaPolDensa [(2,6),(1,2)]
pol6 = creaPolDensa [(2,8),(1,14),(0,3)]
 
-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    densa :: Num a => Polinomio a -> [(Int,a)]
-- tal que (densa p) es la representación densa del polinomio p. Por
-- ejemplo, 
--    pol1        ==  x^5 + 5*x^2 + 4*x
--    densa pol1  ==  [(5,1),(2,5),(1,4)]
-- ---------------------------------------------------------------------
 
densa :: Num a => Polinomio a -> [(Int,a)]
densa p | esPolCero p = []
        | otherwise   = (grado p, coefLider p) : densa (restoPol p)
 
-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    densaAdispersa :: Num a => [(Int,a)] -> [a]
-- tal que (densaAdispersa ps) es la representación dispersa del
-- polinomio cuya representación densa es ps. Por ejemplo,
--    densaAdispersa [(5,1),(2,5),(1,4)]  ==  [1,0,0,5,4,0]
-- ---------------------------------------------------------------------
 
densaAdispersa :: Num a => [(Int,a)] -> [a]
densaAdispersa [] = []
densaAdispersa [(n,a)] = a : replicate n 0
densaAdispersa ((n,a):(m,b):ps) = 
    a : (replicate (n-m-1) 0) ++ densaAdispersa ((m,b):ps)
 
-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
--    dispersa :: Num a => Polinomio a -> [a]
-- tal que (dispersa p) es la representación dispersa del polinomio
-- p. Por ejemplo,
--    pol1           ==  x^5 + 5*x^2 + 4*x
--    dispersa pol1  ==  [1,0,0,5,4,0]
-- ---------------------------------------------------------------------
 
dispersa :: Num a => Polinomio a -> [a]
dispersa = densaAdispersa . densa
 
-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir la función
--    coeficiente :: Num a => Int -> Polinomio a -> a
-- tal que (coeficiente k p) es el coeficiente del término de grado k
-- del polinomio p. Por ejemplo,
--    pol1                ==  x^5 + 5*x^2 + 4*x
--    coeficiente 2 pol1  ==  5
--    coeficiente 3 pol1  ==  0
-- ---------------------------------------------------------------------
 
coeficiente :: Num 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
 
-- Otra definición equivalente es
coeficiente' :: Num a => Int -> Polinomio a -> a
coeficiente' k p = busca k (densa p)
    where busca k ps = head ([a | (n,a) <- ps, n == k] ++ [0])
 
-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la función
--    coeficientes :: Num a => Polinomio a -> [a]
-- tal que (coeficientes p) es la lista de los coeficientes del
-- polinomio p. Por ejemplo,
--    pol1               ==  x^5 + 5*x^2 + 4*x
--    coeficientes pol1  ==  [1,0,0,5,4,0]
-- ---------------------------------------------------------------------
 
coeficientes :: Num a => Polinomio a -> [a]
coeficientes p = [coeficiente k p | k <-[n,n-1..0]]
    where n = grado p
 
-- Una definición equivalente es
coeficientes' :: Num a => Polinomio a -> [a]
coeficientes' = dispersa
 
-- ---------------------------------------------------------------------
-- Ejercicio 8. Definir la función
--    potencia :: Num a => Polinomio a -> Int -> Polinomio a
-- tal que (potencia p n) es la potencia n-ésima del polinomio p. Por
-- ejemplo, 
--    pol2             ==  2*x + 3
--    potencia pol2 2  ==  4*x^2 + 12*x + 9
--    potencia pol2 3  ==  8*x^3 + 36*x^2 + 54*x + 27
-- ---------------------------------------------------------------------
 
potencia :: Num a => Polinomio a -> Int -> Polinomio a
potencia p 0 = polUnidad
potencia p n = multPol p (potencia p (n-1))
 
-- ---------------------------------------------------------------------
-- Ejercicio 9. Mejorar la definición de potencia definiendo la función
--    potenciaM :: Num a => Polinomio a -> Int -> Polinomio a
-- tal que (potenciaM p n) es la potencia n-ésima del polinomio p,
-- utilizando las siguientes propiedades:
--    * Si n es par,   entonces x^n = (x^2)^(n/2)
--    * Si n es impar, entonces x^n = x * (x^2)^((n-1)/2)
-- Por ejemplo, 
--    pol2              ==  2*x + 3
--    potenciaM pol2 2  ==  4*x^2 + 12*x + 9
--    potenciaM pol2 3  ==  8*x^3 + 36*x^2 + 54*x + 27
-- ---------------------------------------------------------------------
 
potenciaM :: Num a => Polinomio a -> Int -> Polinomio a
potenciaM p 0 = polUnidad
potenciaM p n
    | even n    = potenciaM (multPol p p) (n `div` 2)
    | otherwise = multPol p (potenciaM (multPol p p) ((n-1) `div` 2))
Sin categoría