{"id":6761,"date":"2022-03-15T06:00:08","date_gmt":"2022-03-15T04:00:08","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6761"},"modified":"2022-03-26T17:22:02","modified_gmt":"2022-03-26T15:22:02","slug":"ramas-de-un-arbol","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/ramas-de-un-arbol\/","title":{"rendered":"Ramas de un \u00e1rbol"},"content":{"rendered":"<p>Los \u00e1rboles se pueden representar mediante el siguiente tipo de datos<\/p>\n<pre lang=\"text\">\n   data Arbol a = N a [Arbol a]\n     deriving Show\n<\/pre>\n<p>Por ejemplo, los \u00e1rboles<\/p>\n<pre lang=\"text\">\n     1               3\n    \/ \\             \/|\\\n   2   3           \/ | \\\n       |          5  4  7\n       4          |     \/\\\n                  6    2  1\n<\/pre>\n<p>se representan por<\/p>\n<pre lang=\"text\">\n   ej1, ej2 :: Arbol Int\n   ej1 = N 1 [N 2 [],N 3 [N 4 []]]\n   ej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]\n<\/pre>\n<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   ramas :: Arbol b -> [[b]]\n<\/pre>\n<p>tal que (ramas a) es la lista de las ramas del \u00e1rbol a. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   ramas ej1  ==  [[1,2],[1,3,4]]\n   ramas ej2  ==  [[3,5,6],[3,4],[3,7,2],[3,7,1]]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Test.QuickCheck\n\ndata Arbol a = N a [Arbol a]\n  deriving Show\n\nej1, ej2 :: Arbol Int\nej1 = N 1 [N 2 [],N 3 [N 4 []]]\nej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]\n\n-- 1\u00aa soluci\u00f3n\nramas1 :: Arbol b -> [[b]]\nramas1 (N x []) = [[x]]\nramas1 (N x as) = [x : xs | a <- as, xs <- ramas1 a]\n\n-- 2\u00aa soluci\u00f3n\nramas2 :: Arbol b -> [[b]]\nramas2 (N x []) = [[x]]\nramas2 (N x as) = concat (map (map (x:)) (map ramas2 as))\n\n-- 3\u00aa soluci\u00f3n\nramas3 :: Arbol b -> [[b]]\nramas3 (N x []) = [[x]]\nramas3 (N x as) = concat (map (map (x:) . ramas3) as)\n\n-- 4\u00aa soluci\u00f3n\nramas4 :: Arbol b -> [[b]]\nramas4 (N x []) = [[x]]\nramas4 (N x as) = concatMap (map (x:) . ramas4) as\n\n-- 5\u00aa soluci\u00f3n\nramas5 :: Arbol a -> [[a]]\nramas5 (N x []) = [[x]]\nramas5 (N x xs) = map ramas5 xs >>= map (x:)\n\n-- Comprobaci\u00f3n de la equivalencia de las definiciones\n-- ===================================================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n--    \u03bb> sample (arbolArbitrario 4 :: Gen (Arbol Int))\n--    N 0 [N 0 []]\n--    N 1 [N 1 [N (-2) [N (-1) [N (-1) [N (-1) [N 1 []]]]]],N (-1) [N 2 []]]\n--    N 1 [N (-2) [],N 0 [N (-4) [N (-2) []]]]\n--    N (-4) [N 1 [],N 0 [N 6 [N (-4) []],N 2 [N 3 []]]]\n--    N (-7) [N (-7) [N (-3) []]]\n--    N (-2) [N (-8) []]\n--    N (-3) [N 3 [N 2 []]]\n--    N (-12) [N 5 [],N 0 []]\n--    N 14 [N 13 [N (-12) []],N 11 [],N 8 [N (-13) []]]\n--    N (-12) [N (-6) [N 16 [N (-14) [N (-1) []]]]]\n--    N (-5) []\narbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a)\narbolArbitrario n = do\n  x  <- arbitrary\n  ms <- sublistOf [0 .. n `div` 2]\n  as <- mapM arbolArbitrario ms\n  return (N x as)\n\n-- Arbol es una subclase de Arbitraria\ninstance Arbitrary a => Arbitrary (Arbol a) where\n  arbitrary = sized arbolArbitrario\n\n-- La propiedad es\nprop_arbol :: Arbol Int -> Bool\nprop_arbol a =\n  all (== ramas1 a)\n      [ramas2 a,\n       ramas3 a,\n       ramas4 a,\n       ramas5 a]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_arbol\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> ej600 <- generate (arbolArbitrario 600 :: Gen (Arbol Int))\n--    \u03bb> length (ramas1 ej600)\n--    1262732\n--    (1.92 secs, 1,700,238,488 bytes)\n--    \u03bb> length (ramas2 ej600)\n--    1262732\n--    (1.94 secs, 2,549,877,280 bytes)\n--    \u03bb> length (ramas3 ej600)\n--    1262732\n--    (1.99 secs, 2,446,508,472 bytes)\n--    \u03bb> length (ramas4 ej600)\n--    1262732\n--    (1.67 secs, 2,090,469,104 bytes)\n--    \u03bb> length (ramas5 ej600)\n--    1262732\n--    (1.66 secs, 2,112,198,232 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Ramas_de_un_arbol.hs\">GitHub<\/a>.<\/p>\n<p>La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n<p><iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/Bj0jTH77k2k\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Los \u00e1rboles se pueden representar mediante el siguiente tipo de datos data Arbol a = N a [Arbol a] deriving Show Por ejemplo, los \u00e1rboles 1 3 \/ \\ \/|\\ 2 3 \/ | \\ | 5 4 7 4 | \/\\ 6 2 1 se representan por ej1, ej2 :: Arbol Int ej1 =&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[2],"tags":[8,11,6,133],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6761"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=6761"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6761\/revisions"}],"predecessor-version":[{"id":6840,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6761\/revisions\/6840"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6761"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6761"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6761"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}