Existencia de elementos del árbol que verifican una propiedad
Los árboles binarios con valores en las hojas y en los nodos se definen por
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
5 / \ / \ 3 2 / \ 1 4 |
se representa por
|
1 |
N 5 (N 3 (H 1) (H 4)) (H 2) |
Definir la función
|
1 |
algunoArbol :: Arbol t -> (t -> Bool) -> Bool |
tal que algunoArbol a p se verifica si algún elemento del árbol a cumple la propiedad p. Por ejemplo,
|
1 2 |
algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4) == True algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7) == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show algunoArbol :: Arbol a -> (a -> Bool) -> Bool algunoArbol (H x) p = p x algunoArbol (N x i d) p = p x || algunoArbol i p || algunoArbol d p |
|
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 |
from dataclasses import dataclass from typing import Callable, Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): x: A @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def algunoArbol(a: Arbol[A], p: Callable[[A], bool]) -> bool: match a: case H(x): return p(x) case N(x, i, d): return p(x) or algunoArbol(i, p) or algunoArbol(d, p) assert False |
Para definir la función algunoArbol, podemos recorrer el árbol de forma recursiva y evaluar la propiedad p en cada elemento del árbol. Si encontramos algún elemento que cumple la propiedad, podemos devolver True inmediatamente, ya que no es necesario seguir evaluando el resto del árbol. Si recorremos todo el árbol y no encontramos ningún elemento que cumpla la propiedad, entonces podemos devolver False.
Aquí dejo una posible implementación de la función algunoArbol:
La función recibe un árbol Arbol t y una propiedad p representada por una función que toma un elemento de tipo t y devuelve un valor Bool. En el caso de que el árbol sea una hoja H x, evaluamos la propiedad p en el elemento de la hoja y devolvemos el resultado. Si el árbol es un nodo N x izq der, evaluamos la propiedad p en el elemento del nodo y, además, recursivamente en el subárbol izquierdo y en el subárbol derecho. Devolvemos True si alguna de las evaluaciones es True, y False en caso contrario.
En Python, podemos usar la estructura match-case (que se parece al case de algunos lenguajes de programación) para definir la función algunoArbol. Para hacerlo, necesitamos importar la librería dataclass y definir una clase Arbol con dos subclases: H para representar las hojas y N para representar los nodos.
La clase Arbol puede definirse como una clase abstracta, lo que significa que no se pueden crear instancias de esta clase, sino que sólo se pueden crear instancias de sus subclases. Esto nos permite aprovechar la estructura match-case para recorrer el árbol de forma recursiva.
Aquí dejo una posible implementación de la función algunoArbol en Python:
La función algunoArbol recibe un árbol arbol y una propiedad p representada por una función que toma un elemento y devuelve un valor bool. En el caso de que el árbol sea una hoja H, evaluamos la propiedad p en el elemento de la hoja y devolvemos el resultado. Si el árbol es un nodo N, evaluamos la propiedad p en el elemento del nodo y, además, recursivamente en el subárbol izquierdo y en el subárbol derecho. Devolvemos True si alguna de las evaluaciones es True, y False en caso contrario.
Nota: para poder usar la estructura match-case es necesario usar Python 3.10 o superior.
Aquí dejo la solución en Lean:
En este código hemos definido la estructura de datos Arbol α para representar árboles binarios con valores en las hojas y en los nodos. Luego hemos definido la función algunoArbol siguiendo la idea que propuse anteriormente. La función recibe un árbol a : Arbol α y una propiedad p : α → bool, y devuelve un valor bool.
Para evaluar la función con los ejemplos que propusiste, hemos utilizado expresiones lambda λ x, x > 4 y λ x, x > 7 para representar la propiedad de ser mayor que 4 y mayor que 7, respectivamente.