{"id":392,"date":"2014-07-03T07:00:26","date_gmt":"2014-07-03T05:00:26","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=392"},"modified":"2014-12-27T13:44:25","modified_gmt":"2014-12-27T11:44:25","slug":"renombramiento-de-un-arbol","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/renombramiento-de-un-arbol\/","title":{"rendered":"Renombramiento de un \u00e1rbol"},"content":{"rendered":"<pre lang=\"text\">\n-- Los \u00e1rboles binarios se pueden representar mediante el tipo Arbol definido\n-- por\n--    data Arbol a = H a \n--                 | N a (Arbol a) (Arbol a)\n--                 deriving Show\n-- Por ejemplo, el \u00e1rbol\n--         \"C\"\n--         \/ \\ \n--        \/   \\\n--       \/     \\\n--     \"B\"     \"A\"\n--     \/ \\     \/ \\\n--   \"A\" \"B\" \"B\" \"C\" \n-- se puede definir por \n--    ej1 :: Arbol String\n--    ej1 = N \"C\" (N \"B\" (H \"A\") (H \"B\")) (N \"A\" (H \"B\") (H \"C\"))\n--\n-- Definir la funci\u00f3n\n--    renombraArbol :: Arbol t -> Arbol Int\n-- tal que (renombraArbol a) es el \u00e1rbol obtenido sustituyendo el valor\n-- de los nodos y hojas por n\u00fameros tales que tengan el mismo valor si y\n-- s\u00f3lo si coincide su contenido. Por ejemplo,\n--    ghci> renombraArbol ej1\n--    N 2 (N 1 (H 0) (H 1)) (N 0 (H 1) (H 2))\n-- Gr\u00e1ficamente, \n--          2 \n--         \/ \\ \n--        \/   \\\n--       \/     \\\n--      1       0 \n--     \/ \\     \/ \\\n--    0   1   1   2 \n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List \n\ndata Arbol a = H a\n             | N a (Arbol a) (Arbol a) \n             deriving (Show, Eq)\n\nej1 :: Arbol String\nej1 = N \"C\" (N \"B\" (H \"A\") (H \"B\")) (N \"A\" (H \"B\") (H \"C\"))\n\nrenombraArbol :: Ord t => Arbol t -> Arbol Int\nrenombraArbol a = aux a\n    where ys            = valores a\n          aux (H x)     = H (posicion x ys)\n          aux (N x i d) = N (posicion x ys) (aux i) (aux d) \n\n-- (valores a) es la lista de los valores en los nodos y las hojas del\n-- \u00e1rbol a. Por ejemplo,\n--    valores ej1  ==  [\"A\",\"B\",\"C\"]\nvalores :: Ord a => Arbol a -> [a]\nvalores a = sort (nub (aux a))\n    where aux (H x)     = [x]\n          aux (N x i d) = x : (aux i ++ aux d)\n\n-- (posicion x ys) es la posici\u00f3n de x en ys. Por ejemplo.\n--    posicion 7 [5,3,7,8]  ==  2\nposicion :: Eq a => a -> [a] -> Int\nposicion x ys = head [n | (y,n) <- zip ys [0..], y == x]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>&#8212; Los \u00e1rboles binarios se pueden representar mediante el tipo Arbol definido &#8212; por &#8212; data Arbol a = H a &#8212; | N a (Arbol a) (Arbol a) &#8212; deriving Show &#8212; Por ejemplo, el \u00e1rbol &#8212; \u00abC\u00bb &#8212; \/ \\ &#8212; \/ \\ &#8212; \/ \\ &#8212; \u00abB\u00bb \u00abA\u00bb &#8212; \/ \\ \/&#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":[7],"tags":[8,24,6,14,133],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/392"}],"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=392"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/392\/revisions"}],"predecessor-version":[{"id":672,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/392\/revisions\/672"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=392"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=392"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=392"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}