Relación 12

-- I1M 2021-22
-- Tipos de datos algebraicos: Árboles binarios.
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- En esta relación se presenta ejercicios sobre árboles binarios
-- definidos como tipos de datos algebraicos.
-- 
-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Test.QuickCheck
import Control.Monad

-- ---------------------------------------------------------------------
-- Nota. En los siguientes ejercicios se trabajará con los árboles
-- binarios definidos como sigue 
--    data Arbol a = H a
--                 | N a (Arbol a) (Arbol a)
--                 deriving (Show, Eq)
-- Por ejemplo, el árbol
--         9 
--        / \
--       /   \
--      3     7
--     / \  
--    2   4 
-- se representa por
--    N 9 (N 3 (H 2) (H 4)) (H 7) 
-- ---------------------------------------------------------------------

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving (Show, Eq)

arbol1 :: Arbol Int
arbol1 = (N 9 (N 3 (H 2) (H 4)) (H 7))

arbol2 :: Arbol Int
arbol2 = (N 10 (N 3 (N 3 (H 1) (H 4)) (H 7)) (N 15 (H 13) (N 18 (H 16) (H 20))))

-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir la función
--    nHojas :: Arbol a -> Int
-- tal que (nHojas x) es el número de hojas del árbol x. Por ejemplo,
--    nHojas (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  3
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

nHojas :: Arbol a -> Int
nHojas (H e) = 1
nHojas (N e l r) = nHojas l + nHojas r

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir la función
--    nNodos :: Arbol a -> Int
-- tal que (nNodos x) es el número de nodos del árbol x. Por ejemplo,
--    nNodos (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  2
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

nNodos :: Arbol a -> Int
nNodos (H e) = 0
nNodos (N e l r) = 1 + nNodos l + nNodos r

-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Comprobar con QuickCheck que en todo árbol binario el
-- número de sus hojas es igual al número de sus nodos más uno.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_nHojas :: Arbol Int -> Bool
prop_nHojas x = nHojas x == (nNodos x) + 1

-- La comprobación es
-- *Main> quickCheck prop_nHojas
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Definir la función
--    profundidad :: Arbol a -> Int
-- tal que (profundidad x) es la profundidad del árbol x. Por ejemplo,
--    profundidad (N 9 (N 3 (H 2) (H 4)) (H 7))              ==  2
--    profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7))  ==  3
--    profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4)))  ==  2
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

profundidad :: Arbol a -> Int
profundidad (H e) = 0
profundidad (N e l r) = 1 + max (profundidad l) (profundidad r)      

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Comprobar con QuickCheck que para todo árbol biario
-- x, se tiene que
--    nNodos x <= 2^(profundidad x) - 1
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_nNodosProfundidad :: Arbol Int -> Bool
prop_nNodosProfundidad x = nNodos x <= 2^(profundidad x) - 1

-- La comprobación es
-- *Main> quickCheck prop_nNodosProfundidad
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 3.1. Definir la función
--    preorden :: Arbol a -> [a]
-- tal que (preorden x) es la lista correspondiente al recorrido
-- preorden del árbol x; es decir, primero visita la raíz del árbol, a
-- continuación recorre el subárbol izquierdo y, finalmente, recorre el
-- subárbol derecho. Por ejemplo,
--    preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

preorden :: Arbol a -> [a]
preorden (H e) = [e]
preorden (N e l r) = [e] ++ preorden l ++ preorden r 

-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Comprobar con QuickCheck que la longitud de la lista
-- obtenida recorriendo un árbol en sentido preorden es igual al número
-- de nodos del árbol más el número de hojas.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_length_preorden :: Arbol Int -> Bool
prop_length_preorden x = length (preorden x) == nHojas x + nNodos x 

-- La comprobación es
-- *Main> quickCheck prop_length_preorden
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Definir la función
--    postorden :: Arbol a -> [a]
-- tal que (postorden x) es la lista correspondiente al recorrido
-- postorden del árbol x; es decir, primero recorre el subárbol
-- izquierdo, a continuación el subárbol derecho y, finalmente, la raíz
-- del árbol. Por ejemplo,
--    postorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,4,3,7,9]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

