{"id":4870,"date":"2019-03-26T06:00:01","date_gmt":"2019-03-26T04:00:01","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4870"},"modified":"2019-04-02T06:35:19","modified_gmt":"2019-04-02T04:35:19","slug":"arboles-cuyas-ramas-cumplen-una-propiedad","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/arboles-cuyas-ramas-cumplen-una-propiedad\/","title":{"rendered":"\u00c1rboles cuyas ramas cumplen una propiedad"},"content":{"rendered":"

Los \u00e1rboles se pueden representar mediante el siguiente tipo de dato<\/p>\n

 \n   data Arbol a = N a [Arbol a]\n     deriving Show\n<\/pre>\n
Por ejemplo, los \u00e1rboles<\/p>\n
 \n      -1           1            1\n      \/ \\         \/ \\          \/|\\\n     2   3      -2   3        \/ | \\  \n    \/ \\          |          -2  7  3  \n   4   5        -4          \/ \\      \n                           4   5     \n<\/pre>\n
se representan por<\/p>\n
 \n   ej1, ej2, ej3 :: Arbol Int\n   ej1 = N (-1) [N 2 [N 4 [], N 5 []], N 3 []]\n   ej2 = N 1 [N (-2) [N (-4) []], N 3 []]\n   ej3 = N 1 [N (-2) [N 4 [], N 5 []], N 7 [], N 3 []]\n<\/pre>\n
Definir la funci\u00f3n<\/p>\n
 \n   todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool\n<\/pre>\n
tal que (todasDesdeAlguno p ar) se verifica si para toda rama existe un elemento a partir del cual todos los elementos de la rama verifican la propiedad p. Por ejemplo,<\/p>\n
 \n   todasDesdeAlguno (>0) ej1 == True\n   todasDesdeAlguno (>0) ej2 == False\n   todasDesdeAlguno (>0) ej3 == True\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.List (tails)\n\ndata Arbol a = N a [Arbol a]\n  deriving Show\n\nej1, ej2, ej3 :: Arbol Int\nej1 = N (-1) [N 2 [N 4 [], N 5 []], N 3 []]\nej2 = N 1 [N (-2) [N (-4) []], N 3 []]\nej3 = N 1 [N (-2) [N 4 [], N 5 []], N 7 [], N 3 []]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntodasDesdeAlguno :: (b -> Bool) -> Arbol b -> Bool\ntodasDesdeAlguno p a = all (desdeAlguno p) (ramas a)\n\n-- (desdeAlguno p xs) se verifica si la propiedad xs tiene un elementemo\n-- a partir del cual todos los siguientes cumplen la propiedad p. Por\n-- ejemplo, \n--    desdeAlguno (>0) [-1,2,4]   ==  True\n--    desdeAlguno (>0) [1,-2,-4]  ==  False\n--    desdeAlguno (>0) [1,-2,4]   ==  True\n\n-- 1\u00aa definici\u00f3n de desdeAlguno\ndesdeAlguno1 :: (a -> Bool) -> [a] -> Bool\ndesdeAlguno1 p xs =\n  not (null (takeWhile p (reverse xs)))\n\n-- 2\u00aa definici\u00f3n de desdeAlguno\ndesdeAlguno2 :: (a -> Bool) -> [a] -> Bool\ndesdeAlguno2 p xs = any (all p) (init (tails xs))\n\n-- Comparaci\u00f3n de eficiencia:\n--    \u03bb> desdeAlguno1 (>10^7) [1..1+10^7]\n--    True\n--    (4.36 secs, 960,101,896 bytes)\n--    \u03bb> desdeAlguno2 (>10^7) [1..1+10^7]\n--    True\n--    (5.62 secs, 3,600,101,424 bytes)\n\n-- Usaremos la 1\u00aa definici\u00f3n de desdeAlguno\ndesdeAlguno :: (a -> Bool) -> [a] -> Bool\ndesdeAlguno = desdeAlguno1\n\n-- (ramas a) es la lista de las ramas de a. Por ejemplo,\n--    ramas ej1  ==  [[-1,2,4],[-1,2,5],[-1,3]]\n--    ramas ej2  ==  [[1,-2,-4],[1,3]]\n--    ramas ej3  ==  [[1,-2,4],[1,-2,5],[1,7],[1,3]]\nramas :: Arbol a -> [[a]]\nramas (N x []) = [[x]]\nramas (N x as) = map (x:) (concatMap ramas as)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntodasDesdeAlguno2 :: (b -> Bool) -> Arbol b -> Bool\ntodasDesdeAlguno2 p (N x []) = p x\ntodasDesdeAlguno2 p (N _ as) = all (todasDesdeAlguno2 p) as \n<\/pre>\n
Pensamiento<\/h4>\n
\nPor dar al viento trabajo,
\ncos\u00eda con hilo doble
\nlas hojas secas del \u00e1rbol.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Los \u00e1rboles se pueden representar mediante el siguiente tipo de dato data Arbol a = N a [Arbol a] deriving Show Por ejemplo, los \u00e1rboles -1 1 1 \/ \\ \/ \\ \/|\\ 2 3 -2 3 \/ | \\ \/ \\ | -2 7 3 4 5 -4 \/ \\ 4 5 se representan…<\/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":[4],"tags":[41,163,269,58,285,10,181,11,6,32,75],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4870"}],"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=4870"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4870\/revisions"}],"predecessor-version":[{"id":4904,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4870\/revisions\/4904"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4870"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4870"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4870"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}