I1M2011: Ejercicios de definiciones por recursión en Haskell (1)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado las soluciones a los 12 primeros ejercicios de la 6ª relación, que tratan sobre definiciones por recursión.
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 |
-- I1M 2011-12: Rel_6_sol.hs (8 de Noviembre de 2011) -- Definiciones por recursión. -- Departamento de Ciencias de la Computación e I.A. -- Universidad de Sevilla -- ===================================================================== -- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- En esta relación se presentan ejercicios con definiciones por -- recursión correspondientes al tema 6 cuyas transparencias se -- encuentran en -- http://www.cs.us.es/~jalonso/cursos/i1m-11/temas/tema-6.pdf -- --------------------------------------------------------------------- -- Ejercicio 1. Definir por recursión la función -- potencia :: Integer -> Integer -> Integer -- tal que (potencia x n) es x elevado al número natural n. Por ejemplo, -- potencia 2 3 == 8 -- --------------------------------------------------------------------- potencia :: Integer -> Integer -> Integer potencia m 0 = 1 potencia m (n+1) = m*(potencia m n) -- --------------------------------------------------------------------- -- Ejercicio 2. Definir por recursión la función -- and' :: [Bool] -> Bool -- tal que (and' xs) se verifica si todos los elementos de xs son -- verdadero. Por ejemplo, -- and' [1+2 < 4, 2:[3] == [2,3]] == True -- and' [1+2 < 3, 2:[3] == [2,3]] == False -- --------------------------------------------------------------------- and' :: [Bool] -> Bool and' [] = True and' (b:bs) = b && and' bs -- --------------------------------------------------------------------- -- Ejercicio 3. Definir por recursión la función -- concat' :: [[a]] -> [a] -- tal que (concat' xss) es la lista obtenida concatenando las listas de -- xss. Por ejemplo, -- concat' [[1..3],[5..7],[8..10]] == [1,2,3,5,6,7,8,9,10] -- --------------------------------------------------------------------- concat' :: [[a]] -> [a] concat' [] = [] concat' (xs:xss) = xs ++ concat' xss -- --------------------------------------------------------------------- -- Ejercicio 4. Definir por recursión la función -- replicate' :: Int -> a -> [a] -- tal que (replicate' n x) es la lista formado por n copias del -- elemento x. Por ejemplo, -- replicate' 3 2 == [2,2,2] -- --------------------------------------------------------------------- replicate' :: Int -> a -> [a] replicate' 0 _ = [] replicate' (n+1) x = x : replicate' n x -- --------------------------------------------------------------------- -- Ejercicio 5. Definir por recursión la función -- selecciona :: [a] -> Int -> a -- tal que (selecciona xs n) es el n-ésimo elemento de xs. Por ejemplo, -- selecciona [2,3,5,7] 2 == 5 -- --------------------------------------------------------------------- selecciona :: [a] -> Int -> a selecciona (x:_) 0 = x selecciona (_:xs) (n+1) = selecciona xs n -- --------------------------------------------------------------------- -- Ejercicio 6. Definir por recursión la función -- elem' :: Eq a => a -> [a] -> Bool -- tal que (elem' x xs) se verifica si x pertenece a la lista xs. Por -- ejemplo, -- elem' 3 [2,3,5] == True -- elem' 4 [2,3,5] == False -- --------------------------------------------------------------------- elem' :: Eq a => a -> [a] -> Bool elem' x [] = False elem' x (y:ys) | x == y = True | otherwise = elem' x ys -- --------------------------------------------------------------------- -- Ejercicio 7. Definir por recursión la función -- mezcla :: Ord a => [a] -> [a] -> [a] -- tal que (mezcla xs ys) es la lista obtenida mezclando las listas -- ordenadas xs e ys. Por ejemplo, -- mezcla [2,5,6] [1,3,4] == [1,2,3,4,5,6] -- --------------------------------------------------------------------- mezcla :: Ord a => [a] -> [a] -> [a] mezcla [] ys = ys mezcla xs [] = xs mezcla (x:xs) (y:ys) | x <= y = x : mezcla xs (y:ys) | otherwise = y : mezcla (x:xs) ys -- --------------------------------------------------------------------- -- Ejercicio 8. Definir por recursión la función -- ordenada :: Ord a => [a] -> Bool -- tal que (ordenada xs) se verifica si xs es una lista ordenada. Por -- ejemplo, -- ordenada [2,3,5] == True -- ordenada [2,5,3] == False -- --------------------------------------------------------------------- ordenada :: Ord a => [a] -> Bool ordenada [] = True ordenada [_] = True ordenada (x:y:xs) = x <= y && ordenada (y:xs) -- --------------------------------------------------------------------- -- Ejercicio 9. Definir por recursión la función -- borra :: Eq a => a -> [a] -> [a] -- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de -- x en la lista xs. Por ejemplo, -- borra 1 [1,2,1] == [2,1] -- borra 3 [1,2,1] == [1,2,1] -- --------------------------------------------------------------------- borra :: Eq a => a -> [a] -> [a] borra x [] = [] borra x (y:ys) | x == y = ys | otherwise = y : borra x ys -- --------------------------------------------------------------------- -- Ejercicio 10. Definir por recursión la función -- esPermutacion :: Eq a => [a] -> [a] -> Bool -- tal que (esPermutacion xs ys) se verifica si xs es una permutación de -- ys. Por ejemplo, -- esPermutacion [1,2,1] [2,1,1] == True -- esPermutacion [1,2,1] [1,2,2] == False -- --------------------------------------------------------------------- esPermutacion :: Eq a => [a] -> [a] -> Bool esPermutacion [] [] = True esPermutacion [] (y:ys) = False esPermutacion (x:xs) ys = elem x ys && esPermutacion xs (borra x ys) -- --------------------------------------------------------------------- -- Ejercicio 11. Definir la función -- mitades :: [a] -> ([a],[a]) -- tal que (mitades xs) es el par formado por las dos mitades en que se -- divide xs tales que sus longitudes difieren como máximo en uno. Por -- ejemplo, -- mitades [2,3,5,7,9] == ([2,3],[5,7,9]) -- --------------------------------------------------------------------- mitades :: [a] -> ([a],[a]) mitades xs = splitAt (length xs `div` 2) xs -- --------------------------------------------------------------------- -- Ejercicio 12. Definir por recursión la función -- ordMezcla :: Ord a => [a] -> [a] -- tal que (ordMezcla xs) es la lista obtenida ordenado xs por mezcla -- (es decir, considerando que la lista vacía y las listas unitarias -- están ordenadas y cualquier otra lista se ordena mezclando las dos -- listas que resultan de ordenar sus dos mitades por separado). Por -- ejemplo, -- ordMezcla [5,2,3,1,7,2,5] => [1,2,2,3,5,5,7] -- --------------------------------------------------------------------- ordMezcla :: Ord a => [a] -> [a] ordMezcla [] = [] ordMezcla [x] = [x] ordMezcla xs = mezcla (ordMezcla ys) (ordMezcla zs) where (ys,zs) = mitades xs |