{"id":6951,"date":"2022-04-18T07:00:03","date_gmt":"2022-04-18T05:00:03","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6951"},"modified":"2022-04-30T16:22:37","modified_gmt":"2022-04-30T14:22:37","slug":"emparejamiento-de-arboles","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/emparejamiento-de-arboles\/","title":{"rendered":"Emparejamiento de \u00e1rboles"},"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, Eq)\n<\/pre>\n<p>Por ejemplo, los \u00e1rboles<\/p>\n<pre lang=\"text\">\n     1               3\n    \/ \\             \/|\\\n   6   3           \/ | \\\n       |          5  4  7\n       5          |     \/\\\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 6 [],N 3 [N 5 []]]\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   emparejaArboles :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c\n<\/pre>\n<p>tal que <code>(emparejaArboles f a1 a2)<\/code> es el \u00e1rbol obtenido aplicando la funci\u00f3n <code>f<\/code> a los elementos de los \u00e1rboles <code>a1<\/code> y <code>a2<\/code> que se encuentran en la misma posici\u00f3n. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   \u03bb> emparejaArboles (+) (N 1 [N 2 [], N 3[]]) (N 1 [N 6 []])\n   N 2 [N 8 []]\n   \u03bb> emparejaArboles (+) ej1 ej2\n   N 4 [N 11 [],N 7 []]\n   \u03bb> emparejaArboles (+) ej1 ej1\n   N 2 [N 12 [],N 6 [N 10 []]]\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nmodule Emparejamiento_de_arboles where\n\nimport Data.Tree (Tree (..))\nimport Control.Monad.Zip (mzipWith)\nimport Test.QuickCheck (Arbitrary, Gen, arbitrary, sublistOf, sized, quickCheck)\n\ndata Arbol a = N a [Arbol a]\n  deriving (Show, Eq)\n\nej1, ej2 :: Arbol Int\nej1 = N 1 [N 6 [],N 3 [N 5 []]]\nej2 = N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nemparejaArboles1 :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c\nemparejaArboles1 f (N x xs) (N y ys) =\n  N (f x y) (zipWith (emparejaArboles1 f) xs ys)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nemparejaArboles2 :: (a -> b -> c) -> Arbol a -> Arbol b -> Arbol c\nemparejaArboles2 f x y =\n  treeAarbol (mzipWith f (arbolAtree x) (arbolAtree y))\n\narbolAtree :: Arbol a -> Tree a\narbolAtree (N x xs) = Node x (map arbolAtree xs)\n\ntreeAarbol :: Tree a -> Arbol a\ntreeAarbol (Node x xs) = N x (map treeAarbol xs)\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- (arbolArbitrario n) es un \u00e1rbol aleatorio de orden n. Por ejemplo,\n--    \u03bb> generate (arbolArbitrario 5 :: Gen (Arbol Int))\n--    N (-26) [N 8 [N 6 [N 11 []]],N 7 []]\n--    \u03bb> generate (arbolArbitrario 5 :: Gen (Arbol Int))\n--    N 1 []\n--    \u03bb> generate (arbolArbitrario 5 :: Gen (Arbol Int))\n--    N (-19) [N (-11) [],N 25 [],N 19 [N (-27) [],N (-19) [N 17 []]]]\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_emparejaArboles :: Arbol Int -> Arbol Int -> Bool\nprop_emparejaArboles x y =\n  emparejaArboles1 (+) x y == emparejaArboles2 (+) x y &&\n  emparejaArboles1 (*) x y == emparejaArboles2 (*) x y\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_emparejaArboles\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> a500 <- generate (arbolArbitrario 500 :: Gen (Arbol Int))\n--    \u03bb> emparejaArboles1 (+) a500 a500 == emparejaArboles1 (+) a500 a500\n--    True\n--    (1.92 secs, 1,115,813,352 bytes)\n--    \u03bb> emparejaArboles2 (+) a500 a500 == emparejaArboles2 (+) a500 a500\n--    True\n--    (3.28 secs, 2,212,257,928 bytes)\n--\n--    \u03bb> b500 = arbolAtree a500\n--    \u03bb> mzipWith (+) b500 b500 == mzipWith (+) b500 b500\n--    True\n--    (0.21 secs, 563,503,112 bytes)\n<\/pre>\n<p>El c\u00f3digo se encuentra en <a href=\"https:\/\/github.com\/jaalonso\/Exercitium\/blob\/main\/src\/Emparejamiento_de_arboles.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\/RWO2_fadW4g\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe><\/p>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\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, Eq) Por ejemplo, los \u00e1rboles 1 3 \/ \\ \/|\\ 6 3 \/ | \\ | 5 4 7 5 | \/\\ 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":[483,548,547,10,437,549,11,371,518,485,146,76],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6951"}],"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=6951"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6951\/revisions"}],"predecessor-version":[{"id":6989,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6951\/revisions\/6989"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6951"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6951"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6951"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}