postorden :: Arbol a -> [a]
postorden (H e) = [e]
postorden (N e l r) = postorden l ++ postorden r ++ [e] 

inorden :: Arbol a -> [a]
inorden (H e) = [e]
inorden (N e l r) = inorden l ++ [e] ++ inorden r

-- ---------------------------------------------------------------------
-- Ejercicio 3.4. Definir, usando un acumulador, la función
--    preordenIt :: Arbol a -> [a]
-- tal que (preordenIt x) es la lista correspondiente al recorrido
-- preorden del árbol x; es decir, primero visita la raíz del árbol, a
-- continuación recorre el subárbol izquierdo y, finalmente, recorre el
-- subárbol derecho. Por ejemplo,
--    Preordenit (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]
-- 
-- Nota: No usar (++) en la definición
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

preordenIt :: Arbol a -> [a]
preordenIt x = preordenItAux [] x  

preordenItAux :: [a] -> Arbol a -> [a]
preordenItAux ec (H e) = e:ec
preordenItAux ec (N e l r) = e:(preordenItAux (preordenItAux ec r) l)

-- ---------------------------------------------------------------------
-- Ejercicio 3.5. Comprobar con QuickCheck que preordenIt es equivalente
-- a preorden. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_preordenIt :: Arbol Int -> Bool
prop_preordenIt x = preordenIt x == preorden x

-- La comprobación es
-- *Main> quickCheck prop_preordenIt
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir la función
--    espejo :: Arbol a -> Arbol a
-- tal que (espejo x) es la imagen especular del árbol x. Por ejemplo,
--    espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2))
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

espejo :: Arbol a -> Arbol a
espejo (H e) = (H e)
espejo (N e l r) = (N e (espejo r) (espejo l))

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Comprobar con QuickCheck que para todo árbol x,
--    espejo (espejo x) = x
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_espejo :: Arbol Int -> Bool
prop_espejo x = espejo (espejo x) == x

-- La comprobación es
-- *Main> quickCheck prop_espejo
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 4.3. Comprobar con QuickCheck que para todo árbol binario
-- x, se tiene que
--    reverse (preorden (espejo x)) = postorden x
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_reverse_preorden_espejo :: Arbol Int -> Bool
prop_reverse_preorden_espejo x = reverse (preorden (espejo x)) == postorden x

-- La comprobación es
-- *Main> quickCheck prop_reverse_preorden_espejo
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 4.4. Comprobar con QuickCheck que para todo árbol x,
--    postorden (espejo x) = reverse (preorden x)
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_recorrido :: Arbol Int -> Bool
prop_recorrido x = postorden (espejo x) == reverse (preorden x)

-- La comprobación es
-- *Main> quickCheck prop_recorrido
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 5.1. La función take está definida por
--    take :: Int -> [a] -> [a]
--    take 0            = []
--    take n []         = []
--    take n (x:xs)     = x : take (n-1) xs
-- 
-- Definir la función 
--    takeArbol ::  Int -> Arbol a -> Arbol a
-- tal que (takeArbol n t) es el subárbol de t de profundidad n. Por
-- ejemplo,
--    takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9
--    takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7)
--    takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
--    takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
-- ---------------------------------------------------------------------
 
-- Álvaro Galisteo:

takeArbol :: Int -> Arbol a -> Arbol a
takeArbol 0 (N e l r) = H e
takeArbol _ (H e) = H e
takeArbol n (N e l r) = N e (takeArbol (n-1) l) (takeArbol (n-1) r)


-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Comprobar con QuickCheck que la profundidad de 
-- (takeArbol n x) es menor o igual que n, para todo número natural n y
-- todo árbol x. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_takeArbol :: Int -> Arbol Int -> Property
prop_takeArbol n x = n>=0 ==> profundidad (takeArbol n x) <= n 

