{"id":5626,"date":"2016-11-23T19:06:14","date_gmt":"2016-11-23T18:06:14","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5626"},"modified":"2016-11-25T19:07:29","modified_gmt":"2016-11-25T18:07:29","slug":"i1m2016-ejercicios-sobre-arboles-binarios-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2016-ejercicios-sobre-arboles-binarios-en-haskell\/","title":{"rendered":"I1M2016: Ejercicios sobre \u00e1rboles binarios 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 9 sobre \u00e1rboles binarios definidos como tipo 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 \u00e1rboles binarios\n-- definidos como tipos de datos algebraicos.\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-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\nimport Control.Monad\n\n-- ---------------------------------------------------------------------\n-- Nota. En los siguientes ejercicios se trabajar\u00e1 con los \u00e1rboles\n-- binarios definidos como sigue \n--    data Arbol a = H \n--                 | N a (Arbol a) (Arbol a)\n--                 deriving (Show, Eq)\n-- Por ejemplo, el \u00e1rbol\n--         9 \n--        \/ \\\n--       \/   \\\n--      3     7\n--     \/ \\  \n--    2   4 \n-- se representa por\n--    N 9 (N 3 (H 2) (H 4)) (H 7) \n-- ---------------------------------------------------------------------\n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a)\n             deriving (Show, Eq)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir la funci\u00f3n\n--    nHojas :: Arbol a -> Int\n-- tal que (nHojas x) es el n\u00famero de hojas del \u00e1rbol x. Por ejemplo,\n--    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3\n-- ---------------------------------------------------------------------\n\nnHojas :: Arbol a -> Int\nnHojas (H _)     = 1\nnHojas (N x i d) = nHojas i + nHojas d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir la funci\u00f3n\n--    nNodos :: Arbol a -> Int\n-- tal que (nNodos x) es el n\u00famero de nodos del \u00e1rbol x. Por ejemplo,\n--    nNodos (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  2\n-- ---------------------------------------------------------------------\n\nnNodos :: Arbol a -> Int\nnNodos (H _)     = 0\nnNodos (N x i d) = 1 + nNodos i + nNodos d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.3. Comprobar con QuickCheck que en todo \u00e1rbol binario el\n-- n\u00famero de sus hojas es igual al n\u00famero de sus nodos m\u00e1s uno.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_nHojas :: Arbol Int -> Bool\nprop_nHojas x =\n    nHojas x == nNodos x + 1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_nHojas\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Definir la funci\u00f3n\n--    profundidad :: Arbol a -> Int\n-- tal que (profundidad x) es la profundidad del \u00e1rbol x. Por ejemplo,\n--    profundidad (N 9 (N 3 (H 2) (H 4)) (H 7))              ==  2\n--    profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7))  ==  3\n--    profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4)))  ==  2\n-- ---------------------------------------------------------------------\n\nprofundidad :: Arbol a -> Int\nprofundidad (H _)     = 0\nprofundidad (N x i d) = 1 + max (profundidad i) (profundidad d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Comprobar con QuickCheck que para todo \u00e1rbol biario\n-- x, se tiene que\n--    nNodos x <= 2^(profundidad x) - 1\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_nNodosProfundidad :: Arbol Int -> Bool\nprop_nNodosProfundidad x =\n   nNodos x <= 2^(profundidad x) - 1\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_nNodosProfundidad\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Definir la funci\u00f3n\n--    preorden :: Arbol a -> [a]\n-- tal que (preorden x) es la lista correspondiente al recorrido\n-- preorden del \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a\n-- continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el\n-- sub\u00e1rbol derecho. Por ejemplo,\n--    preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]\n-- ---------------------------------------------------------------------\n\npreorden :: Arbol a -> [a]\npreorden (H x)     = [x]\npreorden (N x i d) = x : (preorden i ++ preorden d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Comprobar con QuickCheck que la longitud de la lista\n-- obtenida recorriendo un \u00e1rbol en sentido preorden es igual al n\u00famero\n-- de nodos del \u00e1rbol m\u00e1s el n\u00famero de hojas.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_length_preorden :: Arbol Int -> Bool\nprop_length_preorden x =\n   length (preorden x) == nNodos x + nHojas x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_length_preorden\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.3. Definir la funci\u00f3n\n--    postorden :: Arbol a -> [a]\n-- tal que (postorden x) es la lista correspondiente al recorrido\n-- postorden del \u00e1rbol x; es decir, primero recorre el sub\u00e1rbol\n-- izquierdo, a continuaci\u00f3n el sub\u00e1rbol derecho y, finalmente, la ra\u00edz\n-- del \u00e1rbol. Por ejemplo,\n--    postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]\n-- ---------------------------------------------------------------------\n\npostorden :: Arbol a -> [a]\npostorden (H x)     = [x]\npostorden (N x i d) = postorden i ++ postorden d ++ [x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.4. Definir, usando un acumulador, la funci\u00f3n\n--    preordenIt :: Arbol a -> [a]\n-- tal que (preordenIt x) es la lista correspondiente al recorrido\n-- preorden del \u00e1rbol x; es decir, primero visita la ra\u00edz del \u00e1rbol, a\n-- continuaci\u00f3n recorre el sub\u00e1rbol izquierdo y, finalmente, recorre el\n-- sub\u00e1rbol derecho. Por ejemplo,\n--    preordenIt (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]\n-- \n-- Nota: No usar (++) en la definici\u00f3n\n-- ---------------------------------------------------------------------\n\npreordenIt :: Arbol a -> [a]\npreordenIt x = preordenItAux x []\n    where preordenItAux (H x) xs     = x:xs\n          preordenItAux (N x i d) xs = \n              x : preordenItAux i (preordenItAux d xs)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.5. Comprobar con QuickCheck que preordenIt es equivalente\n-- a preorden. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_preordenIt :: Arbol Int -> Bool\nprop_preordenIt x =\n    preordenIt x == preorden x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_preordenIt\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. Definir la funci\u00f3n\n--    espejo :: Arbol a -> Arbol a\n-- tal que (espejo x) es la imagen especular del \u00e1rbol x. Por ejemplo,\n--    espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))\n-- ---------------------------------------------------------------------\n\nespejo :: Arbol a -> Arbol a\nespejo (H x)     = H x\nespejo (N x i d) = N x (espejo d) (espejo i)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Comprobar con QuickCheck que para todo \u00e1rbol x,\n--    espejo (espejo x) = x\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_espejo :: Arbol Int -> Bool\nprop_espejo x = \n    espejo (espejo x) == x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_espejo\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.3. Comprobar con QuickCheck que para todo \u00e1rbol binario\n-- x, se tiene que\n--    reverse (preorden (espejo x)) = postorden x\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_reverse_preorden_espejo :: Arbol Int -> Bool\nprop_reverse_preorden_espejo x =\n   reverse (preorden (espejo x)) == postorden x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_reverse_preorden_espejo\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.4. Comprobar con QuickCheck que para todo \u00e1rbol x,\n--    postorden (espejo x) = reverse (preorden x)\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_recorrido :: Arbol Int -> Bool\nprop_recorrido x =\n   postorden (espejo x) == reverse (preorden x)\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_recorrido\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. La funci\u00f3n take est\u00e1 definida por\n--    take :: Int -> [a] -> [a]\n--    take 0            = []\n--    take (n+1) []     = []\n--    take (n+1) (x:xs) = x : take n xs\n-- \n-- Definir la funci\u00f3n \n--    takeArbol ::  Int -> Arbol a -> Arbol a\n-- tal que (takeArbol n t) es el sub\u00e1rbol de t de profundidad n. Por\n-- ejemplo,\n--    takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9\n--    takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)\n--    takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)\n--    takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)\n-- ---------------------------------------------------------------------\n \ntakeArbol :: Int -> Arbol a -> Arbol a\ntakeArbol _ (H x)     = H x\ntakeArbol 0 (N x i d) = H x\ntakeArbol n (N x i d) = \n    N x (takeArbol (n-1) i) (takeArbol (n-1) d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Comprobar con QuickCheck que la profundidad de \n-- (takeArbol n x) es menor o igual que n, para todo n\u00famero natural n y\n-- todo \u00e1rbol x. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_takeArbol:: Int -> Arbol Int -> Property\nprop_takeArbol n x =\n    n >= 0 ==> profundidad (takeArbol n x) <= n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_takeArbol\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.1. La funci\u00f3n\n--    repeat :: a -> [a]\n-- est\u00e1 definida de forma que (repeat x) es la lista formada por\n-- infinitos elementos x. Por ejemplo,\n--    repeat 3  ==  [3,3,3,3,3,3,3,3,3,3,3,3,3,...\n-- La definici\u00f3n de repeat es\n--    repeat x = xs where xs = x:xs\n-- \n-- Definir la funci\u00f3n\n--    repeatArbol :: a -> Arbol a\n-- tal que (repeatArbol x) es es \u00e1rbol con infinitos nodos x. Por\n-- ejemplo, \n--    takeArbol 0 (repeatArbol 3) == H 3\n--    takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)\n--    takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))\n-- ---------------------------------------------------------------------\n\nrepeatArbol :: a -> Arbol a\nrepeatArbol x = N x t t\n    where t = repeatArbol x\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.2. La funci\u00f3n \n--    replicate :: Int -> a -> [a]\n-- est\u00e1 definida por \n--    replicate n = take n . repeat\n-- es tal que (replicate n x) es la lista de longitud n cuyos elementos\n-- son x. Por ejemplo,\n--    replicate 3 5  ==  [5,5,5]\n-- \n-- Definir la funci\u00f3n \n--    replicateArbol :: Int -> a -> Arbol a\n-- tal que (replicate n x) es el \u00e1rbol de profundidad n cuyos nodos son\n-- x. Por ejemplo,\n--    replicateArbol 0 5  ==  H 5\n--    replicateArbol 1 5  ==  N 5 (H 5) (H 5)\n--    replicateArbol 2 5  ==  N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))\n-- ---------------------------------------------------------------------\n\nreplicateArbol :: Int -> a -> Arbol a\nreplicateArbol n = takeArbol n . repeatArbol\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.3. Comprobar con QuickCheck que el n\u00famero de hojas de \n-- (replicateArbol n x) es 2^n, para todo n\u00famero natural n\n--\n-- Nota. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como\n-- se indica a continuaci\u00f3n\n--    quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_replicateArbol :: Int -> Int -> Property\nprop_replicateArbol n x =\n    n >= 0 ==> nHojas (replicateArbol n x) == 2^n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Definir la funci\u00f3n\n--    mapArbol :: (a -> a) -> Arbol a -> Arbol a\n-- tal que (mapArbol f x) es el \u00e1rbol obtenido aplic\u00e1ndole a cada nodo de\n-- x la funci\u00f3n f. Por ejemplo,\n--    ghci> mapArbol (*2) (N 9 (N 3 (H 2) (H 4)) (H 7)) \n--    N 18 (N 6 (H 4) (H 8)) (H 14)\n-- ---------------------------------------------------------------------\n\nmapArbol :: (a -> a) -> Arbol a -> Arbol a\nmapArbol f (H x)     = H (f x)\nmapArbol f (N x i d) = N (f x) (mapArbol f i) (mapArbol f d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Comprobar con QuickCheck que \n--    (mapArbol (1+)) . espejo = espejo . (mapArbol (1+))\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_mapArbol_espejo :: Arbol Int -> Bool\nprop_mapArbol_espejo x =\n    ((mapArbol (1+)) . espejo) x == (espejo . (mapArbol (1+))) x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_mapArbol_espejo\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.3. Comprobar con QuickCheck que\n--    (map (1+)) . preorden = preorden . (mapArbol (1+)) \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_map_preorden :: Arbol Int -> Bool\nprop_map_preorden x =\n    ((map (1+)) . preorden) x == (preorden . (mapArbol (1+))) x\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_map_preorden\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Nota. Para comprobar propiedades de \u00e1rboles con QuickCheck se\n-- utilizar\u00e1 el siguiente generador.\n-- ---------------------------------------------------------------------\n\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbol\n    where\n      arbol 0       = liftM H arbitrary \n      arbol n | n>0 = oneof [liftM H arbitrary,\n                             liftM3 N arbitrary subarbol subarbol]\n                      where subarbol = arbol (div n 2)\n\n<\/pre>\n<p>El c\u00f3digo correspondiente se encuentra en <a href=\"http:\/\/bit.ly\/1Muley2\">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 9 sobre \u00e1rboles binarios definidos como tipo 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":[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\/5626"}],"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=5626"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5626\/revisions"}],"predecessor-version":[{"id":5627,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5626\/revisions\/5627"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5626"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5626"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5626"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}