{"id":5628,"date":"2016-11-25T19:13:41","date_gmt":"2016-11-25T18:13:41","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5628"},"modified":"2016-11-25T19:13:41","modified_gmt":"2016-11-25T18:13:41","slug":"i1m2016-ejercicios-de-tipos-de-datos-algebraicos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2016-ejercicios-de-tipos-de-datos-algebraicos-en-haskell\/","title":{"rendered":"I1M2016: Ejercicios de tipos de datos algebraicos en Haskell"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-16\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 10 sobre tipos de dato algebraico.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- En esta relaci\u00f3n se presenta ejercicios sobre distintos tipos de\n-- datos algebraicos. Concretamente,\n--    * \u00c1rboles binarios:\n--      + \u00c1rboles binarios con valores en los nodos.\n--      + \u00c1rboles binarios con valores en las hojas.\n--      + \u00c1rboles binarios con valores en las hojas y en los nodos.\n--      + \u00c1rboles booleanos.  \n--    * \u00c1rboles generales\n--    * Expresiones aritm\u00e9ticas\n--      + Expresiones aritm\u00e9ticas b\u00e1sicas.\n--      + Expresiones aritm\u00e9ticas con una variable.\n--      + Expresiones aritm\u00e9ticas con varias variables.\n--      + Expresiones aritm\u00e9ticas generales. \n--      + Expresiones aritm\u00e9ticas con tipo de operaciones.\n--    * Expresiones vectoriales\n-- \n-- Los ejercicios corresponden al tema 9 que se encuentran en \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-16\/temas\/tema-9.html\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Los \u00e1rboles binarios con valores en los nodos se\n-- pueden definir por\n--    data Arbol1 a = H1 \n--                  | N1 a (Arbol1 a) (Arbol1 a)\n--                  deriving (Show, Eq)\n-- Por ejemplo, el \u00e1rbol\n--         9                \n--        \/ \\    \n--       \/   \\   \n--      8     6  \n--     \/ \\   \/ \\ \n--    3   2 4   5\n-- se puede representar por\n--    N1 9 (N1 8 (N1 3 H1 H1) (N1 2 H1 H1)) (N1 6 (N1 4 H1 H1) (N1 5 H1 H1))\n--\n-- Definir por recursi\u00f3n la funci\u00f3n \n--    sumaArbol :: Num a => Arbol1 a -> a\n-- tal (sumaArbol x) es la suma de los valores que hay en el \u00e1rbol\n-- x. Por ejemplo,\n--    ghci> sumaArbol (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1))  \n--    21\n-- ---------------------------------------------------------------------\n\ndata Arbol1 a = H1 \n             | N1 a (Arbol1 a) (Arbol1 a)\n             deriving (Show, Eq)\n\nsumaArbol :: Num a => Arbol1 a -> a\nsumaArbol H1         = 0\nsumaArbol (N1 x i d) = x + sumaArbol i + sumaArbol d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir la funci\u00f3n \n--    mapArbol :: (a -> b) -> Arbol1 a -> Arbol1 b\n-- tal que (mapArbol f x) es el \u00e1rbol que resulta de sustituir cada nodo\n-- n del \u00e1rbol x por (f n). Por ejemplo,\n--    ghci> mapArbol (+1) (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1))\n--    N1 3 (N1 6 (N1 4 H1 H1) (N1 8 H1 H1)) (N1 5 H1 H1)\n-- ---------------------------------------------------------------------\n\nmapArbol :: (a -> b) -> Arbol1 a -> Arbol1 b\nmapArbol _ H1         = H1\nmapArbol f (N1 x i d) = N1 (f x) (mapArbol f i) (mapArbol f d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Definir la funci\u00f3n\n--    ramaIzquierda :: Arbol1 a -> [a]\n-- tal que (ramaIzquierda a) es la lista de los valores de los nodos de\n-- la rama izquierda del \u00e1rbol a. Por ejemplo,\n--    ghci> ramaIzquierda (N1 2 (N1 5 (N1 3 H1 H1) (N1 7 H1 H1)) (N1 4 H1 H1))\n--    [2,5,3]\n-- ---------------------------------------------------------------------\n\nramaIzquierda :: Arbol1 a -> [a]\nramaIzquierda H1         = []\nramaIzquierda (N1 x i d) = x : ramaIzquierda i\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.4. Diremos que un \u00e1rbol est\u00e1 balanceado si para cada nodo\n-- v la diferencia entre el n\u00famero de nodos (con valor) de sus sub\u00e1rboles\n-- izquierdo y derecho es menor o igual que uno.  \n--\n-- Definir la funci\u00f3n \n--    balanceado :: Arbol1 a -> Bool\n-- tal que (balanceado a) se verifica si el \u00e1rbol a est\u00e1 balanceado. Por \n-- ejemplo,\n--    balanceado (N1 5 H1 (N1 3 H1 H1))           == True\n--    balanceado (N1 5 H1 (N1 3 (N1 4 H1 H1) H1)) == False\n-- ---------------------------------------------------------------------\n\nbalanceado :: Arbol1 a -> Bool\nbalanceado H1         = True\nbalanceado (N1 _ i d) = abs (numeroNodos i - numeroNodos d) <= 1 \n                        &#038;&#038; balanceado i\n                        &#038;&#038; balanceado d\n                        \n-- (numeroNodos a) es el n\u00famero de nodos del \u00e1rbol a. Por ejemplo,\n--    numeroNodos (N1 5 H1 (N1 3 H1 H1)) ==  2\nnumeroNodos :: Arbol1 a -> Int\nnumeroNodos H1         = 0\nnumeroNodos (N1 _ i d) = 1 + numeroNodos i + numeroNodos d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Los \u00e1rboles binarios con valores en las hojas se pueden\n-- definir por\n--    data Arbol2 a = H2 a\n--                  | N2 (Arbol2 a) (Arbol2 a) \n--                  deriving Show\n-- Por ejemplo, los \u00e1rboles \n--    \u00e1rbol1          \u00e1rbol2       \u00e1rbol3     \u00e1rbol4 \n--       o              o           o           o    \n--      \/ \\            \/ \\         \/ \\         \/ \\   \n--     1   o          o   3       o   3       o   1  \n--        \/ \\        \/ \\         \/ \\         \/ \\     \n--       2   3      1   2       1   4       2   3    \n-- se representan por\n--    arbol1, arbol2, arbol3, arbol4 :: Arbol2 Int\n--    arbol1 = N2 (H2 1) (N2 (H2 2) (H2 3))\n--    arbol2 = N2 (N2 (H2 1) (H2 2)) (H2 3)\n--    arbol3 = N2 (N2 (H2 1) (H2 4)) (H2 3)\n--    arbol4 = N2 (N2 (H2 2) (H2 3)) (H2 1)\n-- \n-- Definir la funci\u00f3n\n--    igualBorde :: Eq a => Arbol2 a -> Arbol2 a -> Bool\n-- tal que (igualBorde t1 t2) se verifica si los bordes de los \u00e1rboles\n-- t1 y t2 son iguales. Por ejemplo,\n--    igualBorde arbol1 arbol2  ==  True\n--    igualBorde arbol1 arbol3  ==  False\n--    igualBorde arbol1 arbol4  ==  False\n-- ---------------------------------------------------------------------\n\ndata Arbol2 a = N2 (Arbol2 a) (Arbol2 a) \n              | H2 a\n              deriving Show\n\narbol1, arbol2, arbol3, arbol4 :: Arbol2 Int\narbol1 = N2 (H2 1) (N2 (H2 2) (H2 3))\narbol2 = N2 (N2 (H2 1) (H2 2)) (H2 3)\narbol3 = N2 (N2 (H2 1) (H2 4)) (H2 3)\narbol4 = N2 (N2 (H2 2) (H2 3)) (H2 1)\n\nigualBorde :: Eq a => Arbol2 a -> Arbol2 a -> Bool\nigualBorde t1 t2 = borde t1 == borde t2\n\n-- (borde t) es el borde del \u00e1rbol t; es decir, la lista de las hojas\n-- del \u00e1rbol t le\u00eddas de izquierda a derecha. Por ejemplo, \n--    borde arbol4  ==  [2,3,1]\nborde :: Arbol2 a -> [a]\nborde (N2 i d) = borde i ++ borde d\nborde (H2 x)   = [x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Los \u00e1rboles binarios con valores en las hojas y en los\n-- nodos se definen por\n--    data Arbol3 a = H3 a\n--                 | N3 a (Arbol3 a) (Arbol3 a) \n--                 deriving Show\n-- Por ejemplo, los \u00e1rboles\n--         5              8             5           5\n--        \/ \\            \/ \\           \/ \\         \/ \\\n--       \/   \\          \/   \\         \/   \\       \/   \\\n--      9     7        9     3       9     2     4     7\n--     \/ \\   \/ \\      \/ \\   \/ \\     \/ \\               \/ \\\n--    1   4 6   8    1   4 6   2   1   4             6   2\n-- se pueden representar por\n--    ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol3 Int\n--    ej3arbol1 = N3 5 (N3 9 (H3 1) (H3 4)) (N3 7 (H3 6) (H3 8))\n--    ej3arbol2 = N3 8 (N3 9 (H3 1) (H3 4)) (N3 3 (H3 6) (H3 2))\n--    ej3arbol3 = N3 5 (N3 9 (H3 1) (H3 4)) (H3 2)\n--    ej3arbol4 = N3 5 (H3 4) (N3 7 (H3 6) (H3 2))\n--\n-- Definir la funci\u00f3n\n--    igualEstructura :: Arbol3 -> Arbol3 -> Bool\n-- tal que (igualEstructura a1 a1) se verifica si los \u00e1rboles a1 y a2 \n-- tienen la misma estructura. Por ejemplo,\n--    igualEstructura ej3arbol1 ej3arbol2 == True\n--    igualEstructura ej3arbol1 ej3arbol3 == False\n--    igualEstructura ej3arbol1 ej3arbol4 == False\n-- ---------------------------------------------------------------------\n\ndata Arbol3 a = H3 a\n              | N3 a (Arbol3 a) (Arbol3 a) \n              deriving Show\n\nej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol3 Int\nej3arbol1 = N3 5 (N3 9 (H3 1) (H3 4)) (N3 7 (H3 6) (H3 8))\nej3arbol2 = N3 8 (N3 9 (H3 1) (H3 4)) (N3 3 (H3 6) (H3 2))\nej3arbol3 = N3 5 (N3 9 (H3 1) (H3 4)) (H3 2)\nej3arbol4 = N3 5 (H3 4) (N3 7 (H3 6) (H3 2))\n\nigualEstructura :: Arbol3 a -> Arbol3 a -> Bool\nigualEstructura (H3 _) (H3 _) = True\nigualEstructura (N3 r1 i1 d1) (N3 r2 i2 d2) = \n    igualEstructura i1 i2 && igualEstructura d1 d2\nigualEstructura _ _                       = False  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Definir la funci\u00f3n\n--    algunoArbol :: Arbol3 t -> (t -> Bool) -> Bool\n-- tal que (algunoArbol a p) se verifica si alg\u00fan elemento del \u00e1rbol a\n-- cumple la propiedad p. Por ejemplo,\n--    algunoArbol3 (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>4)  ==  True\n--    algunoArbol3 (N3 5 (N3 3 (H3 1) (H3 4)) (H3 2)) (>7)  ==  False\n-- ---------------------------------------------------------------------\n\nalgunoArbol :: Arbol3 a -> (a -> Bool) -> Bool\nalgunoArbol (H3 x) p     = p x\nalgunoArbol (N3 x i d) p = p x || algunoArbol i p || algunoArbol d p\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.3. Un elemento de un \u00e1rbol se dir\u00e1 de nivel k si aparece\n-- en el \u00e1rbol a distancia k  de la ra\u00edz.  \n-- \n-- Definir la funci\u00f3n\n--    nivel :: Int -> Arbol3 a -> [a]\n-- tal que (nivel k a) es la lista de los elementos de nivel k del \u00e1rbol\n-- a. Por ejemplo,\n--    nivel 0 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9))  ==  [7]\n--    nivel 1 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9))  ==  [2,9]\n--    nivel 2 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9))  ==  [5,4]\n--    nivel 3 (N3 7 (N3 2 (H3 5) (H3 4)) (H3 9))  ==  []\n-- ---------------------------------------------------------------------\n\nnivel :: Int -> Arbol3 a -> [a]\nnivel 0 (H3 x)      = [x]\nnivel 0 (N3 x _  _) = [x]\nnivel k (H3 _ )     = []\nnivel k (N3 _ i d)  = nivel (k-1) i ++ nivel (k-1) d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.4.  Los divisores medios de un n\u00famero son los que ocupan\n-- la posici\u00f3n media entre los divisores de n, ordenados de menor a\n-- mayor. Por ejemplo, los divisores de 60 son \n-- [1,2,3,4,5,6,10,12,15,20,30,60] y sus divisores medios son 6 y 10.\n-- \n-- El \u00e1rbol de factorizaci\u00f3n de un n\u00famero compuesto n se construye de la\n-- siguiente manera: \n--    * la ra\u00edz es el n\u00famero n, \n--    * la rama izquierda es el \u00e1rbol de factorizaci\u00f3n de su divisor\n--      medio menor y\n--    * la rama derecha es el \u00e1rbol de factorizaci\u00f3n de su divisor\n--      medio mayor\n-- Si el n\u00famero es primo, su \u00e1rbol de factorizaci\u00f3n s\u00f3lo tiene una hoja\n-- con dicho n\u00famero. Por ejemplo, el \u00e1rbol de factorizaci\u00f3n de 60 es\n--        60\n--       \/  \\\n--      6    10\n--     \/ \\   \/ \\\n--    2   3 2   5\n--\n-- Definir la funci\u00f3n\n--    arbolFactorizacion :: Int -> Arbol3\n-- tal que (arbolFactorizacion n) es el \u00e1rbol de factorizaci\u00f3n de n. Por\n-- ejemplo, \n--    arbolFactorizacion 60 == N3 60 (N3 6 (H3 2) (H3 3)) (N3 10 (H3 2) (H3 5))\n--    arbolFactorizacion 45 == N3 45 (H3 5) (N3 9 (H3 3) (H3 3))\n--    arbolFactorizacion 7  == H3 7\n--    arbolFactorizacion 14 == N3 14 (H3 2) (H3 7)\n--    arbolFactorizacion 28 == N3 28 (N3 4 (H3 2) (H3 2)) (H3 7)\n--    arbolFactorizacion 84 == N3 84 (H3 7) (N3 12 (H3 3) (N3 4 (H3 2) (H3 2)))\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\n-- =============\narbolFactorizacion :: Int -> Arbol3 Int\narbolFactorizacion n \n    | esPrimo n = H3 n\n    | otherwise = N3 n (arbolFactorizacion x) (arbolFactorizacion y)\n    where (x,y) = divisoresMedio n\n\n-- (esPrimo n) se verifica si n es primo. Por ejemplo,\n--    esPrimo 7  ==  True\n--    esPrimo 9  ==  False\nesPrimo :: Int -> Bool\nesPrimo n = divisores n == [1,n]\n\n-- (divisoresMedio n) es el par formado por los divisores medios de\n-- n. Por ejemplo,\n--    divisoresMedio 30  ==  (5,6)\n--    divisoresMedio  7  ==  (1,7)\ndivisoresMedio :: Int -> (Int,Int)\ndivisoresMedio n = (n `div` x,x)\n    where xs = divisores n\n          x  = xs !! (length xs `div` 2)\n\n-- (divisores n) es la lista de los divisores de n. Por ejemplo,\n--    divisores 30  ==  [1,2,3,5,6,10,15,30]\ndivisores :: Int -> [Int]\ndivisores n = [x | x <- [1..n], n `rem` x == 0]\n\n-- 2\u00aa definici\u00f3n\n-- =============\narbolFactorizacion2 :: Int -> Arbol3 Int\narbolFactorizacion2 n\n    | x == 1    = H3 n\n    | otherwise = N3 n (arbolFactorizacion x) (arbolFactorizacion y)\n    where (x,y) = divisoresMedio n\n\n-- (divisoresMedio2 n) es el par formado por los divisores medios de\n-- n. Por ejemplo,\n--    divisoresMedio2 30  ==  (5,6)\n--    divisoresMedio2  7  ==  (1,7)\ndivisoresMedio2 :: Int -> (Int,Int)\ndivisoresMedio2 n = (n `div` x,x)\n    where m  = ceiling (sqrt (fromIntegral n))\n          x = head [y | y <- [m..n], n `rem` y == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Se consideran los \u00e1rboles con operaciones booleanas\n-- definidos por   \n--    data ArbolB = HB Bool \n--                | Conj ArbolB ArbolB\n--                | Disy ArbolB ArbolB\n--                | Neg ArbolB\n-- \n-- Por ejemplo, los \u00e1rboles\n--                Conj                            Conj          \n--               \/   \\                           \/   \\          \n--              \/     \\                         \/     \\         \n--           Disy      Conj                  Disy      Conj     \n--          \/   \\       \/  \\                \/   \\      \/   \\    \n--       Conj    Neg   Neg True          Conj    Neg   Neg  True \n--       \/  \\    |     |                 \/  \\    |     |        \n--    True False False False          True False True  False     \n--\n-- se definen por\n--    ej1, ej2:: ArbolB\n--    ej1 = Conj (Disy (Conj (HB True) (HB False))\n--                     (Neg (HB False)))\n--               (Conj (Neg (HB False))\n--                     (HB True))\n--    \n--    ej2 = Conj (Disy (Conj (HB True) (HB False))\n--                     (Neg (HB True)))\n--               (Conj (Neg (HB False))\n--                     (HB True))\n-- \n-- Definir la funci\u00f3n \n--    valorB :: ArbolB -> Bool\n-- tal que (valorB ar) es el resultado de procesar el \u00e1rbol realizando\n-- las operaciones booleanas especificadas en los nodos. Por ejemplo,\n--    valorB ej1 == True\n--    valorB ej2 == False\n-- ---------------------------------------------------------------------\n\ndata ArbolB = HB Bool \n            | Conj ArbolB ArbolB\n            | Disy ArbolB ArbolB\n            | Neg ArbolB\n\nej1, ej2:: ArbolB\nej1 = Conj (Disy (Conj (HB True) (HB False))\n                 (Neg (HB False)))\n           (Conj (Neg (HB False))\n                 (HB True))\n\nej2 = Conj (Disy (Conj (HB True) (HB False))\n                 (Neg (HB True)))\n           (Conj (Neg (HB False))\n                 (HB True))\n\nvalorB:: ArbolB -> Bool\nvalorB (HB x)     = x\nvalorB (Neg a)    = not (valorB a)\nvalorB (Conj i d) = (valorB i) && (valorB d)\nvalorB (Disy i d) = (valorB i) || (valorB d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Los \u00e1rboles generales se pueden representar mediante el\n-- siguiente tipo de dato  \n--    data ArbolG a = N a [ArbolG a]\n--                  deriving (Eq, Show)\n-- Por ejemplo, los \u00e1rboles\n--      1               3               3\n--     \/ \\             \/|\\            \/ | \\\n--    2   3           \/ | \\          \/  |  \\\n--        |          5  4  7        5   4   7\n--        4          |     \/\\       |   |  \/ \\\n--                   6    2  1      6   1 2   1\n--                                     \/ \\\n--                                    2   3\n--                                        |\n--                                        4\n-- se representan por\n--    ejG1, ejG2, ejG3 :: ArbolG Int\n--    ejG1 = N 1 [N 2 [],N 3 [N 4 []]]\n--    ejG2 = N 3 [N 5 [N 6 []], \n--               N 4 [], \n--               N 7 [N 2 [], N 1 []]]\n--    ejG3 = N 3 [N 5 [N 6 []], \n--               N 4 [N 1 [N 2 [],N 3 [N 4 []]]], \n--               N 7 [N 2 [], N 1 []]]\n-- \n-- Definir la funci\u00f3n\n--     ramifica :: ArbolG a -> ArbolG a -> (a -> Bool) -> ArbolG a\n-- tal que (ramifica a1 a2 p) el \u00e1rbol que resulta de a\u00f1adir una copia\n-- del \u00e1rbol a2 a los nodos de a1 que cumplen un predicado p. Por\n-- ejemplo, \n--    ghci> ramifica ejG1 (N 8 []) (>4)\n--    N 1 [N 2 [],N 3 [N 4 []]]\n--    ghci> ramifica ejG1 (N 8 []) (>3)\n--    N 1 [N 2 [],N 3 [N 4 [N 8 []]]]\n--    ghci> ramifica ejG1 (N 8 []) (>2)\n--    N 1 [N 2 [],N 3 [N 4 [N 8 []],N 8 []]]\n--    ghci> ramifica ejG1 (N 8 []) (>1)\n--    N 1 [N 2 [N 8 []],N 3 [N 4 [N 8 []],N 8 []]]\n--    ghci> ramifica ejG1 (N 8 []) (>0)\n--    N 1 [N 2 [N 8 []],N 3 [N 4 [N 8 []],N 8 []],N 8 []]\n-- ---------------------------------------------------------------------\n\ndata ArbolG a = N a [ArbolG a]\n              deriving (Eq, Show)\n\nejG1, ejG2, ejG3 :: ArbolG Int\nejG1 = N 1 [N 2 [],N 3 [N 4 []]]\nejG2 = N 3 [N 5 [N 6 []], \n           N 4 [], \n           N 7 [N 2 [], N 1 []]]\nejG3 = N 3 [N 5 [N 6 []], \n           N 4 [N 1 [N 2 [],N 3 [N 4 []]]], \n           N 7 [N 2 [], N 1 []]]\n\nramifica :: ArbolG a -> ArbolG a -> (a -> Bool) -> ArbolG a\nramifica (N x xs) a2 p  \n         | p x       = N x ([ramifica a a2 p | a <- xs] ++ [a2])\n         | otherwise = N x  [ramifica a a2 p | a <- xs]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.1. Las expresiones aritm\u00e9ticas b\u00e1sicas pueden\n-- representarse usando el siguiente tipo de datos  \n--    data Expr1 = C1 Int \n--               | S1 Expr1 Expr1 \n--               | P1 Expr1 Expr1  \n--               deriving Show\n-- Por ejemplo, la expresi\u00f3n 2*(3+7) se representa por\n--    P1 (C1 2) (S1 (C1 3) (C1 7))\n-- \n-- Definir la funci\u00f3n\n--    valor :: Expr1 -> Int                   \n-- tal que (valor e) es el valor de la expresi\u00f3n aritm\u00e9tica e. Por\n-- ejemplo, \n--    valor (P1 (C1 2) (S1 (C1 3) (C1 7)))  ==  20\n-- ---------------------------------------------------------------------\n\ndata Expr1 = C1 Int \n           | S1 Expr1 Expr1 \n           | P1 Expr1 Expr1  \n           deriving Show\n                   \nvalor :: Expr1 -> Int                   \nvalor (C1 x)   = x \nvalor (S1 x y) = valor x + valor y\nvalor (P1 x y) = valor x * valor y\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.2. Definir la funci\u00f3n  \n--    aplica :: (Int -> Int) -> Expr1 -> Expr1\n-- tal que (aplica f e) es la expresi\u00f3n obtenida aplicando la funci\u00f3n f\n-- a cada uno de los n\u00fameros de la expresi\u00f3n e. Por ejemplo, \n--    ghci> aplica (+2) (S1 (P1 (C1 3) (C1 5)) (P1 (C1 6) (C1 7)))\n--    S1 (P1 (C1 5) (C1 7)) (P1 (C1 8) (C1 9))\n--    ghci> aplica (*2) (S1 (P1 (C1 3) (C1 5)) (P1 (C1 6) (C1 7)))\n--    S1 (P1 (C1 6) (C1 10)) (P1 (C1 12) (C1 14))\n-- ---------------------------------------------------------------------\n\naplica :: (Int -> Int) -> Expr1 -> Expr1\naplica f (C1 x)     = C1 (f x)\naplica f (S1 e1 e2) = S1 (aplica f e1) (aplica f e2)\naplica f (P1 e1 e2) = P1 (aplica f e1) (aplica f e2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Las expresiones aritm\u00e9ticas construidas con una\n-- variable (denotada por X), los n\u00fameros enteros y las operaciones de\n-- sumar y multiplicar se pueden representar mediante el tipo de datos\n-- Expr2 definido por     \n--    data Expr2 = X\n--               | C2 Int\n--               | S2 Expr2 Expr2\n--               | P2 Expr2 Expr2\n-- Por ejemplo, la expresi\u00f3n \"X*(13+X)\" se representa por\n-- \"P2 X (S2 (C2 13) X)\".\n-- \n-- Definir la funci\u00f3n \n--    valorE :: Expr2 -> Int -> Int\n-- tal que (valorE e n) es el valor de la expresi\u00f3n e cuando se\n-- sustituye su variable por n. Por ejemplo,\n--    valorE (P2 X (S2 (C2 13) X)) 2  ==  30\n-- ---------------------------------------------------------------------\n \ndata Expr2 = X\n           | C2 Int\n           | S2 Expr2 Expr2\n           | P2 Expr2 Expr2\n\nvalorE :: Expr2 -> Int -> Int\nvalorE X          n = n\nvalorE (C2 a)     n = a\nvalorE (S2 e1 e2) n = valorE e1 n + valorE e2 n\nvalorE (P2 e1 e2) n = valorE e1 n * valorE e2 n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Definir la funci\u00f3n\n--    numVars :: Expr2 -> Int\n-- tal que (numVars e) es el n\u00famero de variables en la expresi\u00f3n e. Por\n-- ejemplo, \n--    numVars (C2 3)                 ==  0\n--    numVars X                      ==  1\n--    numVars (P2 X (S2 (C2 13) X))  ==  2\n-- ---------------------------------------------------------------------\n\nnumVars :: Expr2 -> Int\nnumVars X        = 1\nnumVars (C2 n)   = 0\nnumVars (S2 a b) = numVars a + numVars b\nnumVars (P2 a b) = numVars a + numVars b\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.1. Las expresiones aritm\u00e9ticas con variables pueden\n-- representarse usando el siguiente tipo de datos  \n--    data Expr3 = C3 Int \n--               | V3 Char \n--               | S3 Expr3 Expr3 \n--               | P3 Expr3 Expr3  \n--               deriving Show\n-- Por ejemplo, la expresi\u00f3n 2*(a+5) se representa por\n--    P3 (C3 2) (S3 (V3 'a') (C3 5))\n-- \n-- Definir la funci\u00f3n\n--    valor3 :: Expr3 -> [(Char,Int)] -> Int                   \n-- tal que (valor3 x e) es el valor3 de la expresi\u00f3n x en el entorno e (es\n-- decir, el valor3 de la expresi\u00f3n donde las variables de x se sustituyen\n-- por los valores seg\u00fan se indican en el entorno e). Por ejemplo,\n--    ghci> valor3 (P3 (C3 2) (S3 (V3 'a') (V3 'b'))) [('a',2),('b',5)]\n--    14\n-- ---------------------------------------------------------------------\n\ndata Expr3 = C3 Int \n           | V3 Char \n           | S3 Expr3 Expr3 \n           | P3 Expr3 Expr3  \n           deriving Show\n                   \nvalor3 :: Expr3 -> [(Char,Int)] -> Int                   \nvalor3 (C3 x)   e = x\nvalor3 (V3 x)   e = head [y | (z,y) <- e, z == x]  \nvalor3 (S3 x y) e = valor3 x e + valor3 y e\nvalor3 (P3 x y) e = valor3 x e * valor3 y e\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.2. Definir la funci\u00f3n\n--    sumas :: Expr3 -> Int\n-- tal que (sumas e) es el n\u00famero de sumas en la expresi\u00f3n e. Por \n-- ejemplo, \n--    sumas (P3 (V3 'z') (S3 (C3 3) (V3 'x')))  ==  1\n--    sumas (S3 (V3 'z') (S3 (C3 3) (V3 'x')))  ==  2\n--    sumas (P3 (V3 'z') (P3 (C3 3) (V3 'x')))  ==  0\n-- ---------------------------------------------------------------------\n                   \nsumas :: Expr3 -> Int\nsumas (V3 _)   = 0\nsumas (C3 _)   = 0\nsumas (S3 x y) = 1 + sumas x + sumas y\nsumas (P3 x y) = sumas x + sumas y\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.3. Definir la funci\u00f3n\n--    sustitucion :: Expr3 -> [(Char, Int)] -> Expr3\n-- tal que (sustitucion e s) es la expresi\u00f3n obtenida sustituyendo las\n-- variables de la expresi\u00f3n e seg\u00fan se indica en la sustituci\u00f3n s. Por\n-- ejemplo, \n--    ghci> sustitucion (P3 (V3 'z') (S3 (C3 3) (V3 'x'))) [('x',7),('z',9)]\n--    P3 (C3 9) (S3 (C3 3) (C3 7))\n--    ghci> sustitucion (P3 (V3 'z') (S3 (C3 3) (V3 'y'))) [('x',7),('z',9)]\n--    P3 (C3 9) (S3 (C3 3) (V3 'y'))\n-- ---------------------------------------------------------------------\n                   \nsustitucion :: Expr3 -> [(Char, Int)] -> Expr3\nsustitucion e [] = e\nsustitucion (V3 c) ((d,n):ps) | c == d    = C3 n\n                              | otherwise = sustitucion (V3 c) ps\nsustitucion (C3 n) _ = C3 n                                 \nsustitucion (S3 e1 e2) ps = S3 (sustitucion e1 ps) (sustitucion e2 ps)\nsustitucion (P3 e1 e2) ps = P3 (sustitucion e1 ps) (sustitucion e2 ps)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.4. Definir la funci\u00f3n\n--    reducible :: Expr3 -> Bool\n-- tal que (reducible a) se verifica si a es una expresi\u00f3n reducible; es\n-- decir, contiene una operaci\u00f3n en la que los dos operandos son n\u00fameros. \n-- Por ejemplo,\n--    reducible (S3 (C3 3) (C3 4))               == True\n--    reducible (S3 (C3 3) (V3 'x'))             == False\n--    reducible (S3 (C3 3) (P3 (C3 4) (C3 5)))   == True\n--    reducible (S3 (V3 'x') (P3 (C3 4) (C3 5))) == True\n--    reducible (S3 (C3 3) (P3 (V3 'x') (C3 5))) == False\n--    reducible (C3 3)                           == False\n--    reducible (V3 'x')                         == False\n-- ---------------------------------------------------------------------\n\nreducible :: Expr3 -> Bool\nreducible (C3 _)             = False\nreducible (V3 _)             = False\nreducible (S3 (C3 _) (C3 _)) = True\nreducible (S3 a b)           = reducible a || reducible b\nreducible (P3 (C3 _) (C3 _)) = True\nreducible (P3 a b)           = reducible a || reducible b\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9. Las expresiones aritm\u00e9ticas generales se pueden definir\n-- usando el siguiente tipo de datos \n--    data Expr4 = C4 Int \n--               | Y \n--               | S4 Expr4 Expr4 \n--               | R4 Expr4 Expr4 \n--               | P4 Expr4 Expr4 \n--               | E4 Expr4 Int\n--               deriving (Eq, Show)\n-- Por ejemplo, la expresi\u00f3n \n--    3*x - (x+2)^7\n-- se puede definir por\n--    R4 (P4 (C4 3) Y) (E4 (S4 Y (C4 2)) 7)\n-- \n-- Definir la funci\u00f3n  \n--    maximo :: Expr4 -> [Int] -> (Int,[Int])\n-- tal que (maximo e xs) es el par formado por el m\u00e1ximo valor de la\n-- expresi\u00f3n e para los puntos de xs y en qu\u00e9 puntos alcanza el\n-- m\u00e1ximo. Por ejemplo, \n--    ghci> maximo (E4 (S4 (C4 10) (P4 (R4 (C4 1) Y) Y)) 2) [-3..3]\n--    (100,[0,1])\n-- ---------------------------------------------------------------------\n\ndata Expr4 = C4 Int \n          | Y \n          | S4 Expr4 Expr4 \n          | R4 Expr4 Expr4 \n          | P4 Expr4 Expr4 \n          | E4 Expr4 Int\n          deriving (Eq, Show)\n\nmaximo :: Expr4 -> [Int] -> (Int,[Int])\nmaximo e ns = (m,[n | n <- ns, valor e n == m])  \n    where m = maximum [valor e n | n <- ns]\n          valor :: Expr4 -> Int -> Int\n          valor (C4 x) _ = x\n          valor Y     n = n\n          valor (S4 e1 e2) n = (valor e1 n) + (valor e2 n)\n          valor (R4 e1 e2) n = (valor e1 n) - (valor e2 n)\n          valor (P4 e1 e2) n = (valor e1 n) * (valor e2 n)\n          valor (E4 e  m ) n = (valor e  n)^m\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10. Las operaciones de suma, resta y  multiplicaci\u00f3n se\n-- pueden representar mediante el siguiente tipo de datos \n--    data Op = Su | Re | Mu\n-- La expresiones aritm\u00e9ticas con dichas operaciones se pueden\n-- representar mediante el siguiente tipo de dato algebraico\n--    data Expr5 = C5 Int \n--               | A Op Expr5 Expr\n-- Por ejemplo, la expresi\u00f3n\n--    (7-3)+(2*5)\n-- se representa por\n--    A Su (A Re (C5 7) (C5 3)) (A Mu (C5 2) (C5 5))\n--\n-- Definir la funci\u00f3n\n--    valorEG :: Expr5 -> Int\n-- tal que (valorEG e) es el valorEG de la expresi\u00f3n e. Por ejemplo,\n--    valorEG (A Su (A Re (C5 7) (C5 3)) (A Mu (C5 2) (C5 5)))  ==  14\n--    valorEG (A Mu (A Re (C5 7) (C5 3)) (A Su (C5 2) (C5 5)))  ==  28\n-- ---------------------------------------------------------------------\n\ndata Op = Su | Re | Mu\n\ndata Expr5 = C5 Int | A Op Expr5 Expr5\n\nvalorEG :: Expr5 -> Int\nvalorEG (C5 x) = x\nvalorEG (A o e1 e2) = aplica o (valorEG e1) (valorEG e2)\n    where aplica :: Op -> Int -> Int -> Int\n          aplica Su x y = x+y\n          aplica Re x y = x-y\n          aplica Mu x y = x*y\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 11. Se consideran las expresiones vectoriales formadas por\n-- un vector, la suma de dos expresiones vectoriales o el producto de un\n-- entero por una expresi\u00f3n vectorial. El siguiente tipo de dato define\n-- las expresiones vectoriales  \n--    data ExpV = Vec Int Int\n--              | Sum ExpV ExpV\n--              | Mul Int ExpV\n--              deriving Show\n-- \n-- Definir la funci\u00f3n \n--    valorEV :: ExpV -> (Int,Int)\n-- tal que (valorEV e) es el valorEV de la expresi\u00f3n vectorial c. Por\n-- ejemplo, \n--    valorEV (Vec 1 2)                                  ==  (1,2)\n--    valorEV (Sum (Vec 1 2 ) (Vec 3 4))                 ==  (4,6)\n--    valorEV (Mul 2 (Vec 3 4))                          ==  (6,8)\n--    valorEV (Mul 2 (Sum (Vec 1 2 ) (Vec 3 4)))         ==  (8,12)\n--    valorEV (Sum (Mul 2 (Vec 1 2)) (Mul 2 (Vec 3 4)))  ==  (8,12)\n-- ---------------------------------------------------------------------\n\ndata ExpV = Vec Int Int\n          | Sum ExpV ExpV\n          | Mul Int ExpV\n          deriving Show\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\nvalorEV :: ExpV -> (Int,Int)\nvalorEV (Vec x y)   = (x,y)\nvalorEV (Sum e1 e2) = (x1+x2,y1+y2) \n    where (x1,y1) = valorEV e1  \n          (x2,y2) = valorEV e2  \nvalorEV (Mul n e)   = (n*x,n*y) \n    where (x,y) = valorEV e  \n\n-- 2\u00aa soluci\u00f3n\n-- ===========\nvalorEV2 :: ExpV -> (Int,Int)\nvalorEV2 (Vec a b)   = (a, b)\nvalorEV2 (Sum e1 e2) = suma (valorEV2 e1) (valorEV2 e2)\nvalorEV2 (Mul n e1)  = multiplica n (valorEV2 e1)\n\nsuma :: (Int,Int) -> (Int,Int) -> (Int,Int)\nsuma (a,b) (c,d) = (a+c,b+d)\n\nmultiplica :: Int -> (Int, Int) -> (Int, Int)\nmultiplica n (a,b) = (n*a,n*b)\n<\/pre>\n<p>El c\u00f3digo correspondiente se encuentra en <a href=\"http:\/\/bit.ly\/1NTYOny\">GitHub<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los ejercicios de la relaci\u00f3n 10 sobre tipos de dato algebraico. Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[260],"tags":[263,270,313],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5628"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=5628"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5628\/revisions"}],"predecessor-version":[{"id":5629,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5628\/revisions\/5629"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5628"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5628"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5628"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}