Aplicación de una función a un árbol
El árbol binario
|
1 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9)) |
El tipo de los árboles binarios se puede definir por
|
1 2 3 |
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq) |
Definir la función
|
1 |
mapArbol :: (a -> b) -> Arbol a -> Arbol b |
tal que mapArbol f t es el árbolo obtenido aplicando la función f a los elementos del árbol t. Por ejemplo,
|
1 2 |
λ> mapArbol (+ 1) (Nodo (Hoja 2) (Hoja 4)) Nodo (Hoja 3) (Hoja 5) |
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 = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Show, Eq) mapArbol :: (a -> b) -> Arbol a -> Arbol b mapArbol f (Hoja a) = Hoja (f a) mapArbol f (Nodo l r) = Nodo (mapArbol f l) (mapArbol f r) |
|
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") B = TypeVar("B") @dataclass class Arbol(Generic[A]): pass @dataclass class Hoja(Arbol[A]): x: A @dataclass class Nodo(Arbol[A]): i: Arbol[A] d: Arbol[A] def mapArbol(f: Callable[[A], B], a: Arbol[A]) -> Arbol[B]: match a: case Hoja(x): return Hoja(f(x)) case Nodo(i, d): return Nodo(mapArbol(f, i), mapArbol(f, d)) assert False |