Menu Close

I1M2013: Ejercicios con tipos de datos algebraicos en Haskell

En las clases de ayer y hoy de Informática de 1º del Grado en Matemáticas hemos comentando soluciones de los ejercicios sobre tipos de datos algebraicos en Haskell de la relaciones 18 y 19.

En la relación 18 se consideran abreviaturas y dos tipos de datos algebraicos: los números naturales (para los que se define su producto) y los árboles binarios, para los que se definen funciones para calcular:

  • los puntos más cercanos,
  • la ocurrencia de un elemento en el árbol,
  • el número de hojas,
  • el carácter balanceado de un árbol y
  • el árbol balanceado correspondiente a una lista.

En la relación 19 se plantean ejercicios sobre árboles binarios. En concreto, se definen funciones para calcular:

  • el número de hojas de un árbol,
  • el número de nodos de un árbol,
  • la profundidad de un árbol,
  • el recorrido preorden de un árbol,
  • el recorrido postorden de un árbol,
  • el recorrido preorden de forma iterativa,

Los ejercicios, y sus soluciones, se muestran a continuación. Los de la relación 18 son

-- ---------------------------------------------------------------------
-- Ejercicio 1. Los puntos del plano se pueden representar por pares de
-- números como se indica a continuación  
--    type Punto = (Double,Double) 
-- Definir la función 
--    cercanos :: [Punto] -> [Punto] -> (Punto,Punto)
-- tal que (cercanos ps qs) es un par de puntos, el primero de ps y el
-- segundo de qs, que son los más cercanos (es decir, no hay otro par
-- (p',q') con p' en ps y q' en qs tales que la distancia entre p' y q'
-- sea menor que la que hay entre p y q). Por ejemplo,
--    cercanos [(2,5),(3,6)] [(4,3),(1,0),(7,9)] == ((2.0,5.0),(4.0,3.0))
-- ---------------------------------------------------------------------
 
type Punto = (Double,Double) 
 
cercanos :: [Punto] -> [Punto] -> (Punto,Punto)
cercanos ps qs = (p,q)
    where (d,p,q) = minimum [(distancia p q, p, q) | p <- ps, q <-qs]
          distancia (x,y) (u,v) = sqrt ((x-u)^2+(y-v)^2)
 
-- ---------------------------------------------------------------------
-- Ejercicio 2.1. En los diguientes ejercicios se usará el tipo
-- algebraico de datos de los números naturales definido por
--    data Nat = Cero | Suc Nat
--               deriving (Eq, Show)
-- Definir la función
--    suma :: Nat -> Nat -> Nat
-- tal que (suma m n) es la suma de los números naturales m y
-- n. Por ejemplo, 
--    ghci> suma (Suc (Suc Cero)) (Suc (Suc (Suc Cero)))
--    Suc (Suc (Suc (Suc (Suc Cero))))
-- ---------------------------------------------------------------------
 
data Nat = Cero | Suc Nat
           deriving (Eq, Show)
 
suma :: Nat -> Nat -> Nat
suma Cero    n = n
suma (Suc m) n = Suc (suma m n)
 
-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir la función
--    producto :: Nat -> Nat -> Nat
-- tal que (producto m n) es el producto de los números naturales m y
-- n. Por ejemplo, 
--    ghci> producto (Suc (Suc Cero)) (Suc (Suc (Suc Cero)))
--    Suc (Suc (Suc (Suc (Suc (Suc Cero)))))
-- ---------------------------------------------------------------------
 
producto :: Nat -> Nat -> Nat
producto Cero _    = Cero
producto (Suc m) n = suma n (producto m n)
 
-- ---------------------------------------------------------------------
-- Ejercicio 3. En los apartados de este ejercicio se trabajará con
-- árboles binarios definidos como sigue
--    data Arbol = Hoja Int 
--               | Nodo Arbol Int Arbol
--               deriving (Show, Eq)
-- Por ejemplo, el árbol
--         5 
--        / \
--       /   \
--      3     7
--     / \   / \  
--    1   4 6   9  
-- se representa por
--    Nodo (Nodo (Hoja 1) 3 (Hoja 4)) 
--         5 
--         (Nodo (Hoja 6) 7 (Hoja 9))
-- ---------------------------------------------------------------------
 
data Arbol = Hoja Int 
           | Nodo Arbol Int Arbol
           deriving (Show, Eq)
 
ejArbol :: Arbol
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4)) 
               5 
               (Nodo (Hoja 6) 7 (Hoja 9))
 
