Árboles cuyas ramas cumplen una propiedad
Los árboles se pueden representar mediante el siguiente tipo de dato
|
1 2 |
data Arbol a = N a [Arbol a] deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
-1 1 1 / \ / \ /|\ 2 3 -2 3 / | \ / \ | -2 7 3 4 5 -4 / \ 4 5 |
se representan por
|
1 2 3 4 |
ej1, ej2, ej3 :: Arbol Int ej1 = N (-1) [N 2 [N 4 [], N 5 []], N 3 []] ej2 = N 1 [N (-2) [N (-4) []], N 3 []] ej3 = N 1 [N (-2) [N 4 [], N 5 []], N 7 [], N 3 []] |
Definir la función
|
1 |
todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool |
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,
|
1 2 3 |
todasDesdeAlguno (>0) ej1 == True todasDesdeAlguno (>0) ej2 == False todasDesdeAlguno (>0) ej3 == True |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
import Data.List (tails) data Arbol a = N a [Arbol a] deriving Show ej1, ej2, ej3 :: Arbol Int ej1 = N (-1) [N 2 [N 4 [], N 5 []], N 3 []] ej2 = N 1 [N (-2) [N (-4) []], N 3 []] ej3 = N 1 [N (-2) [N 4 [], N 5 []], N 7 [], N 3 []] -- 1ª solución -- =========== todasDesdeAlguno :: (b -> Bool) -> Arbol b -> Bool todasDesdeAlguno p a = all (desdeAlguno p) (ramas a) -- (desdeAlguno p xs) se verifica si la propiedad xs tiene un elementemo -- a partir del cual todos los siguientes cumplen la propiedad p. Por -- ejemplo, -- desdeAlguno (>0) [-1,2,4] == True -- desdeAlguno (>0) [1,-2,-4] == False -- desdeAlguno (>0) [1,-2,4] == True -- 1ª definición de desdeAlguno desdeAlguno1 :: (a -> Bool) -> [a] -> Bool desdeAlguno1 p xs = not (null (takeWhile p (reverse xs))) -- 2ª definición de desdeAlguno desdeAlguno2 :: (a -> Bool) -> [a] -> Bool desdeAlguno2 p xs = any (all p) (init (tails xs)) -- Comparación de eficiencia: -- λ> desdeAlguno1 (>10^7) [1..1+10^7] -- True -- (4.36 secs, 960,101,896 bytes) -- λ> desdeAlguno2 (>10^7) [1..1+10^7] -- True -- (5.62 secs, 3,600,101,424 bytes) -- Usaremos la 1ª definición de desdeAlguno desdeAlguno :: (a -> Bool) -> [a] -> Bool desdeAlguno = desdeAlguno1 -- (ramas a) es la lista de las ramas de a. Por ejemplo, -- ramas ej1 == [[-1,2,4],[-1,2,5],[-1,3]] -- ramas ej2 == [[1,-2,-4],[1,3]] -- ramas ej3 == [[1,-2,4],[1,-2,5],[1,7],[1,3]] ramas :: Arbol a -> [[a]] ramas (N x []) = [[x]] ramas (N x as) = map (x:) (concatMap ramas as) -- 2ª solución -- =========== todasDesdeAlguno2 :: (b -> Bool) -> Arbol b -> Bool todasDesdeAlguno2 p (N x []) = p x todasDesdeAlguno2 p (N _ as) = all (todasDesdeAlguno2 p) as |
Pensamiento
Por dar al viento trabajo,
cosía con hilo doble
las hojas secas del árbol.Antonio Machado
Falla en árboles como el siguiente