Enumeración de los árboles binarios en Haskell

En esta relación se definen funciones que enumeran el conjunto de los árboles binarios cuyas hojas son números naturales; es decir, funciones biyectivas $f: \mathbb{N} \to A$ y $g: A \to \mathbb{N}$ , donde $A$ es el conjunto de los árboles binarios cuyas hojas son números naturales. La propiedad biyectiva se comprueba mostrando que $f \cdot g$ y $g \cdot f$ son la identidad.

La enumeración se basa en la de los pares de números naturales vista
en el módulo Enumeración del producto cartesiano de los naturales.

-- ---------------------------------------------------------------------
-- Librerias auxiliares                                               --
-- ---------------------------------------------------------------------

import Enumeracion_del_producto_cartesianos_de_naturales

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir el tipo de datos Arbol formado por los árboles
-- binarios cuyas hojas son números enteros. 
-- ---------------------------------------------------------------------

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

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    arbol :: Int -> Arbol
-- tal que (arbol n) es el n-ésimo árbol binario construido mediante el
-- siguiente procedimiento: sea (x,y) el n-ésimo par de números
-- naturales, entonces (arbol n) es
--    * Hoja y,                       si x=0
--    * Nodo (arbol (x-1)) (arbol y), en caso contrario.
-- Por ejemplo, 
--    ghci> [(n, par n, arbol n) | n <- [0..19]]
--    [(0,(0,0),Hoja 0),
--     (1,(0,1),Hoja 1),
--     (2,(1,0),Nodo (Hoja 0) (Hoja 0)),
--     (3,(0,2),Hoja 2),
--     (4,(1,1),Nodo (Hoja 0) (Hoja 1)),
--     (5,(2,0),Nodo (Hoja 1) (Hoja 0)),
--     (6,(0,3),Hoja 3),
--     (7,(1,2),Nodo (Hoja 0) (Nodo (Hoja 0) (Hoja 0))),
--     (8,(2,1),Nodo (Hoja 1) (Hoja 1)),
--     (9,(3,0),Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 0)),
--     (10,(0,4),Hoja 4),
--     (11,(1,3),Nodo (Hoja 0) (Hoja 2)),
--     (12,(2,2),Nodo (Hoja 1) (Nodo (Hoja 0) (Hoja 0))),
--     (13,(3,1),Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 1)),
--     (14,(4,0),Nodo (Hoja 2) (Hoja 0)),
--     (15,(0,5),Hoja 5),
--     (16,(1,4),Nodo (Hoja 0) (Nodo (Hoja 0) (Hoja 1))),
--     (17,(2,3),Nodo (Hoja 1) (Hoja 2)),
--     (18,(3,2),Nodo (Nodo (Hoja 0) (Hoja 0)) (Nodo (Hoja 0) (Hoja 0))),
--     (19,(4,1),Nodo (Hoja 2) (Hoja 1))]
--    ghci> arbol 41934
--    Nodo (Hoja 7) (Nodo (Hoja 3) (Hoja 5))
-- ---------------------------------------------------------------------

arbol :: Int -> Arbol
arbol n | x == 0    = Hoja y
        | otherwise = Nodo (arbol (x-1)) (arbol y) 
        where (x,y) = par n

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    indiceArbol :: Arbol -> Int
-- tal que (indiceArbol x) es el índice del árbol x; es decir el número
-- n tal que x (arbol n) es x. Por ejemplo, 
--    ghci> indiceArbol (Nodo (Hoja 7) (Nodo (Hoja 3) (Hoja 5)))
--    41934
-- ---------------------------------------------------------------------

indiceArbol :: Arbol -> Int
indiceArbol (Hoja n)   = indice (0,n)
indiceArbol (Nodo i d) = indice (1 + indiceArbol i, indiceArbol d)

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    prop_indiceArbol_arbol :: Int -> Bool
-- tal que (prop_indiceArbol_arbol n) se verifica si para todo árbol x
-- de índice menor o igual que n se tiene que (indiceArbol (arbol x)) es
-- x. Por ejemplo, 
--    ghci> prop_indiceArbolArbol 100
--    True
-- ---------------------------------------------------------------------

prop_indiceArbol_arbol :: Int -> Bool
prop_indiceArbol_arbol n =
    and [indiceArbol (arbol x) == x | x <- [0..n]]

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
--    arbolesMenores :: Arbol -> [Arbol]
-- tal que (arbolesMenores x) es la lista de árboles cuyo índice es
-- menor o igual que el de árbol x. Por ejemplo,
--    ghci> arbolesMenores (Hoja 3)
--    [Hoja 0,
--     Hoja 1,
--     Nodo (Hoja 0) (Hoja 0),
--     Hoja 2,
--     Nodo (Hoja 0) (Hoja 1),
--     Nodo (Hoja 1) (Hoja 0),
--     Hoja 3]
-- ---------------------------------------------------------------------

arbolesMenores :: Arbol -> [Arbol]
arbolesMenores x = [arbol n | n <- [0..indiceArbol x]] 

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir la propiedad
--    prop_arbol_indiceArbol :: Arbol -> Bool
-- tal que (prop_arbol_indiceArbol x) se verifica si para cualquier
-- árbol y menor que x se tiene que (arbol (indiceArbol y)) es y. Por
-- ejemplo, 
--    ghci> prop_arbol_indiceArbol (Hoja 5)
--    True
-- ---------------------------------------------------------------------

prop_arbol_indiceArbol :: Arbol -> Bool
prop_arbol_indiceArbol x =
    and [arbol (indiceArbol y) == y | y <- arbolesMenores x]

100

101

102

