Ir al contenido principal

Aplicación de una función a un árbol

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

   data Arbol a = Hoja a
                | Nodo (Arbol a) (Arbol a)
     deriving (Show, Eq)

Definir la función

   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,

   λ> 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.

Soluciones en Haskell

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)

Soluciones en Python

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