Datos inductivos (recursivos)

 En Haskell algunos árboles binarios con nodos interiores decorados se 

representan así

data Bin = Hoja Int | B Int Bin Bin deriving Show

La parte "Hoja Int" la podemos interpretar como las hojas del árbol,

ya sin descendientes. La parte "B Int Bin Bin" hace referencia a la parte

de nodos internos (raíz y no hojas) que lleva la información en la parte

superior de un triángulo en "Int" y en la rama izquierda tiene un árbol

de tipo Bin, así como en la parte derecha.

Teniendo presente ésto, una función típica (endomorfismo) sería:

 

arbolConstante (Hoja n) = Hoja 2

arbolConstante (B n izq der) = B 2 (arbolConstante izq) (arbolConstante der)

 

Esta función toma un árbol binario y lo transforma en otro árbol binario

con todo nodo valiendo 2.

Otro ejemplo sería el de sumar todos los elementos de un árbol de este tipo:

sumaArbol (Hoja n) = n

sumaArbol (B n izq der) = n+sizq+sder

              where

                     sizq=sumaArbol izq

                     sder=sumaArbol der