Árboles con todas sus ramas con algún elemento que cumple una propiedad
En lógica temporal, la expresión AFp significa que en algún momento en el futuro se cumple la propiedad p. Trasladado a su interpretación en forma de árbol lo que quiere decir es que en todas las ramas (desde la raíz hasta una hoja) hay un nodo que cumple la propiedad p.
Consideramos el siguiente tipo algebraico de los árboles binarios:
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show,Eq) |
y el siguiente árbol
|
1 2 |
a1 :: Arbol Int a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8) |
En este árbol se cumple (AF par); es decir, en todas las ramas hay un número par; pero no se cumple (AF primo); es decir, hay ramas en las que no hay ningún número primo. Donde una rama es la secuencia de nodos desde el nodo inicial o raíz hasta una hoja.
Definir la función
|
1 |
propiedadAF :: (a -> Bool) -> Arbol a -> Bool |
tal que (propiedadAF p a) se verifica si se cumple (AF p) en el árbol a; es decir, si en todas las ramas hay un nodo (interno u hoja) que cumple la propiedad p. Por ejemplo
|
1 2 |
propiedadAF even a1 == True propiedadAF (<7) a1 == False |
Soluciones
[schedule expon=’2015-03-26′ expat=»06:00″]
|
1 2 3 4 5 6 7 8 9 10 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show,Eq) a1 :: Arbol Int a1 = N 9 (N 3 (H 2) (N 4 (H 1) (H 5))) (H 8) propiedadAF :: (a -> Bool) -> Arbol a -> Bool propiedadAF p (H a) = p a propiedadAF p (N a i d) = p a || (propiedadAF p i && propiedadAF p d) |