-- --------------------------------------------------------------------
-- Ejercicio 3.1. Definir la función
--    ocurre :: Int -> Arbol -> Bool
-- tal que (ocurre x a) se verifica si x ocurre en el árbol a como valor
-- de un nodo o de una hoja. Por ejemplo,
--    ocurre  4 ejArbol  ==  True
--    ocurre 10 ejArbol  ==  False
-- ---------------------------------------------------------------------
 
ocurre :: Int -> Arbol -> Bool
ocurre m (Hoja n)     = m == n
ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d
 
-- ---------------------------------------------------------------------
-- Ejercicio 3.2. En el preludio está definido el tipo de datos
--    data Ordering = LT | EQ | GT
-- junto con la función
--    compare :: Ord a => a -> a -> Ordering
-- que decide si un valor en un tipo ordenado es menor (LT), igual (EQ)
-- o mayor (GT) que otro. 
-- 
-- Usando esta función, redefinir la función
--    ocurre :: Int -> Arbol -> Bool
-- del ejercicio anterior. 
-- ---------------------------------------------------------------------
 
ocurre' :: Int -> Arbol -> Bool
ocurre' m (Hoja n)     = m == n
ocurre' m (Nodo i n d) = case compare m n of
                           LT -> ocurre' m i
                           EQ -> True
                           GT -> ocurre' m d
 
-- ---------------------------------------------------------------------
-- Ejercicio 4. En los apartados de este ejercicio se trabajará con
-- árboles binarios definidos como sigue
--    type ArbolB = HojaB Int 
--                | NodoB ArbolB ArbolB 
--                deriving Show
-- Por ejemplo, el árbol
--         . 
--        / \
--       /   \
--      .     .
--     / \   / \  
--    1   4 6   9  
-- se representa por
--    NodoB (NodoB (HojaB 1) (HojaB 4)) 
--          (NodoB (HojaB 6) (HojaB 9))
-- ---------------------------------------------------------------------
 
data ArbolB = HojaB Int 
            | NodoB ArbolB ArbolB
            deriving Show
 
ejArbolB :: ArbolB
ejArbolB = NodoB (NodoB (HojaB 1) (HojaB 4)) 
                 (NodoB (HojaB 6) (HojaB 9))
 
-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir la función 
--    nHojas :: ArbolB -> Int
-- tal que (nHojas a) es el número de hojas del árbol a. Por ejemplo,
--    nHojas (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7)))  ==  3
--    nHojas ejArbolB ==  4
-- ---------------------------------------------------------------------
 
nHojas :: ArbolB -> Int
nHojas (HojaB _)     = 1
nHojas (NodoB a1 a2) = nHojas a1 + nHojas a2
 
-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Se dice que un árbol de este tipo es balanceado si es
-- una hoja o bien si para cada nodo se tiene que el número de hojas en
-- cada uno de sus subárboles difiere como máximo en uno y sus
-- subárboles son balanceados. Definir la función 
--    balanceado :: ArbolB -> BoolB
-- tal que (balanceado a) se verifica si a es un árbol balanceado. Por
-- ejemplo, 
--    balanceado ejArbolB
--    ==> True
--    balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (HojaB 7)))
--    ==> True
--    balanceado (NodoB (HojaB 5) (NodoB (HojaB 3) (NodoB (HojaB 5) (HojaB 7))))
--    ==> False
-- ---------------------------------------------------------------------
 
balanceado :: ArbolB -> Bool
balanceado (HojaB _)     = True
balanceado (NodoB a1 a2) = abs (nHojas a1 - nHojas a2) <= 1 &&
                           balanceado a1 &&
                           balanceado a2
 
-- ---------------------------------------------------------------------
-- Ejercicio 4.3. Definir la función 
--    mitades :: [a] -> ([a],[a]) 
-- tal que (mitades xs) es un par de listas que se obtiene al dividir xs
-- en dos mitades cuya longitud difiere como máximo en uno. Por ejemplo,
--    mitades [2,3,5,1,4,7]    ==  ([2,3,5],[1,4,7])
--    mitades [2,3,5,1,4,7,9]  ==  ([2,3,5],[1,4,7,9])
-- ---------------------------------------------------------------------
 
mitades :: [a] -> ([a],[a])
mitades xs = splitAt (length xs `div` 2) xs
 
