Menu Close

Árboles cuyas ramas cumplen una propiedad

Los árboles se pueden representar mediante el siguiente tipo de dato

   data Arbol a = N a [Arbol a]
     deriving Show

Por ejemplo, los árboles

      -1           1            1
      / \         / \          /|\
     2   3      -2   3        / | \  
    / \          |          -2  7  3  
   4   5        -4          / \      
                           4   5

se representan por

   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

   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,

   todasDesdeAlguno (>0) ej1 == True
   todasDesdeAlguno (>0) ej2 == False
   todasDesdeAlguno (>0) ej3 == True

Soluciones

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

6 soluciones de “Árboles cuyas ramas cumplen una propiedad

  1. frahidzam
    ramas :: Arbol a -> [[a]]
    ramas (N x []) = [[x]]
    ramas (N x as) = [x:xs | a <- as, xs <- ramas a]
     
    todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool
    todasDesdeAlguno p a =  all p  (map last (ramas a))
  2. frahidzam
    ultimos :: Arbol a -> [a]
    ultimos (N x []) = [x]
    ultimos (N _ as) = concat [ultimos a | a <- as]
     
    todasDesdeAlguno2 :: (a -> Bool) -> Arbol a -> Bool
    todasDesdeAlguno2 p a = and [p x | x <- ultimos a]
  3. adogargon
    todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool
    todasDesdeAlguno p (N x []) = p x
    todasDesdeAlguno p (N x xs) | arbolprop p (N x xs) = True
                                | otherwise = and [ todasDesdeAlguno p t | t <- xs]
     
    arbolprop :: (a -> Bool) -> Arbol a -> Bool
    arbolprop p (N a []) = p a
    arbolprop p (N a xs) = p a && and [arbolprop p b | b <- xs ]
  4. luipromor
    todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool
    todasDesdeAlguno p (N a [] ) = p a
    todasDesdeAlguno p (N a xs) = p a || and [ todasDesdeAlguno p i | i <- xs]
    • guicabgod

      Falla en árboles como el siguiente

      λ> todasDesdeAlguno even (N 2 [N 3 []])
      True
  5. javmarcha1
    todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool
    todasDesdeAlguno p (N x xs) =
      and [ (takeWhile (==True) (map p ys)) /= []
          | ys <- map reverse (ramas (N x xs))]
     
    ramas :: Arbol a -> [[a]]
    ramas (N x []) = [[x]]
    ramas (N x as) = [x:xs | a <- as, xs <- ramas a]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.