103

104

105

106

107

108

109

110

111

112

-- ---------------------------------------------------------------------

-- Librerias auxiliares --

-- ---------------------------------------------------------------------

import Enumeracion_del_producto_cartesianos_de_naturales

-- ---------------------------------------------------------------------

-- Ejercicio 1. Definir el tipo de datos Arbol formado por los árboles

-- binarios cuyas hojas son números enteros.

-- ---------------------------------------------------------------------

data Arbol = Hoja Int

| Nodo Arbol Arbol

deriving (Eq, Show)

-- ---------------------------------------------------------------------

-- Ejercicio 2. Definir la función

-- arbol :: Int -> Arbol

-- tal que (arbol n) es el n-ésimo árbol binario construido mediante el

-- siguiente procedimiento: sea (x,y) el n-ésimo par de números

-- naturales, entonces (arbol n) es

-- * Hoja y, si x=0

-- * Nodo (arbol (x-1)) (arbol y), en caso contrario.

-- Por ejemplo,

-- ghci> [(n, par n, arbol n) | n <- [0..19]]

-- [(0,(0,0),Hoja 0),

-- (1,(0,1),Hoja 1),

-- (2,(1,0),Nodo (Hoja 0) (Hoja 0)),

-- (3,(0,2),Hoja 2),

-- (4,(1,1),Nodo (Hoja 0) (Hoja 1)),

-- (5,(2,0),Nodo (Hoja 1) (Hoja 0)),

-- (6,(0,3),Hoja 3),

-- (7,(1,2),Nodo (Hoja 0) (Nodo (Hoja 0) (Hoja 0))),

-- (8,(2,1),Nodo (Hoja 1) (Hoja 1)),

-- (9,(3,0),Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 0)),

-- (10,(0,4),Hoja 4),

-- (11,(1,3),Nodo (Hoja 0) (Hoja 2)),

-- (12,(2,2),Nodo (Hoja 1) (Nodo (Hoja 0) (Hoja 0))),

-- (13,(3,1),Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 1)),

-- (14,(4,0),Nodo (Hoja 2) (Hoja 0)),

-- (15,(0,5),Hoja 5),

-- (16,(1,4),Nodo (Hoja 0) (Nodo (Hoja 0) (Hoja 1))),

-- (17,(2,3),Nodo (Hoja 1) (Hoja 2)),

-- (18,(3,2),Nodo (Nodo (Hoja 0) (Hoja 0)) (Nodo (Hoja 0) (Hoja 0))),

-- (19,(4,1),Nodo (Hoja 2) (Hoja 1))]

-- ghci> arbol 41934

-- Nodo (Hoja 7) (Nodo (Hoja 3) (Hoja 5))

-- ---------------------------------------------------------------------

arbol :: Int -> Arbol

arbol n | x == 0 = Hoja y

| otherwise = Nodo (arbol (x-1)) (arbol y)

where (x,y) = par n

-- ---------------------------------------------------------------------

-- Ejercicio 3. Definir la función

-- indiceArbol :: Arbol -> Int

-- tal que (indiceArbol x) es el índice del árbol x; es decir el número

-- n tal que x (arbol n) es x. Por ejemplo,

-- ghci> indiceArbol (Nodo (Hoja 7) (Nodo (Hoja 3) (Hoja 5)))

-- 41934

-- ---------------------------------------------------------------------

indiceArbol :: Arbol -> Int

indiceArbol (Hoja n) = indice (0,n)

indiceArbol (Nodo i d) = indice (1 + indiceArbol i, indiceArbol d)

-- ---------------------------------------------------------------------

-- Ejercicio 4. Definir la función

-- prop_indiceArbol_arbol :: Int -> Bool

-- tal que (prop_indiceArbol_arbol n) se verifica si para todo árbol x

-- de índice menor o igual que n se tiene que (indiceArbol (arbol x)) es

-- x. Por ejemplo,

-- ghci> prop_indiceArbolArbol 100

-- True

-- ---------------------------------------------------------------------

prop_indiceArbol_arbol :: Int -> Bool

prop_indiceArbol_arbol n =

and [indiceArbol (arbol x) == x | x <- [0..n]]

-- ---------------------------------------------------------------------

-- Ejercicio 5. Definir la función

-- arbolesMenores :: Arbol -> [Arbol]

-- tal que (arbolesMenores x) es la lista de árboles cuyo índice es

-- menor o igual que el de árbol x. Por ejemplo,

-- ghci> arbolesMenores (Hoja 3)

-- [Hoja 0,

-- Hoja 1,

-- Nodo (Hoja 0) (Hoja 0),

-- Hoja 2,

-- Nodo (Hoja 0) (Hoja 1),

-- Nodo (Hoja 1) (Hoja 0),

-- Hoja 3]

-- ---------------------------------------------------------------------

arbolesMenores :: Arbol -> [Arbol]

arbolesMenores x = [arbol n | n <- [0..indiceArbol x]]

-- ---------------------------------------------------------------------

-- Ejercicio 6. Definir la propiedad

-- prop_arbol_indiceArbol :: Arbol -> Bool

-- tal que (prop_arbol_indiceArbol x) se verifica si para cualquier

-- árbol y menor que x se tiene que (arbol (indiceArbol y)) es y. Por

-- ejemplo,

-- ghci> prop_arbol_indiceArbol (Hoja 5)

-- True

-- ---------------------------------------------------------------------

prop_arbol_indiceArbol :: Arbol -> Bool

prop_arbol_indiceArbol x =

and [arbol (indiceArbol y) == y | y <- arbolesMenores x]

Se puede imprimir o compartir con