-- ---------------------------------------------------------------------
-- Ejercicio 4.4. Definir la función
--    arbolBalanceado :: [Int] -> ArbolB
-- tal que (arbolBalanceado xs) es el árbol balanceado correspondiente
-- a la lista xs. Por ejemplo,
--    ghci> arbolBalanceado [2,5,3]
--    NodoB (HojaB 2) (NodoB (HojaB 5) (HojaB 3))
--    ghci> arbolBalanceado [2,5,3,7]
--    NodoB (NodoB (HojaB 2) (HojaB 5)) (NodoB (HojaB 3) (HojaB 7))
-- ---------------------------------------------------------------------
 
arbolBalanceado :: [Int] -> ArbolB
arbolBalanceado [x] = HojaB x
arbolBalanceado xs  = NodoB (arbolBalanceado ys) (arbolBalanceado zs)
                      where (ys,zs) = mitades xs

Los de la relación 19 son

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                  
-- ---------------------------------------------------------------------
 
import Data.List
 
-- ---------------------------------------------------------------------
-- Nota. En los siguientes ejercicios se trabajará con los árboles
-- binarios definidos como sigue 
--    data Arbol a = Hoja 
--                 | Nodo a (Arbol a) (Arbol a)
--                 deriving (Show, Eq)
-- En los ejemplos se usará el siguiente árbol
--    arbol = Nodo 9
--                   (Nodo 3 
--                         (Nodo 2 Hoja Hoja) 
--                         (Nodo 4 Hoja Hoja)) 
--                   (Nodo 7 Hoja Hoja)
-- ---------------------------------------------------------------------
 
data Arbol a = Hoja 
             | Nodo a (Arbol a) (Arbol a)
             deriving (Show, Eq)
 
arbol = Nodo 9
               (Nodo 3 
                     (Nodo 2 Hoja Hoja) 
                     (Nodo 4 Hoja Hoja)) 
               (Nodo 7 Hoja Hoja)
 
-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función
--    nHojas :: Arbol a -> Int
-- tal que (nHojas x) es el número de hojas del árbol x. Por ejemplo,
--    ghci> arbol
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    ghci> nHojas arbol
--    6
-- ---------------------------------------------------------------------
 
nHojas :: Arbol a -> Int
nHojas Hoja         = 1
nHojas (Nodo x i d) = nHojas i + nHojas d
 
-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    nNodos :: Arbol a -> Int
-- tal que (nNodos x) es el número de nodos del árbol x. Por ejemplo,
--    ghci> arbol
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    ghci> nNodos arbol
--    5
-- ---------------------------------------------------------------------
 
nNodos :: Arbol a -> Int
nNodos Hoja         = 0
nNodos (Nodo x i d) = 1 + nNodos i + nNodos d
 
-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    profundidad :: Arbol a -> Int
-- tal que (profundidad x) es la profundidad del árbol x. Por ejemplo,
--    ghci> arbol
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    ghci> profundidad arbol
--    3
-- ---------------------------------------------------------------------
 
profundidad :: Arbol a -> Int
profundidad Hoja = 0
profundidad (Nodo x i d) = 1 + max (profundidad i) (profundidad d)
 
-- ---------------------------------------------------------------------
-- Ejercicio 4. 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,
--    ghci> arbol
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    ghci> preorden arbol
--    [9,3,2,4,7]
-- ---------------------------------------------------------------------
 
preorden :: Arbol a -> [a]
preorden Hoja         = []
preorden (Nodo x i d) = x : (preorden i ++ preorden d)
 
-- ---------------------------------------------------------------------
-- Ejercicio 5. 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,
--    ghci> arbol
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    ghci> postorden arbol
--    [2,4,3,7,9]
-- ---------------------------------------------------------------------
 
postorden :: Arbol a -> [a]
postorden Hoja         = []
postorden (Nodo x i d) = postorden i ++ postorden d ++ [x]
 
-- ---------------------------------------------------------------------
-- Ejercicio 6. 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,
--    ghci> arbol
--    Nodo 9 (Nodo 3 (Nodo 2 Hoja Hoja) (Nodo 4 Hoja Hoja)) (Nodo 7 Hoja Hoja)
--    ghci> preordenIt arbol
--    [9,3,2,4,7]
-- Nota: No usar (++) en la definición
-- ---------------------------------------------------------------------
 
preordenIt :: Arbol a -> [a]
preordenIt x = preordenItAux x []
    where preordenItAux Hoja xs         = xs
          preordenItAux (Nodo x i d) xs = 
              x : preordenItAux i (preordenItAux d xs)
I1M2013