{"id":5850,"date":"2017-11-22T11:45:13","date_gmt":"2017-11-22T10:45:13","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5850"},"modified":"2017-11-25T11:54:09","modified_gmt":"2017-11-25T10:54:09","slug":"i1m2017-ejercicios-de-tipos-de-datos-algebraicos-en-haskell-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-ejercicios-de-tipos-de-datos-algebraicos-en-haskell-1\/","title":{"rendered":"I1M2017: Ejercicios de tipos de datos algebraicos en Haskell (1)"},"content":{"rendered":"<p>En la segunda parte de la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-17\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los 3 primeros ejercicios de la relaci\u00f3n 9 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-17\/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<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la segunda parte de la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los 3 primeros ejercicios de la relaci\u00f3n 9 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":[265],"tags":[270,316],"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\/5850"}],"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=5850"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5850\/revisions"}],"predecessor-version":[{"id":5855,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5850\/revisions\/5855"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5850"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5850"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5850"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}