{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Tema 21: El TAD de los polinomios\n", " \n", "\n", "----------\n", "\n", "[José A. Alonso](https://www.cs.us.es/~jalonso) \n", "[Departamento de Ciencias de la Computación e I.A.](https://www.cs.us.es) \n", "[Universidad de Sevilla](http://www.us.es) \n", "Sevilla, 17 de agosto de 2019" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Notas:__ \n", "+ La versión interactiva de este tema se encuentra en [Binder](https://mybinder.org/v2/gh/jaalonso/Temas_interactivos_de_PF_con_Haskell/master?urlpath=lab/tree/temas/Tema-21.ipynb).\n", "+ Se desactiva el [corrector estilo de Haskell](https://github.com/gibiansky/IHaskell/wiki#opt-no-lint)." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ ":opt no-lint" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Especificación del TAD de los polinomios" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Signatura del TAD de los polinomios\n", "\n", "**Signatura del TAD de los polinomios**\n", "\n", "```sesion\n", "polCero :: Polinomio a \n", "esPolCero :: Polinomio a -> Bool \n", "consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a \n", "grado :: Polinomio a -> Int \n", "coefLider :: Num a => Polinomio a -> a \n", "restoPol :: (Num a, Eq a) => Polinomio a -> Polinomio a\n", "```\n", "Descripción de las operaciones:\n", "\n", "+ `polCero` es el polinomio cero.\n", "\n", "+ `(esPolCero p)` se verifica si `p` es el polinomio cero.\n", "\n", "+ `(consPol n b p)` es el polinomio $bx^n+p$.\n", "\n", "+ `(grado p)` es el grado del polinomio `p`.\n", "\n", "+ `(coefLider p)` es el coeficiente líder del polinomio `p`.\n", "\n", "+ `(restoPol p)` es el resto del polinomio `p`.\n", "\n", "**Ejemplos de polinomios**\n", "\n", "+ Definición:\n", "\n", "```haskell\n", "ejPol1, ejPol2, ejPol3, ejTerm:: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "ejTerm = consPol 1 4 polCero\n", "```\n", "\n", "+ Evaluación:\n", "\n", "```sesion\n", "ejPol1 == 3*x^4 + -5*x^2 + 3\n", "ejPol2 == x^5 + 5*x^2 + 4*x\n", "ejPol3 == 6*x^4 + 2*x\n", "ejTerm == 4*x\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Propiedades del TAD de los polinomios\n", "\n", "+ `esPolCero polCero`\n", "\n", "+ `n > grado p && b /= 0 ==> not (esPolCero (consPol n b p))`\n", "\n", "+ `consPol (grado p) (coefLider p) (restoPol p) == p`\n", "\n", "+ `n > grado p && b /= 0 ==> grado (consPol n b p) == n `\n", "\n", "+ `n > grado p && b /= 0 ==> coefLider (consPol n b p) == b `\n", "\n", "+ `n > grado p && b /= 0 ==> restoPol (consPol n b p) == p `" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Implementación del TAD de los polinomios" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Los polinomios como tipo de dato algebraico" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "module PolRepTDA\n", " ( Polinomio,\n", " polCero, -- Polinomio a \n", " esPolCero, -- Polinomio a -> Bool \n", " consPol, -- (Num a, Eq a)) => Int -> a -> Polinomio a -> Polinomio a \n", " grado, -- Polinomio a -> Int \n", " coefLider, -- Num t => Polinomio t -> t \n", " restoPol -- Polinomio t -> Polinomio t \n", " ) where\n", "\n", "-- ---------------------------------------------------------------------\n", "-- TAD de los polinomios mediante un tipo de dato algebraico. --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- Representamos un polinomio mediante los constructores ConsPol y\n", "-- PolCero. Por ejemplo, el polinomio \n", "-- 6x^4 -5x^2 + 4x -7 \n", "-- se representa por \n", "-- ConsPol 4 6 (ConsPol 2 (-5) (ConsPol 1 4 (ConsPol 0 (-7) PolCero)))\n", "\n", "data Polinomio a = PolCero \n", " | ConsPol Int a (Polinomio a)\n", " deriving Eq\n", " \n", "-- ---------------------------------------------------------------------\n", "-- Escritura de los polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "instance (Num a, Show a, Eq a) => Show (Polinomio a) where\n", " show PolCero = \"0\"\n", " show (ConsPol 0 b PolCero) = show b\n", " show (ConsPol 0 b p) = concat [show b, \" + \", show p] \n", " show (ConsPol 1 b PolCero) = show b ++ \"*x\"\n", " show (ConsPol 1 b p) = concat [show b, \"*x + \", show p] \n", " show (ConsPol n 1 PolCero) = \"x^\" ++ show n \n", " show (ConsPol n b PolCero) = concat [show b, \"*x^\", show n] \n", " show (ConsPol n 1 p) = concat [\"x^\", show n, \" + \", show p] \n", " show (ConsPol n b p) = concat [show b, \"*x^\", show n, \" + \", show p] \n", "\n", "-- ---------------------------------------------------------------------\n", "-- Ejemplos de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- Ejemplos de polinomios con coeficientes enteros:\n", "ejPol1, ejPol2, ejPol3:: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "\n", "-- Comprobación de escritura:\n", "-- > ejPol1\n", "-- 3*x^4 + -5*x^2 + 3\n", "-- > ejPol2\n", "-- x^5 + 5*x^2 + 4*x\n", "-- > ejPol3\n", "-- 6*x^4 + 2*x\n", "\n", "-- Ejemplos de polinomios con coeficientes reales:\n", "ejPol5, ejPol6, ejPol7:: Polinomio Float\n", "ejPol5 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol6 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol7 = consPol 1 2 (consPol 4 6 polCero)\n", "\n", "-- Comprobación de escritura:\n", "-- > ejPol5\n", "-- 3.0*x^4 + -5.0*x^2 + 3.0\n", "-- > ejPol6\n", "-- x^5 + 5.0*x^2 + 4.0*x\n", "-- > ejPol7\n", "-- 6.0*x^4 + 2.0*x\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Implementación de la especificación --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- polCero es el polinomio cero. Por ejemplo,\n", "-- > polCero\n", "-- 0\n", "polCero :: Polinomio a\n", "polCero = PolCero\n", "\n", "-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\n", "-- esPolCero polCero == True\n", "-- esPolCero ejPol1 == False\n", "esPolCero :: Polinomio a -> Bool\n", "esPolCero PolCero = True\n", "esPolCero _ = False\n", "\n", "-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- consPol 3 2 polCero == 2*x^3\n", "-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x\n", "-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x\n", "-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x\n", "consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a \n", "consPol _ 0 p = p\n", "consPol n b PolCero = ConsPol n b PolCero\n", "consPol n b (ConsPol m c p) \n", " | n > m = ConsPol n b (ConsPol m c p)\n", " | n < m = ConsPol m c (consPol n b p)\n", " | b+c == 0 = p\n", " | otherwise = ConsPol n (b+c) p\n", "\n", "-- (grado p) es el grado del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- grado ejPol3 == 4\n", "grado :: Polinomio a -> Int\n", "grado PolCero = 0\n", "grado (ConsPol n _ _) = n\n", "\n", "-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- coefLider ejPol3 == 6\n", "coefLider :: Num t => Polinomio t -> t\n", "coefLider PolCero = 0\n", "coefLider (ConsPol _ b _) = b\n", "\n", "-- (restoPol p) es el resto del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- restoPol ejPol3 == 2*x\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- restoPol ejPol2 == 5*x^2 + 4*x\n", "restoPol :: Polinomio t -> Polinomio t\n", "restoPol PolCero = PolCero\n", "restoPol (ConsPol _ _ p) = p" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Ejemplos" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*x^4 + -5*x^2 + 3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol1 :: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol1 " ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 :: Polinomio Int\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol2" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*x^4 + 2*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol3 :: Polinomio Int\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "ejPol3" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "polCero" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "esPolCero polCero" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "esPolCero ejPol1" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 \n", "consPol 3 0 ejPol2 " ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*x^3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 3 2 polCero " ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7*x^6 + x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 6 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 7*x^4 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 4 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8*x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 5 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*x^4 + 2*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "4" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol3 \n", "grado ejPol3 " ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "coefLider ejPol3 " ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "restoPol ejPol3 " ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 \n", "restoPol ejPol2 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Se elimina la implementación." ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ ":m - PolRepTDA" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Los polinomios como listas densas" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Representaremos un polinomio por la lista de sus coeficientes ordenados\n", "en orden decreciente según el grado. Por ejemplo, el polinomio \n", "6x^4 -5x^2 + 4x -7 se representa por [6,0,-2,4,-7]" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [], "source": [ "module PolRepDensa\n", " ( Polinomio,\n", " polCero, -- Polinomio a \n", " esPolCero, -- Polinomio a -> Bool \n", " consPol, -- (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a \n", " grado, -- Polinomio a -> Int \n", " coefLider, -- Num a => Polinomio a -> a \n", " restoPol -- (Num a, Eq a) => Polinomio a -> Polinomio a\n", " ) where\n", "\n", "-- ---------------------------------------------------------------------\n", "-- TAD de los polinomios mediante listas densas --\n", "-- ---------------------------------------------------------------------\n", "\n", "newtype Polinomio a = Pol [a] \n", " deriving Eq\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Escritura de los polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "instance (Num a, Show a, Eq a) => Show (Polinomio a) where\n", " show pol \n", " | esPolCero pol = \"0\"\n", " | n == 0 && esPolCero p = show a \n", " | n == 0 = concat [show a, \" + \", show p] \n", " | n == 1 && esPolCero p = show a ++ \"*x\"\n", " | n == 1 = concat [show a, \"*x + \", show p] \n", " | a == 1 && esPolCero p = \"x^\" ++ show n\n", " | esPolCero p = concat [show a, \"*x^\", show n] \n", " | a == 1 = concat [\"x^\", show n, \" + \", show p] \n", " | otherwise = concat [show a, \"*x^\", show n, \" + \", show p] \n", " where n = grado pol\n", " a = coefLider pol\n", " p = restoPol pol\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Ejemplos de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- Ejemplos de polinomios con coeficientes enteros:\n", "ejPol1, ejPol2, ejPol3:: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "\n", "-- Comprobación de escritura:\n", "-- > ejPol1\n", "-- 3*x^4 + -5*x^2 + 3\n", "-- > ejPol2\n", "-- x^5 + 5*x^2 + 4*x\n", "-- > ejPol3\n", "-- 6*x^4 + 2*x\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Implementación de la especificación --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- polCero es el polinomio cero. Por ejemplo,\n", "-- ghci> polCero\n", "-- 0\n", "polCero :: Polinomio a\n", "polCero = Pol []\n", "\n", "-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\n", "-- esPolCero polCero == True\n", "-- esPolCero ejPol1 == False\n", "esPolCero :: Polinomio a -> Bool\n", "esPolCero (Pol []) = True\n", "esPolCero _ = False\n", "\n", "-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- consPol 3 2 polCero == 2*x^3\n", "-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x\n", "-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x\n", "-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x\n", "consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\n", "consPol _ 0 p = p\n", "consPol n b p@(Pol xs) \n", " | esPolCero p = Pol (b : replicate n 0)\n", " | n > m = Pol (b : replicate (n-m-1) 0 ++ xs)\n", " | n < m = consPol m c (consPol n b (restoPol p))\n", " | b+c == 0 = Pol (dropWhile (==0) (tail xs))\n", " | otherwise = Pol ((b+c):tail xs)\n", " where \n", " c = coefLider p\n", " m = grado p\n", " \n", "-- (grado p) es el grado del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- grado ejPol3 == 4\n", "grado:: Polinomio a -> Int\n", "grado (Pol []) = 0\n", "grado (Pol xs) = length xs - 1\n", "\n", "-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- coefLider ejPol3 == 6\n", "coefLider:: Num t => Polinomio t -> t\n", "coefLider (Pol []) = 0\n", "coefLider (Pol (a:_)) = a \n", "\n", "-- (restoPol p) es el resto del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- restoPol ejPol3 == 2*x\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- restoPol ejPol2 == 5*x^2 + 4*x\n", "restoPol :: (Num t, Eq t) => Polinomio t -> Polinomio t\n", "restoPol (Pol []) = polCero\n", "restoPol (Pol [_]) = polCero\n", "restoPol (Pol (_:b:as)) \n", " | b == 0 = Pol (dropWhile (==0) as)\n", " | otherwise = Pol (b:as)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Ejemplos" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*x^4 + -5*x^2 + 3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol1 :: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol1 " ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 :: Polinomio Int\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol2" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*x^4 + 2*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol3 :: Polinomio Int\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "ejPol3" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "polCero" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "esPolCero polCero" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "esPolCero ejPol1" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 \n", "consPol 3 0 ejPol2 " ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*x^3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 3 2 polCero " ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7*x^6 + x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 6 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 7*x^4 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 4 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8*x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 5 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*x^4 + 2*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "4" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol3 \n", "grado ejPol3 " ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "coefLider ejPol3 " ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "restoPol ejPol3 " ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 \n", "restoPol ejPol2 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Se elimina la implementación." ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ ":m - PolRepDensa" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Los polinomios como listas dispersas\n", "\n", "Representaremos un polinomio mediante una lista de pares (grado,coef),\n", "ordenados en orden decreciente según el grado. Por ejemplo, el\n", "polinomio 6x^4 -5x^2 + 4x -7 se representa por [(4,6),(2,-5),(1,4),(0,-7)]. " ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [], "source": [ "module PolRepDispersa\n", " ( Polinomio,\n", " polCero, -- Polinomio a \n", " esPolCero, -- Num a => Polinomio a -> Bool \n", " consPol, -- Num a => Int -> a -> Polinomio a -> Polinomio a \n", " grado, -- Polinomio a -> Int \n", " coefLider, -- Num a => Polinomio a -> a \n", " restoPol -- Polinomio a -> Polinomio a \n", " ) where\n", "\n", "-- ---------------------------------------------------------------------\n", "-- TAD de los polinomios mediante listas dispersas. --\n", "-- ---------------------------------------------------------------------\n", "\n", "newtype Polinomio a = Pol [(Int,a)] \n", " deriving Eq\n", " \n", "-- ---------------------------------------------------------------------\n", "-- Escritura de los polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "instance (Num t, Show t, Eq t) => Show (Polinomio t) where\n", " show pol \n", " | esPolCero pol = \"0\"\n", " | n == 0 && esPolCero p = show a \n", " | n == 0 = concat [show a, \" + \", show p] \n", " | n == 1 && esPolCero p = show a ++ \"*x\"\n", " | n == 1 = concat [show a, \"*x + \", show p] \n", " | a == 1 && esPolCero p = \"x^\" ++ show n\n", " | esPolCero p = concat [show a, \"*x^\", show n] \n", " | a == 1 = concat [\"x^\", show n, \" + \", show p] \n", " | otherwise = concat [show a, \"*x^\", show n, \" + \", show p] \n", " where n = grado pol\n", " a = coefLider pol\n", " p = restoPol pol\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Ejemplos de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- Ejemplos de polinomios con coeficientes enteros:\n", "ejPol1, ejPol2, ejPol3:: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "\n", "-- Comprobación de escritura:\n", "-- > ejPol1\n", "-- 3*x^4 + -5*x^2 + 3\n", "-- > ejPol2\n", "-- x^5 + 5*x^2 + 4*x\n", "-- > ejPol3\n", "-- 6*x^4 + 2*x\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Implementación de la especificación --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- polCero es el polinomio cero. Por ejemplo,\n", "-- ghci> polCero\n", "-- 0\n", "polCero :: Num a => Polinomio a\n", "polCero = Pol []\n", "\n", "-- (esPolCero p) se verifica si p es el polinomio cero. Por ejemplo,\n", "-- esPolCero polCero == True\n", "-- esPolCero ejPol1 == False\n", "esPolCero :: Num a => Polinomio a -> Bool\n", "esPolCero (Pol []) = True\n", "esPolCero _ = False\n", "\n", "-- (consPol n b p) es el polinomio bx^n+p. Por ejemplo,\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- consPol 3 0 ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- consPol 3 2 polCero == 2*x^3\n", "-- consPol 6 7 ejPol2 == 7*x^6 + x^5 + 5*x^2 + 4*x\n", "-- consPol 4 7 ejPol2 == x^5 + 7*x^4 + 5*x^2 + 4*x\n", "-- consPol 5 7 ejPol2 == 8*x^5 + 5*x^2 + 4*x\n", "consPol :: (Num a, Eq a) => Int -> a -> Polinomio a -> Polinomio a\n", "consPol _ 0 p = p\n", "consPol n b p@(Pol xs) \n", " | esPolCero p = Pol [(n,b)]\n", " | n > m = Pol ((n,b):xs)\n", " | n < m = consPol m c (consPol n b (Pol (tail xs)))\n", " | b+c == 0 = Pol (tail xs)\n", " | otherwise = Pol ((n,b+c) : tail xs)\n", " where \n", " c = coefLider p\n", " m = grado p\n", "\n", "-- (grado p) es el grado del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- grado ejPol3 == 4\n", "grado:: Polinomio a -> Int\n", "grado (Pol []) = 0\n", "grado (Pol ((n,_):_)) = n\n", "\n", "-- (coefLider p) es el coeficiente líder del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- coefLider ejPol3 == 6\n", "coefLider:: Num t => Polinomio t -> t\n", "coefLider (Pol []) = 0\n", "coefLider (Pol ((_,b):_)) = b\n", "\n", "-- (restoPol p) es el resto del polinomio p. Por ejemplo,\n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- restoPol ejPol3 == 2*x\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- restoPol ejPol2 == 5*x^2 + 4*x\n", "restoPol :: Num t => Polinomio t -> Polinomio t\n", "restoPol (Pol []) = polCero\n", "restoPol (Pol [_]) = polCero\n", "restoPol (Pol (_:xs)) = Pol xs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Ejemplos" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*x^4 + -5*x^2 + 3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol1 :: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol1 " ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 :: Polinomio Int\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol2" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*x^4 + 2*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol3 :: Polinomio Int\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "ejPol3" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "polCero" ] }, { "cell_type": "code", "execution_count": 41, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "esPolCero polCero" ] }, { "cell_type": "code", "execution_count": 42, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "esPolCero ejPol1" ] }, { "cell_type": "code", "execution_count": 43, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 \n", "consPol 3 0 ejPol2 " ] }, { "cell_type": "code", "execution_count": 44, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*x^3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 3 2 polCero " ] }, { "cell_type": "code", "execution_count": 45, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7*x^6 + x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 6 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 46, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 7*x^4 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 4 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 47, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "8*x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "consPol 5 7 ejPol2 " ] }, { "cell_type": "code", "execution_count": 48, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*x^4 + 2*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "4" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol3 \n", "grado ejPol3 " ] }, { "cell_type": "code", "execution_count": 49, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "coefLider ejPol3 " ] }, { "cell_type": "code", "execution_count": 50, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "restoPol ejPol3 " ] }, { "cell_type": "code", "execution_count": 51, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 \n", "restoPol ejPol2 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Se elimina la implementación." ] }, { "cell_type": "code", "execution_count": 52, "metadata": {}, "outputs": [], "source": [ ":m - PolRepDispersa" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Comprobación de las implementaciones con QuickCheck" ] }, { "cell_type": "code", "execution_count": 53, "metadata": {}, "outputs": [], "source": [ "{-# LANGUAGE FlexibleInstances #-}\n", "\n", "module PolPropiedades where\n", "\n", "-- Nota: Hay que elegir una implementación del TAD de polinomios\n", "import PolRepTDA\n", "-- import PolRepDispersa\n", "-- import PolRepDensa\n", "\n", "import Test.QuickCheck\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Generador de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (genPol n) es un generador de polinomios. Por ejemplo,\n", "-- ghci> sample (genPol 1)\n", "-- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10\n", "-- -4*x^8 + 2*x\n", "-- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x\n", "-- -9*x^9 + x^5 + -7\n", "-- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2\n", "-- 7*x^10 + 5*x^9 + -5\n", "-- -8*x^10 + -7\n", "-- -5*x\n", "-- 5*x^10 + 4*x^4 + -3\n", "-- 3*x^3 + -4\n", "-- 10*x\n", "genPol :: Int -> Gen (Polinomio Int)\n", "genPol 0 = return polCero\n", "genPol _ = do\n", " n <- choose (0,10)\n", " b <- choose (-10,10)\n", " p <- genPol (div n 2)\n", " return (consPol n b p) \n", "\n", "instance Arbitrary (Polinomio Int) where\n", " arbitrary = sized genPol\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Propiedades --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- Propiedad. polCero es el polinomio cero.\n", "prop_polCero_es_cero :: Bool\n", "prop_polCero_es_cero =\n", " esPolCero polCero\n", "\n", "-- Comprobación.\n", "-- ghci> quickCheck prop_polCero_es_cero\n", "-- +++ OK, passed 100 tests.\n", "\n", "-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces \n", "-- (consPol n b p) es un polinomio distinto del cero.\n", "prop_consPol_no_cero :: Int -> Int -> Polinomio Int -> Property\n", "prop_consPol_no_cero n b p =\n", " n > grado p && b /= 0 ==> \n", " not (esPolCero (consPol n b p))\n", "\n", "-- Comprobación.\n", "-- ghci> quickCheck prop_consPol_no_cero\n", "-- +++ OK, passed 100 tests.\n", "\n", "-- Propiedad. (consPol (grado p) (coefLider p) (restoPol p)) es igual a p.\n", "prop_consPol :: Polinomio Int -> Bool\n", "prop_consPol p =\n", " consPol (grado p) (coefLider p) (restoPol p) == p\n", "\n", "-- Comprobación\n", "-- > quickCheck prop_consPol\n", "-- +++ OK, passed 100 tests.\n", "\n", "-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces\n", "-- el grado de (consPol n b p) es n.\n", "prop_grado :: Int -> Int -> Polinomio Int -> Property\n", "prop_grado n b p = \n", " n > grado p && b /= 0 ==> \n", " grado (consPol n b p) == n \n", " \n", "-- Comprobación.\n", "-- ghci> quickCheck prop_grado\n", "-- +++ OK, passed 100 tests.\n", "\n", "-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces\n", "-- el coeficiente líder de (consPol n b p) es b.\n", "prop_coefLider :: Int -> Int -> Polinomio Int -> Property\n", "prop_coefLider n b p = \n", " n > grado p && b /= 0 ==> \n", " coefLider (consPol n b p) == b \n", " \n", "-- Comprobación.\n", "-- ghci> quickCheck prop_coefLider\n", "-- +++ OK, passed 100 tests.\n", "\n", "-- Propiedad. Si n es mayor que el grado de p y b no es cero, entonces\n", "-- el resto de (consPol n b p) es p.\n", "prop_restoPol :: Int -> Int -> Polinomio Int -> Property\n", "prop_restoPol n b p = \n", " n > grado p && b /= 0 ==> \n", " restoPol (consPol n b p) == p \n", " \n", "-- Comprobación.\n", "-- ghci> quickCheck prop_restoPol\n", "-- +++ OK, passed 100 tests." ] }, { "cell_type": "code", "execution_count": 54, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+++ OK, passed 1 test." ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "+++ OK, passed 100 tests; 264 discarded." ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "+++ OK, passed 100 tests." ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "+++ OK, passed 100 tests; 234 discarded." ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "+++ OK, passed 100 tests; 286 discarded." ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "+++ OK, passed 100 tests; 339 discarded." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import Test.QuickCheck\n", "quickCheck prop_polCero_es_cero\n", "quickCheck prop_consPol_no_cero\n", "quickCheck prop_consPol\n", "quickCheck prop_grado\n", "quickCheck prop_coefLider\n", "quickCheck prop_restoPol" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Se elimina el módulo" ] }, { "cell_type": "code", "execution_count": 55, "metadata": {}, "outputs": [], "source": [ ":m - PolPropiedades" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Operaciones con polinomios" ] }, { "cell_type": "code", "execution_count": 56, "metadata": {}, "outputs": [], "source": [ "module PolOperaciones (module Pol, module PolOperaciones) where\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Importación de librerías --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- Nota: Hay que elegir una implementación del TAD de los polinomios.\n", "import PolRepTDA as Pol\n", "-- import PolRepDispersa as Pol\n", "-- import PolRepDensa as Pol\n", "\n", "import Test.QuickCheck\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Ejemplos --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- Ejemplos de polinomios con coeficientes enteros:\n", "ejPol1, ejPol2, ejPol3, ejTerm :: Polinomio Int\n", "ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))\n", "ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n", "ejPol3 = consPol 4 6 (consPol 1 2 polCero)\n", "ejTerm = consPol 1 4 polCero\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Generador de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (genPol n) es un generador de polinomios. Por ejemplo,\n", "-- ghci> sample (genPol 1)\n", "-- 7*x^9 + 9*x^8 + 10*x^7 + -14*x^5 + -15*x^2 + -10\n", "-- -4*x^8 + 2*x\n", "-- -8*x^9 + 4*x^8 + 2*x^6 + 4*x^5 + -6*x^4 + 5*x^2 + -8*x\n", "-- -9*x^9 + x^5 + -7\n", "-- 8*x^10 + -9*x^7 + 7*x^6 + 9*x^5 + 10*x^3 + -1*x^2\n", "-- 7*x^10 + 5*x^9 + -5\n", "-- -8*x^10 + -7\n", "-- -5*x\n", "-- 5*x^10 + 4*x^4 + -3\n", "-- 3*x^3 + -4\n", "-- 10*x\n", "genPol :: (Arbitrary a, Num a, Eq a) => Int -> Gen (Polinomio a)\n", "genPol 0 = return polCero\n", "genPol _ = do\n", " n <- choose (0,10)\n", " b <- arbitrary\n", " p <- genPol (div n 2)\n", " return (consPol n b p) \n", "\n", "instance (Arbitrary a, Num a, Eq a) => Arbitrary (Polinomio a) where\n", " arbitrary = sized genPol\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Funciones sobre términos --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (creaTermino n a) es el término a*x^n. Por ejemplo, \n", "-- creaTermino 2 5 == 5*x^2\n", "creaTermino :: (Num t, Eq t) => Int -> t -> Polinomio t\n", "creaTermino n a = consPol n a polCero\n", "\n", "-- (termLider p) es el término líder del polinomio p. Por ejemplo,\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- termLider ejPol2 == x^5\n", "termLider :: (Num t, Eq t) => Polinomio t -> Polinomio t\n", "termLider p = creaTermino (grado p) (coefLider p)\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Suma de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo, \n", "-- ejPol1 == 3*x^4 + -5*x^2 + 3\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- sumaPol ejPol1 ejPol2 == x^5 + 3*x^4 + 4*x + 3\n", "sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a\n", "sumaPol p q \n", " | esPolCero p = q\n", " | esPolCero q = p\n", " | n1 > n2 = consPol n1 a1 (sumaPol r1 q)\n", " | n1 < n2 = consPol n2 a2 (sumaPol p r2)\n", " | otherwise = consPol n1 (a1+a2) (sumaPol r1 r2)\n", " where n1 = grado p\n", " a1 = coefLider p\n", " r1 = restoPol p\n", " n2 = grado q\n", " a2 = coefLider q\n", " r2 = restoPol q\n", "\n", "-- Propiedad. El polinomio cero es el elemento neutro de la suma.\n", "prop_neutroSumaPol :: Polinomio Int -> Bool\n", "prop_neutroSumaPol p = \n", " sumaPol polCero p == p\n", "\n", "-- Comprobación con QuickCheck.\n", "-- ghci> quickCheck prop_neutroSumaPol\n", "-- OK, passed 100 tests.\n", "\n", "-- Propiedad. La suma es conmutativa.\n", "prop_conmutativaSuma :: Polinomio Int -> Polinomio Int -> Bool\n", "prop_conmutativaSuma p q = \n", " sumaPol p q == sumaPol q p\n", "\n", "-- Comprobación:\n", "-- ghci> quickCheck prop_conmutativaSuma\n", "-- OK, passed 100 tests.\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Producto de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (multPorTerm t p) es el producto del término t por el polinomio\n", "-- p. Por ejemplo,\n", "-- ejTerm == 4*x\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- multPorTerm ejTerm ejPol2 == 4*x^6 + 20*x^3 + 16*x^2\n", "multPorTerm :: (Num t, Eq t) => Polinomio t -> Polinomio t -> Polinomio t\n", "multPorTerm term pol \n", " | esPolCero pol = polCero\n", " | otherwise = consPol (n+m) (a*b) (multPorTerm term r)\n", " where n = grado term\n", " a = coefLider term\n", " m = grado pol\n", " b = coefLider pol\n", " r = restoPol pol \n", "\n", "-- (multPol p q) es el producto de los polinomios p y q. Por\n", "-- ejemplo,\n", "-- ghci> ejPol1\n", "-- 3*x^4 + -5*x^2 + 3\n", "-- ghci> ejPol2\n", "-- x^5 + 5*x^2 + 4*x\n", "-- ghci> multPol ejPol1 ejPol2\n", "-- 3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x\n", "multPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a\n", "multPol p q\n", " | esPolCero p = polCero\n", " | otherwise = sumaPol (multPorTerm (termLider p) q)\n", " (multPol (restoPol p) q)\n", "\n", "-- Propiedad. El producto de polinomios es conmutativo.\n", "prop_conmutativaProducto :: Polinomio Int -> Polinomio Int -> Bool\n", "prop_conmutativaProducto p q = \n", " multPol p q == multPol q p\n", "\n", "-- La comprobación es\n", "-- ghci> quickCheck prop_conmutativaProducto\n", "-- OK, passed 100 tests.\n", "\n", "-- El producto es distributivo respecto de la suma.\n", "prop_distributivaProductoSuma :: Polinomio Int -> Polinomio Int \n", " -> Polinomio Int -> Bool\n", "prop_distributivaProductoSuma p q r =\n", " multPol p (sumaPol q r) == sumaPol (multPol p q) (multPol p r)\n", "\n", "-- Comprobación:\n", "-- ghci> quickCheck prop_distributivaProductoSuma\n", "-- OK, passed 100 tests.\n", "\n", "-- polUnidad es el polinomio unidad. Por ejemplo, \n", "-- ghci> polUnidad\n", "-- 1\n", "polUnidad :: (Num t, Eq t) => Polinomio t\n", "polUnidad = consPol 0 1 polCero\n", "\n", "-- Propiedad. El polinomio unidad es el elemento neutro del producto.\n", "prop_polUnidad :: Polinomio Int -> Bool\n", "prop_polUnidad p = \n", " multPol p polUnidad == p\n", "\n", "-- Comprobación:\n", "-- ghci> quickCheck prop_polUnidad\n", "-- OK, passed 100 tests.\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Valor de un polinomio en un punto --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (valor p c) es el valor del polinomio p al sustituir su variable por\n", "-- c. Por ejemplo, \n", "-- ejPol1 == 3*x^4 + -5*x^2 + 3\n", "-- valor ejPol1 0 == 3\n", "-- valor ejPol1 1 == 1\n", "-- valor ejPol1 (-2) == 31\n", "valor:: (Num a, Eq a) => Polinomio a -> a -> a\n", "valor p c \n", " | esPolCero p = 0\n", " | otherwise = b*c^n + valor r c\n", " where n = grado p\n", " b = coefLider p\n", " r = restoPol p\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Verificación de raices de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (esRaiz c p) se verifica si c es una raiz del polinomio p. por\n", "-- ejemplo, \n", "-- ejPol3 == 6*x^4 + 2*x\n", "-- esRaiz 1 ejPol3 == False\n", "-- esRaiz 0 ejPol3 == True\n", "esRaiz :: (Num a, Eq a) => a -> Polinomio a -> Bool\n", "esRaiz c p = valor p c == 0\n", "\n", "-- ---------------------------------------------------------------------\n", "-- Derivación de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (derivada p) es la derivada del polinomio p. Por ejemplo, \n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- derivada ejPol2 == 5*x^4 + 10*x + 4\n", "derivada :: (Eq a, Num a) => Polinomio a -> Polinomio a\n", "derivada p \n", " | n == 0 = polCero\n", " | otherwise = consPol (n-1) (b * fromIntegral n) (derivada r)\n", " where n = grado p\n", " b = coefLider p\n", " r = restoPol p\n", "\n", "-- Propiedad. La derivada de la suma es la suma de las derivadas.\n", "prop_derivada :: Polinomio Int -> Polinomio Int -> Bool\n", "prop_derivada p q =\n", " derivada (sumaPol p q) == sumaPol (derivada p) (derivada q)\n", "\n", "-- Comprobación\n", "-- ghci> quickCheck prop_derivada\n", "-- OK, passed 100 tests. \n", "\n", "-- ---------------------------------------------------------------------\n", "-- Resta de polinomios --\n", "-- ---------------------------------------------------------------------\n", "\n", "-- (resta p q) es la el polinomio obtenido restándole a p el q. Por\n", "-- ejemplo, \n", "-- ejPol1 == 3*x^4 + -5*x^2 + 3\n", "-- ejPol2 == x^5 + 5*x^2 + 4*x\n", "-- restaPol ejPol1 ejPol2 == -1*x^5 + 3*x^4 + -10*x^2 + -4*x + 3\n", "restaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a\n", "restaPol p q = \n", " sumaPol p (multPorTerm (creaTermino 0 (-1)) q)" ] }, { "cell_type": "code", "execution_count": 57, "metadata": {}, "outputs": [], "source": [ "import Test.QuickCheck" ] }, { "cell_type": "code", "execution_count": 58, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "5*x^2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "creaTermino 2 5 " ] }, { "cell_type": "code", "execution_count": 59, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2\n", "termLider ejPol2" ] }, { "cell_type": "code", "execution_count": 60, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*x^4 + -5*x^2 + 3" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5 + 3*x^4 + 4*x + 3" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol1 \n", "ejPol2 \n", "sumaPol ejPol1 ejPol2 " ] }, { "cell_type": "code", "execution_count": 61, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+++ OK, passed 100 tests." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "quickCheck prop_neutroSumaPol" ] }, { "cell_type": "code", "execution_count": 62, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+++ OK, passed 100 tests." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "quickCheck prop_conmutativaSuma" ] }, { "cell_type": "code", "execution_count": 63, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "4*x^6 + 20*x^3 + 16*x^2" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejTerm \n", "ejPol2 \n", "multPorTerm ejTerm ejPol2" ] }, { "cell_type": "code", "execution_count": 64, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*x^4 + -5*x^2 + 3" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "3*x^9 + -5*x^7 + 15*x^6 + 15*x^5 + -25*x^4 + -20*x^3 + 15*x^2 + 12*x" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol1\n", "ejPol2\n", "multPol ejPol1 ejPol2" ] }, { "cell_type": "code", "execution_count": 65, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+++ OK, passed 100 tests." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "quickCheck prop_conmutativaProducto" ] }, { "cell_type": "code", "execution_count": 66, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+++ OK, passed 100 tests." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "quickCheck prop_distributivaProductoSuma" ] }, { "cell_type": "code", "execution_count": 67, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "polUnidad" ] }, { "cell_type": "code", "execution_count": 68, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+++ OK, passed 100 tests." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "quickCheck prop_polUnidad" ] }, { "cell_type": "code", "execution_count": 69, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3*x^4 + -5*x^2 + 3" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "3" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "1" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "31" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol1 \n", "valor ejPol1 0 \n", "valor ejPol1 1 \n", "valor ejPol1 (-2) " ] }, { "cell_type": "code", "execution_count": 70, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6*x^4 + 2*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "False" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "True" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol3 \n", "esRaiz 1 ejPol3 \n", "esRaiz 0 ejPol3 " ] }, { "cell_type": "code", "execution_count": 71, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "x^5 + 5*x^2 + 4*x" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "5*x^4 + 10*x + 4" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "ejPol2 \n", "derivada ejPol2 " ] }, { "cell_type": "code", "execution_count": 72, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "+++ OK, passed 100 tests." ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "quickCheck prop_derivada" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> **Nota** Se borran los ficheros de los módulos usados" ] }, { "cell_type": "code", "execution_count": 73, "metadata": {}, "outputs": [ { "data": { "text/plain": [] }, "metadata": {}, "output_type": "display_data" } ], "source": [ ":! rm -f *.hs *.hi *.o *.dyn_*" ] } ], "metadata": { "kernelspec": { "display_name": "Haskell", "language": "haskell", "name": "haskell" }, "language_info": { "codemirror_mode": "ihaskell", "file_extension": ".hs", "name": "haskell", "pygments_lexer": "Haskell", "version": "8.6.5" } }, "nbformat": 4, "nbformat_minor": 4 }