Expresiones aritméticas mediante tipos abstracto de datos y polinomios en Haskell
El objetivo de esta relación de ejercicios es estudiar dos representaciones de las expresiones aritméticas construidas con una variable, los números enteros y las operaciones suma y producto.
Una representación es mediante tipo algebraico y la otra es mediante la lista de los coeficientes del polinomio correspondiente.
Se verá como puede transformarse una representación en la otra y se comprobará con QuickCheck la equivalencia de las representaciones.
La relación está basada en el ejercicio 3.3 (página 15) del artículo Interactive Proof Introduction to Isabelle/HOL de Tobias Nipkow.
El contenido de la relación de ejercicios se encuentra en LógicaMente y se muestra a continuación:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 |
-- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import Test.QuickCheck -- --------------------------------------------------------------------- -- Ejercicio 1. Definir el tipo de datos Exp para representar la -- expresiones aritméticas construidas con una variables, los números -- enteros y las operaciones de sumar y multiplicar. Por ejemplo, la -- expresión 3+5x^2 se puede representar por -- Sum (Const 2) (Mul Var (Mul Var (Const 5))) -- --------------------------------------------------------------------- data Exp = Var | Const Int | Sum Exp Exp | Mul Exp Exp deriving Show exp1 :: Exp exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5))) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- valorE :: Exp -> Int -> Int -- tal que (valorE e n) es el valor de la expresión e cuando se -- sustituye su variable por n. Por ejemplo, -- valorE exp1 2 == 23 -- --------------------------------------------------------------------- valorE :: Exp -> Int -> Int valorE Var n = n valorE (Const a) n = a valorE (Sum e1 e2) n = (valorE e1 n) + (valorE e2 n) valorE (Mul e1 e2) n = (valorE e1 n) * (valorE e2 n) -- --------------------------------------------------------------------- -- Ejercicio 3. Los polinomios se pueden representar por la lista de sus -- coeficientes. Por ejemplo, el polinomio 3+5x^2 se puede representar -- por [3,0,5]. Definir el tipo Pol para representar polinomios. -- --------------------------------------------------------------------- type Pol = [Int] -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- simplifica :: Pol -> Pol -- tal que (simplifica p) es el polinomio obtenido eliminando los ceros -- finales de p. Por ejemplo, -- simplifica [3,0,5,0,0] == [3,0,5] -- --------------------------------------------------------------------- simplifica :: Pol -> Pol simplifica p = reverse (dropWhile (==0) (reverse p)) -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- sumaPol :: Pol -> Pol -> Pol -- tal que (sumaPol p1 p2) es la suma de los polinomios p1 y p2. Por -- ejemplo, -- sumaPol [1,3] [4,-3,7] == [5,0,7] -- sumaPol [1,3,7] [4,-3] == [5,0,7] -- sumaPol [1,4,7,3,-5] [6,-4,1,-3,5] == [7,0,8] -- --------------------------------------------------------------------- sumaPol :: Pol -> Pol -> Pol sumaPol p1 p2 = simplifica ((zipWith (+) q1 q2) ++ r1 ++ r2) where n1 = length p1 n2 = length p2 n = min n1 n2 (q1,r1) = splitAt n p1 (q2,r2) = splitAt n p2 -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- multiplicaPol :: Pol -> Pol -> Pol -- tal que (multiplicaPol p1 p2) es el producto de los polinomios p1 y -- p2. Por ejemplo, -- multiplicaPol [1,3] [2,0,5] == [2,6,5,15] -- --------------------------------------------------------------------- multiplicaPol :: Pol -> Pol -> Pol multiplicaPol [a] p2 = [a*b | b <- p2] multiplicaPol p1 [b] = [a*b | a <- p1] multiplicaPol (a:p1) (b:p2) = (a*b) : suma3Pol (multiplicaPol [a] p2) (multiplicaPol p1 [b]) (0 : (multiplicaPol p1 p2)) where suma3Pol p q r = sumaPol p (sumaPol q r) -- --------------------------------------------------------------------- -- Ejercicio 7. Definir la función -- polinomio :: Exp -> Pol -- tal que (polinomio e) es el polinomio equivalente a la expresión -- e. Por ejemplo, -- exp1 == Sum (Const 3) (Mul Var (Mul Var (Const 5))) -- polinomio exp1 == [3,0,5] -- --------------------------------------------------------------------- polinomio :: Exp -> Pol polinomio Var = [0,1] polinomio (Const a) = [a] polinomio (Sum e1 e2) = sumaPol (polinomio e1) (polinomio e2) polinomio (Mul e1 e2) = multiplicaPol (polinomio e1) (polinomio e2) -- --------------------------------------------------------------------- -- Ejercicio 8. Definir la función -- expresion :: Pol -> Exp -- tal que (expresion p) es una expresión aritmética equivalente al -- polinomio p. Por ejemplo, -- ghci> expresion [3,0,5] -- Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5)))) -- ghci> polinomio (expresion [3,0,5]) -- [3,0,5] -- --------------------------------------------------------------------- expresion :: Pol -> Exp expresion [a] = Const a expresion (a:p) = Sum (Const a) (Mul Var (expresion p)) -- --------------------------------------------------------------------- -- Ejercicio 9. Comprobar con QuickCheck que, para todo polinomio p, -- polinomio (expresion p) == p -- --------------------------------------------------------------------- -- La propiedad es prop_polinomio_expresion :: Pol -> Property prop_polinomio_expresion p = not (null p) ==> polinomio (expresion p) == p -- La comprobación es -- ghci> quickCheck prop_polinomio_expresion -- +++ OK, passed 100 tests. -- --------------------------------------------------------------------- -- Ejercicio 10. Definir la función -- valorP :: Pol -> Int -> Int -- tal que (valorP p n) es el valor del polinomio p cuando se sustituye -- su variable por n. Por ejemplo, -- valorP [3,0,5] 2 == 23 -- --------------------------------------------------------------------- valorP :: Pol -> Int -> Int valorP [a] _ = a valorP (a:p) n = a + n * valorP p n -- --------------------------------------------------------------------- -- Ejercicio 11. Comprobar con QuickCheck que, para todo polinomio p y -- todo entero n, -- valorP p n == valorE (expresion p) n -- --------------------------------------------------------------------- -- La propiedad es prop_valor :: Pol -> Int -> Property prop_valor p n = not (null p) ==> valorP p n == valorE (expresion p) n -- La comprobación es -- ghci> quickCheck prop_valor -- +++ OK, passed 100 tests. |