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 |