{"id":1215,"date":"2011-02-14T15:27:52","date_gmt":"2011-02-14T15:27:52","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1215"},"modified":"2013-03-08T05:50:03","modified_gmt":"2013-03-08T05:50:03","slug":"i1m2010-ejercicios-de-haskell-relaciones-16-17-y-18","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-ejercicios-de-haskell-relaciones-16-17-y-18\/","title":{"rendered":"I1M2010: Ejercicios de Haskell (relaciones 16, 17 y 18)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-10\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado la resoluci\u00f3n de ejercicios de las relaciones 16, 17 y 18 cuyas soluciones se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<p>Las soluciones de los ejercicios  de la relaci\u00f3n 16 son <\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Usando el tipo de dato Nat y la funci\u00f3n suma definidas\r\n-- en las transparencias del tema 9, definir la funci\u00f3n\r\n--    producto :: Nat -> Nat -> Nat\r\n-- tal que (producto m n) es el producto de los n\u00fameros naturales m y\r\n-- n. Por ejemplo, \r\n--    *Main> producto (Suc (Suc Cero)) (Suc (Suc (Suc Cero)))\r\n--    Suc (Suc (Suc (Suc (Suc (Suc Cero)))))\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Nat = Cero | Suc Nat\r\n           deriving (Eq, Show)\r\n\r\nsuma :: Nat -> Nat -> Nat\r\nsuma Cero    n = n\r\nsuma (Suc m) n = Suc (suma m n)\r\n\r\nproducto :: Nat -> Nat -> Nat\r\nproducto Cero _    = Cero\r\nproducto (Suc m) n = suma n (producto m n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Nota. En los siguientes ejercicios se trabajar\u00e1 con \u00e1rboles binarios\r\n-- definidos como sigue\r\n--    data Arbol = Hoja Int \r\n--               | Nodo Arbol Int Arbol\r\n--               deriving (Show, Eq)\r\n-- Por ejemplo, el \u00e1rbol\r\n--         5 \r\n--        \/ \\\r\n--       \/   \\\r\n--      3     7\r\n--     \/ \\   \/ \\  \r\n--    1   4 6   9  \r\n-- se representa por\r\n--    Nodo (Nodo (Hoja 1) 3 (Hoja 4)) \r\n--         5 \r\n--         (Nodo (Hoja 6) 7 (Hoja 9))\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Arbol = Hoja Int \r\n           | Nodo Arbol Int Arbol\r\n           deriving (Show, Eq)\r\n\r\nejArbol :: Arbol\r\nejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4)) \r\n               5 \r\n               (Nodo (Hoja 6) 7 (Hoja 9))\r\n\r\n-- --------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    ocurre :: Int -> Arbol -> Bool\r\n-- tal que (ocurre x a) se verifica si x ocurre en el \u00e1rbol a como valor\r\n-- de un nodo o de una hoja. Por ejemplo,\r\n--    ocurre  4 ejArbol  ==  True\r\n--    ocurre 10 ejArbol  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nocurre :: Int -> Arbol -> Bool\r\nocurre m (Hoja n)     = m == n\r\nocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. En el preludio est\u00e1 definido el tipo de datos\r\n--    data Ordering = LT | EQ | GT\r\n-- junto con la funci\u00f3n\r\n--    compare :: Ord a => a -> a -> Ordering\r\n-- que decide si un valor en un tipo ordenado es menor (LT), igual (EQ)\r\n-- o mayor (GT) que otro. \r\n-- \r\n-- Usando esta funci\u00f3n, redefinir la funci\u00f3n\r\n--    ocurre :: Int -> Arbol -> Bool\r\n-- del ejercicio anterior. \r\n-- ---------------------------------------------------------------------\r\n\r\nocurre' :: Int -> Arbol -> Bool\r\nocurre' m (Hoja n)     = m == n\r\nocurre' m (Nodo i n d) = case compare m n of\r\n                           LT -> ocurre' m i\r\n                           EQ -> True\r\n                           GT -> ocurre' m d\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. \u00bfPorqu\u00e9 la segunda definici\u00f3n de ocurre es m\u00e1s eficiente\r\n-- que la primera? \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La nueva definici\u00f3n es m\u00e1s eficiente porque s\u00f3lo necesita una\r\n-- comparaci\u00f3n por nodo, mientras que la definici\u00f3n de las\r\n-- transparencias necesita dos comparaciones por nodo.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Nota. En los siguientes ejercicios se trabajar\u00e1 con \u00e1rboles binarios\r\n-- definidos como sigue\r\n--    type ArbolB = HojaB Int \r\n--                | NodoB ArbolB ArbolB \r\n--                deriving Show\r\n-- Por ejemplo, el \u00e1rbol\r\n--         . \r\n--        \/ \\\r\n--       \/   \\\r\n--      .     .\r\n--     \/ \\   \/ \\  \r\n--    1   4 6   9  \r\n-- se representa por\r\n--    NodoB (NodoB (HojaB 1) (HojaB 4)) \r\n--          (NodoB (HojaB 6) (HojaB 9))\r\n-- ---------------------------------------------------------------------\r\n\r\ndata ArbolB = HojaB Int \r\n            | NodoB ArbolB ArbolB\r\n            deriving Show\r\n\r\nejArbolB :: ArbolB\r\nejArbolB = NodoB (NodoB (HojaB 1) (HojaB 4)) \r\n                 (NodoB (HojaB 6) (HojaB 9))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n \r\n--    nHojas :: ArbolB -> Int\r\n-- tal que (nHojas a) es el n\u00famero de hojas del \u00e1rbol a. Por ejemplo,\r\n--    nHojas (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7)))  ==  3\r\n--    nHojas ejArbolB ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nnHojas :: ArbolB -> Int\r\nnHojas (HojaB _)     = 1\r\nnHojas (NodoB a1 a2) = nHojas a1 + nHojas a2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Se dice que un \u00e1rbol de este tipo es balanceado si es\r\n-- una hoja o bien si para cada nodo se tiene que el n\u00famero de hojas en\r\n-- cada uno de sus sub\u00e1rboles difiere como m\u00e1ximo en uno y sus\r\n-- sub\u00e1rboles son balanceados. Definir la funci\u00f3n \r\n--    balanceado :: ArbolB -> BoolB\r\n-- tal que (balanceado a) se verifica si a es un \u00e1rbol balanceado. Por\r\n-- ejemplo, \r\n--    bakaceado ejArbolB\r\n--    ==> True\r\n--    balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7)))\r\n--    ==> True\r\n--    balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (NodoB (HojaB 5) (HojaB 7))))\r\n--    ==> False\r\n-- ---------------------------------------------------------------------\r\n \r\nbalanceado :: ArbolB -> Bool\r\nbalanceado (HojaB _)     = True\r\nbalanceado (NodoB a1 a2) = abs (nHojas a1 - nHojas a2) <= 1 &#038;&#038;\r\n                           balanceado a1 &#038;&#038;\r\n                           balanceado a2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n \r\n--    mitades :: [a] -> ([a],[a]) \r\n-- tal que (mitades xs) es un par de listas que se obtiene al dividir xs\r\n-- en dos mitades cuya longitud difiere como m\u00e1ximo en uno. Por ejemplo,\r\n--    mitades [2,3,5,1,4,7]    ==  ([2,3,5],[1,4,7])\r\n--    mitades [2,3,5,1,4,7,9]  ==  ([2,3,5],[1,4,7,9])\r\n-- ---------------------------------------------------------------------\r\n\r\nmitades :: [a] -> ([a],[a])\r\nmitades xs = splitAt (length xs `div` 2) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir la funci\u00f3n\r\n--    arbolBalanceado :: [Int] -> ArbolB\r\n-- tal que (arbolBalanceado xs) es el \u00e1rbol balanceado correspondiente\r\n-- a la lista xs. Por ejemplo,\r\n--    *Main> arbolBalanceado [2,5,3]\r\n--    NodoB (HojaB 2) (NodoB (HojaB 5) (HojaB 3))\r\n--    *Main> arbolBalanceado [2,5,3,7]\r\n--    NodoB (NodoB (HojaB 2) (HojaB 5)) (NodoB (HojaB 3) (HojaB 7))\r\n-- ---------------------------------------------------------------------\r\n\r\narbolBalanceado :: [Int] -> ArbolB\r\narbolBalanceado [x] = HojaB x\r\narbolBalanceado xs  = NodoB (arbolBalanceado ys) (arbolBalanceado zs)\r\n                      where (ys,zs) = mitades xs\r\n                                       \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Los n\u00fameros naturales menores que 10 que son m\u00faltiplos\r\n-- de 3 \u00f3 5 son 3, 5, 6 y 9. La suma de estos m\u00faltiplos es 23. Definir\r\n-- la funci\u00f3n \r\n--    sumaMultiplosMenores :: Integer -> Integer\r\n-- tal que (sumaMultiplosMenores n) es la suma de todos los m\u00faltiplos de\r\n-- 3 \u00f3 5 menores que n. Por ejemplo,\r\n--    sumaMultiplosMenores 10  =>  23\r\n-- Calcular la suma de todos los m\u00faltiplos de 3 \u00f3 5 menores que 1000,\r\n-- indicando el tiempo y el espacio empleado.\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaMultiplosMenores :: Integer -> Integer\r\nsumaMultiplosMenores n = \r\n    sum [x | x <- [1..n-1], multiplo x 3 || multiplo x 5]\r\n    where multiplo x y = mod x y == 0\r\n\r\n-- C\u00e1lculo:\r\n--    *Main> :set +s\r\n--    *Main> sumaMultiplosMenores 1000\r\n--    233168\r\n--    (0.03 secs, 1053460 bytes)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir la funci\u00f3n\r\n--    productoCartesiano :: [[a]] -> [[a]]\r\n-- tal que (productoCartesiano xss) es el producto cartesiano de los conjuntos\r\n-- xss. Por ejemplo,\r\n--    *Main> productoCartesiano [[1,3],[2,5]]\r\n--    [[1,2],[1,5],[3,2],[3,5]]\r\n--    *Main> productoCartesiano [[1,3],[2,5],[6,4]]\r\n--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]\r\n--    *Main> productoCartesiano [[1,3,5],[2,4]]\r\n--    [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]]\r\n--    *Main> productoCartesiano []\r\n--    [[]]\r\n-- ---------------------------------------------------------------------\r\n\r\nproductoCartesiano :: [[a]] -> [[a]]\r\nproductoCartesiano []       = [[]]\r\nproductoCartesiano (xs:xss) = \r\n    [x:ys | x <- xs, ys <- productoCartesiano xss]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir (por recursi\u00f3n, plegado y comprensi\u00f3n)  el\r\n-- predicado \r\n--    comprueba :: [[Int]] -> Bool\r\n-- tal que tal que (comprueba xss) se verifica si cada elemento de la\r\n-- lista de listas xss contiene alg\u00fan n\u00famero par. Por ejemplo, \r\n--    comprueba [[1,2],[3,4,5],[8]]  ==  True\r\n--    comprueba [[1,2],[3,5]]        ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\ncompruebaR :: [[Int]] -> Bool\r\ncompruebaR [] = True\r\ncompruebaR (xs:xss) = tienePar xs && compruebaR xss\r\n\r\n-- (tienePar xs) se verifica si xs contiene alg\u00fan n\u00famero par. \r\ntienePar  :: [Int] -> Bool\r\ntienePar []     = False\r\ntienePar (x:xs) = even x || tienePar xs\r\n\r\n-- La definici\u00f3n por plegado es\r\ncompruebaP :: [[Int]] -> Bool\r\ncompruebaP = foldr f True\r\n    where f x y = tienePar x && y\r\n\r\n-- La definici\u00f3n por comprensi\u00f3n es\r\ncompruebaC :: [[Int]] -> Bool\r\ncompruebaC xss = and [or [even x | x <- xs] | xs <- xss]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir la funci\u00f3n\r\n--    pertenece :: Ord a => a -> [a] -> Bool\r\n-- tal que (pertenece x ys) se verifica si x pertenece a la lista\r\n-- ordenada creciente, finita o infinita, ys. Por ejemplo,\r\n--    pertenece 22 [1,3,22,34]  ==>  True\r\n--    pertenece 22 [1,3,34]     ==>  False\r\n--    pertenece 23 [1,3..]      ==>  True\r\n--    pertenece 22 [1,3..]      ==>  False\r\n-- ---------------------------------------------------------------------\r\n\r\npertenece :: Ord a => a -> [a] -> Bool\r\npertenece _ [] = False\r\npertenece x (y:ys) | x >  y    = pertenece x ys\r\n                   | x == y    = True\r\n                   | otherwise = False\r\n\r\n-- La definici\u00f3n de pertenece puede simplificarse\r\npertenece' :: Ord a => a -> [a] -> Bool\r\npertenece' x ys = elem x (takeWhile (<= x) ys)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    listasMayores :: [[Int]] -> [[Int]]\r\n-- tal que (listasMayores xss) es la lista de las listas de xss de mayor\r\n-- suma. Por ejemplo,\r\n--    *Main> listasMayores [[1,3,5],[2,7],[1,1,2],[3],[5]]\r\n--    [[1,3,5],[2,7]]\r\n-- ---------------------------------------------------------------------\r\n\r\nlistasMayores :: [[Int]] -> [[Int]]\r\nlistasMayores xss = [xs | xs <- xss, sum xs == m]\r\n    where m = maximum [sum xs | xs <- xss]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Definir la constante\r\n--    pares :: Int\r\n-- tal que pares es la lista de todos los pares de n\u00fameros enteros\r\n-- positivos ordenada seg\u00fan la suma de sus componentes y el valor de la\r\n-- primera componente. Por ejemplo, \r\n--    *Main> take 11 pares\r\n--    [(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(1,4),(2,3),(3,2),(4,1),(1,5)]\r\n-- ---------------------------------------------------------------------\r\n\r\npares :: [(Integer,Integer)]\r\npares = [(x,z-x) | z <- [1..], x <- [1..z-1]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Definir la constante\r\n--    paresDestacados :: [(Integer,Integer)]\r\n-- tal que paresDestadados es la lista de pares de n\u00fameros enteros (x,y)\r\n-- tales que 11 divide a x+13y y 13 divide a x+11y. \r\n-- ---------------------------------------------------------------------\r\n\r\nparesDestacados :: [(Integer,Integer)]\r\nparesDestacados = [(x,y) | (x,y) <- pares,\r\n                           mod (x+13*y) 11 == 0,\r\n                           mod (x+11*y) 13 == 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la constante\r\n--    parDestacadoConMenorSuma :: Integer\r\n-- tal que pardestacadoconmenorsuma es el par destacado con menor suma y\r\n-- calcular su valor y su posici\u00f3n en la lista pares.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n es\r\nparDestacadoConMenorSuma :: (Integer,Integer)\r\nparDestacadoConMenorSuma = head paresDestacados\r\n\r\n-- El valor es\r\n--   *Main> parDestacadoConMenorSuma\r\n--   (23,5)\r\n\r\n-- La posici\u00f3n es\r\n--    *Main> 1 + length (takeWhile (\/=parDestacadoConMenorSuma) pares)\r\n--    374\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Definir la funci\u00f3n\r\n--    limite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b\r\n-- tal que (limite f a) es el valor de f en el primer t\u00e9rmino x tal que \r\n-- para todo y entre x+1 y x+100, el valor absoluto de f(y)-f(x) es\r\n-- menor que a. Por ejemplo,\r\n--    limite (\\n -> (2*n+1)\/(n+5)) 0.001  ==  1.9900110987791344\r\n--    limite (\\n -> (1+1\/n)**n) 0.001     ==  2.714072874546881\r\n-- ---------------------------------------------------------------------\r\n\r\nlimite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b\r\nlimite f a = \r\n    head [f x | x <- [1..],\r\n                maximum [abs(f y - f x) | y <- [x+1..x+100]] < a]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 18. Definir la funci\u00f3n\r\n--    esLimite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b -> Bool\r\n-- tal que (esLimite f b a) se verifica si existe un x tal que para todo\r\n-- y entre x+1 y x+100, el valor absoluto de f(y)-b es menor que a. Por\r\n-- ejemplo, \r\n--    esLimite (\\n -> (2*n+1)\/(n+5)) 2 0.01     ==  True\r\n--    esLimite (\\n -> (1+1\/n)**n) (exp 1) 0.01  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nesLimite :: (Num a, Enum a, Num b, Ord b) => (a -> b) -> b -> b -> Bool\r\nesLimite f b a =\r\n    not (null [x | x <- [1..],\r\n                   maximum [abs(f y - b) | y <- [x+1..x+100]] < a])\r\n<\/pre>\n<p>Las soluciones de los ejercicios  de la relaci\u00f3n 17 son <\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                  \r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Nota. En los siguientes ejercicios se pide adaptar funciones sobre  \r\n-- lista a funciones sobre \u00e1rboles definidos por\r\n--    data Arbol a = Hoja | Nodo (Arbol a) a (Arbol a) deriving Show\r\n-- ---------------------------------------------------------------------\r\n\r\ndata Arbol a = Hoja \r\n             | Nodo (Arbol a) a (Arbol a) \r\n             deriving Show\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. La funci\u00f3n take est\u00e1 definida por\r\n--    take :: Int -> [a] -> [a]\r\n--    take 0            = []\r\n--    take (n+1) []     = []\r\n--    take (n+1) (x:xs) = x : take n xs\r\n-- Definir la funci\u00f3n \r\n--    takeArbol ::  Int -> Arbol a -> Arbol a\r\n-- tal que (takeArbol n t) es el sub\u00e1rbol de t de profundidad n. Por\r\n-- ejemplo,\r\n--    *Main> takeArbol 0 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja))\r\n--    Hoja\r\n--    *Main> takeArbol 1 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja))\r\n--    Nodo Hoja 6 Hoja\r\n--    *Main> takeArbol 2 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja))\r\n--    Nodo Hoja 6 (Nodo Hoja 7 Hoja)\r\n--    *Main> takeArbol 3 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja))\r\n--    Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja)\r\n--    *Main> takeArbol 4 (Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja))\r\n--    Nodo Hoja 6 (Nodo (Nodo Hoja 5 Hoja) 7 Hoja)\r\n-- ---------------------------------------------------------------------\r\n \r\ntakeArbol 0     _            = Hoja\r\ntakeArbol (n+1) Hoja         = Hoja\r\ntakeArbol (n+1) (Nodo l x r) = Nodo (takeArbol n l) x (takeArbol n r)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. La funci\u00f3n\r\n--    repeat :: a -> [a]\r\n-- est\u00e1 definida de forma que (repeat x) es la lista formada por\r\n-- infinitos elementos x. Por ejemplo,\r\n--    repeat 3  ==>  [3,3,3,3,3,3,3,3,3,3,3,3,3,...\r\n-- La definici\u00f3n de repeat es\r\n--    repeat x = xs where xs = x:xs\r\n-- Definir la funci\u00f3n\r\n--    repeatArbol :: a -> Arbol a\r\n-- tal que (repeatArbol x) es es \u00e1rbol con infinitos nodos x. Por\r\n-- ejemplo, \r\n--    Main> takeArbol 0 (repeatArbol 3)\r\n--    Hoja\r\n--    *Main> takeArbol 1 (repeatArbol 3)\r\n--    Nodo Hoja 3 Hoja\r\n--    *Main> takeArbol 2 (repeatArbol 3)\r\n--    Nodo (Nodo Hoja 3 Hoja) 3 (Nodo Hoja 3 Hoja)\r\n-- ---------------------------------------------------------------------\r\n\r\nrepeatArbol :: a -> Arbol a\r\nrepeatArbol x = Nodo t x t\r\n                where t = repeatArbol x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. La funci\u00f3n \r\n--    replicate :: Int -> a -> [a]\r\n-- est\u00e1 definida por \r\n--    replicate n = take n . repeat\r\n-- es tal que (replicate n x) es la lista de longitud n cuyos elementos\r\n-- son x. Por ejemplo,\r\n--    replicate 3 5  ==>  [5,5,5]\r\n-- Definir la funci\u00f3n \r\n--    replicateArbol :: Int -> a -> Arbol a\r\n-- tal que (replicate n x) es el \u00e1rbol de profundidad n cuyos nodos son\r\n-- x. Por ejemplo,\r\n--    *Main> replicateArbol 0 5\r\n--    Hoja\r\n--    *Main> replicateArbol 1 5\r\n--    Nodo Hoja 5 Hoja\r\n--    *Main> replicateArbol 2 5\r\n--    Nodo (Nodo Hoja 5 Hoja) 5 (Nodo Hoja 5 Hoja)\r\n-- ---------------------------------------------------------------------\r\n\r\nreplicateArbol :: Int -> a -> Arbol a\r\nreplicateArbol n = takeArbol n . repeatArbol\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Extender el procedimiento de decisi\u00f3n de tautolog\u00edas\r\n-- para incluir las disyunciones (Disj) y las equivalencias (Equi). Por\r\n-- ejemplo, \r\n--    *Main> esTautologia (Equi (Var 'A') (Disj (Var 'A') (Var 'A')))\r\n--    True\r\n--    *Main> esTautologia (Equi (Var 'A') (Disj (Var 'A') (Var 'B')))\r\n--    False\r\n-- Se incluye el c\u00f3digo del procedimiento visto en clase para que se\r\n-- extienda de manera adecuada.\r\n-- ---------------------------------------------------------------------\r\n\r\ndata FProp = Const Bool\r\n           | Var Char\r\n           | Neg FProp\r\n           | Conj FProp FProp\r\n           | Disj FProp FProp   -- A\u00f1adido\r\n           | Impl FProp FProp\r\n           | Equi FProp FProp   -- A\u00f1adido\r\n           deriving Show\r\n\r\ntype Interpretacion = [(Char, Bool)]\r\n\r\nvalor :: Interpretacion -> FProp -> Bool\r\nvalor _ (Const b)  = b\r\nvalor i (Var x)    = busca x i\r\nvalor i (Neg p)    = not (valor i p)\r\nvalor i (Conj p q) = valor i p && valor i q\r\nvalor i (Disj p q) = valor i p || valor i q    -- A\u00f1adido \r\nvalor i (Impl p q) = valor i p <= valor i q\r\nvalor i (Equi p q) = valor i p == valor i q    -- A\u00f1adido \r\n\r\nbusca :: Eq c => c -> [(c,v)] -> v\r\nbusca c t = head [v | (c',v) <- t, c == c']\r\n\r\nvariables :: FProp -> [Char]\r\nvariables (Const _)  = []\r\nvariables (Var x)    = [x]\r\nvariables (Neg p)    = variables p\r\nvariables (Conj p q) = variables p ++ variables q\r\nvariables (Disj p q) = variables p ++ variables q   -- A\u00f1adido\r\nvariables (Impl p q) = variables p ++ variables q\r\nvariables (Equi p q) = variables p ++ variables q   -- A\u00f1adido\r\n\r\ninterpretacionesVar :: Int -> [[Bool]]\r\ninterpretacionesVar 0     = [[]]\r\ninterpretacionesVar (n+1) = \r\n    map (False:) bss ++ map (True:) bss\r\n    where bss = interpretacionesVar n\r\n\r\ninterpretaciones :: FProp -> [Interpretacion]\r\ninterpretaciones p =  \r\n    map (zip vs) (interpretacionesVar (length vs))\r\n    where vs = nub (variables p)\r\n\r\nesTautologia :: FProp -> Bool\r\nesTautologia p = \r\n    and [valor i p | i <- interpretaciones p]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir la funci\u00f3n\r\n--    interpretacionesVar' :: Int -> [[Bool]]\r\n-- que sea equivalente a interpretacionesVar pero que en su definici\u00f3n\r\n-- use listas de comprensi\u00f3n en lugar de map. Por ejemplo,\r\n--    *Main> interpretacionesVar' 2\r\n--    [[False,False],[False,True],[True,False],[True,True]]\r\n-- ---------------------------------------------------------------------\r\n\r\ninterpretacionesVar' :: Int -> [[Bool]]\r\ninterpretacionesVar' 0     = [[]]\r\ninterpretacionesVar' (n+1) = \r\n    [False:bs | bs <- bss] ++ [True:bs | bs <- bss]\r\n    where bss = interpretacionesVar' n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir la funci\u00f3n\r\n--    interpretaciones' :: FProp -> [Interpretacion]\r\n-- que sea equivalente a interpretaciones pero que en su definici\u00f3n\r\n-- use listas de comprensi\u00f3n en lugar de map. Por ejemplo,\r\n--    *Main> interpretaciones' (Impl (Var 'A') (Conj (Var 'A') (Var 'B')))\r\n--    [[('A',False),('B',False)],\r\n--     [('A',False),('B',True)],\r\n--     [('A',True),('B',False)],\r\n--     [('A',True),('B',True)]]\r\n-- ---------------------------------------------------------------------\r\n\r\ninterpretaciones' :: FProp -> [Interpretacion]\r\ninterpretaciones' p =  \r\n    [zip vs i | i <- is] \r\n    where vs = nub (variables p)\r\n          is = interpretacionesVar (length vs)\r\n<\/pre>\n<p>Las soluciones de los ejercicios  de la relaci\u00f3n 18 son <\/p>\n<pre lang=\"haskell\">\r\n-- ----------------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                       --\r\n-- ----------------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.Char\r\nimport Data.List\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1 (Modelizaci\u00f3n de un juego de cartas)\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio resuelto. Definir el tipo de datos Palo para representar los cuatro\r\n-- palos de la baraja: picas, corazones, diamantes y tr\u00e9boles. Hacer que\r\n-- Palo sea instancia de Eq y Show.\r\n-- ----------------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n es\r\ndata Palo = Picas | Corazones | Diamantes | Treboles\r\n            deriving (Eq, Show)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Nota: Para que QuickCheck pueda generar elementos del tipo Palo se usa la \r\n-- siguiente funci\u00f3n.\r\n-- ----------------------------------------------------------------------------\r\n\r\ninstance Arbitrary Palo where\r\n    arbitrary = elements [Picas, Corazones, Diamantes, Treboles]\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio resuelto. Definir el tipo de dato Color para representar los\r\n-- colores de las cartas: rojo y negro. Hacer que Color sea instancia de Show. \r\n-- ----------------------------------------------------------------------------\r\n\r\ndata Color = Rojo | Negro\r\n             deriving Show\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.1. Definir la funci\u00f3n\r\n--    color :: Palo -> Color  \r\n-- tal que (color p) es el color del palo p. Por ejemplo,\r\n--    color Corazones ==>  Rojo\r\n-- Nota: Los corazones y los diamantes son rojos. Las picas y los\r\n-- tr\u00e9boles son negros.  \r\n-- ----------------------------------------------------------------------------\r\n\r\ncolor :: Palo -> Color\r\ncolor Picas     = Negro\r\ncolor Corazones = Rojo\r\ncolor Diamantes = Rojo\r\ncolor Treboles  = Negro\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio resuelto. Los valores de las cartas se dividen en los num\u00e9ricos\r\n-- (del 2 al 10) y las figuras (sota, reina, rey y as). Definir el tipo\r\n-- de datos Valor para representar los valores de las cartas. Hacer que\r\n-- Valor sea instancia de Eq y Show.\r\n--    Main> :type Sota\r\n--    Sota :: Valor\r\n--    Main> :type Reina\r\n--    Reina :: Valor\r\n--    Main> :type Rey\r\n--    Rey :: Valor\r\n--    Main> :type As\r\n--    As :: Valor\r\n--    Main> :type Numerico 3\r\n--    Numerico 3 :: Valor\r\n-- ----------------------------------------------------------------------------\r\n\r\ndata Valor = Numerico Int | Sota | Reina | Rey | As\r\n             deriving (Eq, Show)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Nota: Para que QuickCheck pueda generar elementos del tipo Valor se usa la \r\n-- siguiente funci\u00f3n.\r\n-- ----------------------------------------------------------------------------\r\n\r\ninstance Arbitrary Valor where\r\n  arbitrary =\r\n    oneof $\r\n      [ do return c\r\n      | c <- [Sota,Reina,Rey,As]\r\n      ] ++\r\n      [ do n <- choose (2,10)\r\n           return (Numerico n)\r\n      ] \r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.2. El orden de valor de las cartas (de mayor a menor) es\r\n-- as, rey, reina, sota y las num\u00e9ricas seg\u00fan su valor. Definir la funci\u00f3n \r\n--    mayor :: Valor -> Valor -> Bool  \r\n-- tal que (mayor x y) se verifica si la carta x es de mayor valor que\r\n-- la carta y. Por ejemplo, \r\n--    mayor Sota (Numerico 7)    ==>  True\r\n--    mayor (Numerico 10) Reina  ==>  False\r\n-- ----------------------------------------------------------------------------\r\n\r\nmayor :: Valor -> Valor -> Bool\r\nmayor _            As           = False\r\nmayor As           _            = True\r\nmayor _            Rey          = False\r\nmayor Rey          _            = True\r\nmayor _            Reina        = False\r\nmayor Reina        _            = True\r\nmayor _            Sota         = False\r\nmayor Sota         _            = True\r\nmayor (Numerico m) (Numerico n) = m > n\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.3. Comprobar con QuickCheck si dadas dos cartas, una\r\n-- siempre tiene mayor valor que la otra. En caso de que no se verifique,\r\n-- a\u00f1adir la menor precondici\u00f3n para que lo haga.\r\n-- ----------------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_MayorValor1 a b =\r\n    mayor a b || mayor b a\r\n\r\n-- La comprobaci\u00f3n es \r\n--    Main> quickCheck prop_MayorValor1\r\n--    Falsifiable, after 2 tests:\r\n--    Sota\r\n--    Sota\r\n-- que indica que la propiedad es falsa porque la sota no tiene mayor\r\n-- valor que la sota.  \r\n\r\n-- La precondici\u00f3n es que las cartas sean distintas:\r\nprop_MayorValor a b =\r\n    a \/= b ==> mayor a b || mayor b a\r\n\r\n-- La comprobaci\u00f3n es \r\n--    Main> quickCheck prop_MayorValor\r\n--    OK, passed 100 tests.\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio resuelto. Definir el tipo de datos Carta para representar las\r\n-- cartas mediante un valor y un palo. Hacer que Carta sea instancia de\r\n-- Eq y Show. Por ejemplo,\r\n--    Main> :type Carta Rey Corazones\r\n--    Carta Rey Corazones :: Carta\r\n--    Main> :type Carta (Numerico 4) Corazones\r\n--    Carta (Numerico 4) Corazones :: Carta\r\n-- ----------------------------------------------------------------------------\r\n\r\ndata Carta = Carta Valor Palo\r\n             deriving (Eq, Show)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.4. Definir la funci\u00f3n \r\n--    valor :: Carta -> Valor  \r\n-- tal que (valor c) es el valor de la carta c. Por ejemplo,\r\n--    valor (Carta Rey Corazones)  ==>  Rey  \r\n-- ----------------------------------------------------------------------------\r\n\r\nvalor :: Carta -> Valor\r\nvalor (Carta v p) = v\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.5. Definir la funci\u00f3n \r\n--    palo :: Carta -> Valor  \r\n-- tal que (palo c) es el palo de la carta c. Por ejemplo,\r\n--    palo (Carta Rey Corazones)  ==>  Corazones\r\n-- ----------------------------------------------------------------------------\r\n\r\npalo :: Carta -> Palo\r\npalo (Carta v p) = p\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Nota: Para que QuickCheck pueda generar elementos del tipo Carta se usa la \r\n-- siguiente funci\u00f3n.\r\n-- ----------------------------------------------------------------------------\r\n\r\ninstance Arbitrary Carta where\r\n    arbitrary =\r\n        do v <- arbitrary\r\n           p <- arbitrary\r\n           return (Carta v p)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.6. Definir la funci\u00f3n\r\n--    ganaCarta :: Palo -> Carta -> Carta -> Bool\r\n-- tal que (ganaCarta p c1 c2) se verifica si la carta c1 le gana a la\r\n-- carta c2 cuando el palo de triunfo es p (es decir, las cartas son del\r\n-- mismo palo y el valor de c1 es mayor que el de c2 o c1 es del palo de\r\n-- triunfo). Por ejemplo, \r\n--    ganaCarta Corazones (Carta Sota Picas) (Carta (Numerico 5) Picas)\r\n--    ==> True\r\n--    ganaCarta Corazones (Carta (Numerico 3) Picas) (Carta Sota Picas)\r\n--    ==> False\r\n--    ganaCarta Corazones (Carta (Numerico 3) Corazones) (Carta Sota Picas)\r\n--    ==> True\r\n--    ganaCarta Treboles (Carta (Numerico 3) Corazones) (Carta Sota Picas)\r\n--    ==> False\r\n-- ----------------------------------------------------------------------------\r\n\r\nganaCarta :: Palo -> Carta -> Carta -> Bool\r\nganaCarta triunfo c c' \r\n    | palo c == palo c' = mayor (valor c) (valor c')\r\n    | palo c == triunfo = True\r\n    | otherwise         = False\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.7. Comprobar con QuickCheck si dadas dos cartas, una\r\n-- siempre gana a la otra. \r\n-- ----------------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_GanaCarta t c1 c2 =\r\n    ganaCarta t c1 c2 || ganaCarta t c2 c1\r\n\r\n-- La comprobaci\u00f3n es \r\n--    Main> quickCheck prop_GanaCarta\r\n--    Falsifiable, after 0 tests:\r\n--    Diamantes\r\n--    Carta Rey Corazones\r\n--    Carta As Treboles\r\n-- que indica que la propiedad no se verifica ya que cuando el triunfo\r\n-- es diamantes, ni el rey de corazones le gana al as de tr\u00e9boles ni el\r\n-- as de tr\u00e9boles le gana al rey de corazones. \r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio resuelto. Definir el tipo de datos Mano para representar una\r\n-- mano en el juego de cartas. Una mano es vac\u00eda o se obtiene agregando\r\n-- una carta a una mano. Hacer Mano instancia de Eq y Show. Por ejemplo,\r\n--    Main> :type Agrega (Carta Rey Corazones) Vacia\r\n--    Agrega (Carta Rey Corazones) Vacia :: Mano\r\n-- ----------------------------------------------------------------------------\r\n\r\ndata Mano = Vacia | Agrega Carta Mano\r\n            deriving (Eq, Show)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Nota: Para que QuickCheck pueda generar elementos del tipo Mano se usa la \r\n-- siguiente funci\u00f3n.\r\n-- ----------------------------------------------------------------------------\r\n\r\ninstance Arbitrary Mano where\r\n    arbitrary =\r\n        do cs <- arbitrary\r\n           let mano []     = Vacia\r\n               mano (c:cs) = Agrega c (mano cs)\r\n           return (mano cs)\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.8. Una mano gana a una carta c si alguna carta de la mano\r\n-- le gana a c. Definir la funci\u00f3n \r\n--    ganaMano :: Palo -> Mano -> Carta -> Bool  \r\n-- tal que (gana t m c) se verifica si la mano m le gana a la carta c\r\n-- cuando el triunfo es t. Por ejemplo, \r\n--    ganaMano Picas (Agrega (Carta Sota Picas) Vacia) (Carta Rey Corazones)\r\n--    ==>  True\r\n--    ganaMano Picas (Agrega (Carta Sota Picas) Vacia) (Carta Rey Picas)\r\n--    ==>  False\r\n-- ----------------------------------------------------------------------------\r\n\r\nganaMano :: Palo -> Mano -> Carta -> Bool\r\nganaMano triunfo Vacia        c' = False\r\nganaMano triunfo (Agrega c m) c' = ganaCarta triunfo c c' || \r\n                                   ganaMano triunfo m c'\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.9. Definir la funci\u00f3n\r\n--    eligeCarta :: Palo -> Carta -> Mano -> Carta  \r\n-- tal que (eligeCarta t c1 m) es la mejor carta de la mano m frente a\r\n-- la carta c cuando el triunfo es t. La estrategia para elegir la mejor\r\n-- carta es la siguiente:\r\n-- * Si la mano s\u00f3lo tiene una carta, se elige dicha carta.\r\n-- * Si la primera carta de la mano es del palo de c1 y la mejor del\r\n--   resto no es del palo de c1, se elige la primera de la mano,\r\n-- * Si la primera carta de la mano no es del palo de c1 y la mejor\r\n--   del resto es del palo de c1, se elige la mejor del resto.\r\n-- * Si la primera carta de la mano le gana a c1 y la mejor del\r\n--   resto no le gana a c1, se elige la primera de la mano,\r\n-- * Si la mejor del resto le gana a c1 y la primera carta de la mano\r\n--   no le gana a c1, se elige la mejor del resto.\r\n-- * Si el valor de la primera carta es mayor que el de la mejor del\r\n--   resto, se elige la mejor del resto. \r\n-- * Si el valor de la primera carta no es mayor que el de la mejor\r\n--   del resto, se elige la primera carta.\r\n-- ----------------------------------------------------------------------------\r\n\r\neligeCarta :: Palo -> Carta -> Mano -> Carta\r\neligeCarta triunfo c1 (Agrega c Vacia) = c                        -- 1\r\neligeCarta triunfo c1 (Agrega c resto) \r\n  | palo c == palo c1 && palo c' \/= palo c1                  = c  -- 2\r\n  | palo c \/= palo c1 && palo c' == palo c1                  = c' -- 3\r\n  | ganaCarta triunfo c  c1 && not (ganaCarta triunfo c' c1) = c  -- 4\r\n  | ganaCarta triunfo c' c1 && not (ganaCarta triunfo c c1)  = c' -- 5\r\n  | mayor (valor c) (valor c')                               = c' -- 6\r\n  | otherwise                                                = c  -- 7\r\n where\r\n  c' = eligeCarta triunfo c1 resto\r\n\r\n-- ----------------------------------------------------------------------------\r\n-- Ejercicio 1.10. Comprobar con QuickCheck que si una mano es ganadora,\r\n-- entonces la carta elegida es ganadora.\r\n-- ----------------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_eligeCartaGanaSiEsPosible triunfo c m = \r\n    m \/= Vacia ==> \r\n    ganaMano triunfo m c == ganaCarta triunfo (eligeCarta triunfo c m) c\r\n\r\n-- La comprobaci\u00f3n es\r\n--    Main> quickCheck prop_eligeCartaGanaSiEsPosible\r\n--    Falsifiable, after 12 tests:\r\n--    Corazones\r\n--    Carta Rey Treboles\r\n--    Agrega (Carta (Numerico 6) Diamantes) \r\n--           (Agrega (Carta Sota Picas) \r\n--            (Agrega (Carta Rey Corazones) \r\n--             (Agrega (Carta (Numerico 10) Treboles) \r\n--              Vacia)))\r\n-- La carta elegida es el 10 de tr\u00e9boles (porque tiene que ser del mismo\r\n-- palo), aunque el mano hay una carta (el rey de corazones) que gana.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado la resoluci\u00f3n de ejercicios de las relaciones 16, 17 y 18 cuyas soluciones 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":[133],"tags":[27,287],"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\/1215"}],"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=1215"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1215\/revisions"}],"predecessor-version":[{"id":2932,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1215\/revisions\/2932"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1215"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1215"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1215"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}