I1M2011: Ejercicios sobre tipos algebraicos en Haskell
En la clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los ejercicios de la 18ª relación.
En esta relación se presenta ejercicios sobre tipos de datos algebraicos. Se consideran 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:
- la ocurrencia de un elemento en el árbol,
- el número de hojas
- el carácter balanceado de un árbol,
- el árbol balanceado correspondiente a una lista,
Los ejercicios, y sus soluciones, se muestran a continuación.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
-- --------------------------------------------------------------------- -- Ejercicio 1. Usando el tipo de dato Nat y la función suma definidas -- en las transparencias del tema 9, 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))))) -- --------------------------------------------------------------------- data Nat = Cero | Suc Nat deriving (Eq, Show) suma :: Nat -> Nat -> Nat suma Cero n = n suma (Suc m) n = Suc (suma m n) producto :: Nat -> Nat -> Nat producto Cero _ = Cero producto (Suc m) n = suma n (producto m n) -- --------------------------------------------------------------------- -- Nota. En los siguientes ejercicios 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 2. 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. 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. ¿Porqué la segunda definición de ocurre es más eficiente -- que la primera? -- --------------------------------------------------------------------- -- La nueva definición es más eficiente porque sólo necesita una -- comparación por nodo, mientras que la definición de las -- transparencias necesita dos comparaciones por nodo. -- --------------------------------------------------------------------- -- Nota. En los siguientes ejercicios 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 5. 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 6. 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 7. 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 8. 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 |