-- La comprobación es
-- *Main> quickCheck prop_takeArbol
-- +++ OK, passed 100 tests; 102 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 6.1. La función
--    repeat :: a -> [a]
-- está definida de forma que (repeat x) es la lista formada por
-- infinitos elementos x. Por ejemplo,
--    repeat 3  ==  [3,3,3,3,3,3,3,3,3,3,3,3,3,...
-- La definición de repeat es
--    repeat x = xs where xs = x:xs
-- 
-- Definir la función
--    repeatArbol :: a -> Arbol a
-- tal que (repeatArbol x) es es árbol con infinitos nodos x. Por
-- ejemplo, 
--    takeArbol 0 (repeatArbol 3) == H 3
--    takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3)
--    takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

repeatArbol :: a -> Arbol a
repeatArbol x = N x (repeatArbol x) (repeatArbol x) 

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. La función 
--    replicate :: Int -> a -> [a]
-- está definida por 
--    replicate n = take n . repeat
-- es tal que (replicate n x) es la lista de longitud n cuyos elementos
-- son x. Por ejemplo,
--    replicate 3 5  ==  [5,5,5]
-- 
-- Definir la función 
--    replicateArbol :: Int -> a -> Arbol a
-- tal que (replicate n x) es el árbol de profundidad n cuyos nodos son
-- x. Por ejemplo,
--    replicateArbol 0 5  ==  H 5
--    replicateArbol 1 5  ==  N 5 (H 5) (H 5)
--    replicateArbol 2 5  ==  N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

replicateArbol :: Int -> a -> Arbol a
replicateArbol n = takeArbol n . repeatArbol 

-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Comprobar con QuickCheck que el número de hojas de 
-- (replicateArbol n x) es 2^n, para todo número natural n
--
-- Nota. Al hacer la comprobación limitar el tamańo de las pruebas como
-- se indica a continuación
--    quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_replicateArbol :: Int -> Int -> Property
prop_replicateArbol n x = n>=0 ==> nHojas (replicateArbol n x) == 2^n 

-- La comprobación es
-- quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol
-- +++ OK, passed 100 tests; 48 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir la función
--    mapArbol :: (a -> a) -> Arbol a -> Arbol a
-- tal que (mapArbol f x) es el árbol obtenido aplicándole a cada nodo de
-- x la función f. Por ejemplo,
--    ghci> mapArbol (*2) (N 9 (N 3 (H 2) (H 4)) (H 7)) 
--    N 18 (N 6 (H 4) (H 8)) (H 14)
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

mapArbol :: (a -> a) -> Arbol a -> Arbol a
mapArbol f (H e) = H (f e) 
mapArbol f (N e l r) = (N (f e) (mapArbol f l) (mapArbol f r))

-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Comprobar con QuickCheck que 
--    (mapArbol (1+)) . espejo = espejo . (mapArbol (1+))
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_mapArbol_espejo :: Arbol Int -> Bool
prop_mapArbol_espejo x = (mapArbol (+1) (espejo x)) == (espejo (mapArbol (+1) (x)))

-- La comprobación es
-- *Main> quickCheck prop_mapArbol_espejo
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que
--    (map (1+)) . preorden = preorden . (mapArbol (1+)) 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:

-- La propiedad es
prop_map_preorden :: Arbol Int -> Bool
prop_map_preorden x = map (1+) (preorden x) == preorden (mapArbol (1+) x) 

-- La comprobación es
-- *Main> quickCheck prop_map_preorden
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Nota. Para comprobar propiedades de árboles con QuickCheck se
-- utilizará el siguiente generador.
-- ---------------------------------------------------------------------

instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbol
    where
      arbol 0       = liftM H arbitrary 
      arbol n | n>0 = oneof [liftM H arbitrary,
                             liftM3 N arbitrary subarbol subarbol]
                      where subarbol = arbol (div n 2)
      arbol _       = error "Imposible"