I1M2011: Definiciones por recursión en Haskell
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos iniciado el estudio de las definiciones por recursión en Haskell. Concretamente, hemos visto ejemplos de recursión sobre los números naturales, recursión sobre listas, recursión sobre listas que necesitan guardas en el caso recursivo y recursión sobre varios argumentos.
Como tarea para la próxima clase se ha propuesto escribir de manera colaborativa las soluciones de los ejercicios de la 6ª relación.
Las transparencias usadas en la clase son las comprendidas entre las páginas 1 y 11 del tema 6:
El código correspondiente es
|
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 |
-- --------------------------------------------------------------------- -- Librerías auxiliares -- -- --------------------------------------------------------------------- import Prelude hiding (product, reverse, length, (++), zip, drop, init) import Data.Char -- --------------------------------------------------------------------- -- Recursión numérica -- -- --------------------------------------------------------------------- -- (factorial n) es el factorial de n. Por ejemplo, -- factorial 3 == 6 factorial :: Integer -> Integer factorial 0 = 1 factorial (n+1) = (n+1) * factorial n -- (m `por` n) es el producto de m por n. Por ejemplo, -- 3 `por` 2 == 6 por :: Int -> Int -> Int m `por` 0 = 0 m `por` (n + 1) = m + (m `por` n) -- --------------------------------------------------------------------- -- Recusión sobre lista -- -- --------------------------------------------------------------------- -- (product xs) es el producto de los números de xs. Por ejemplo, -- product [7,5,2] == 70 product :: Num a => [a] -> a product [] = 1 product (n:ns) = n * product ns -- (length xs) es el número de elementos de xs. Por ejemplo, -- length [2,4,5] == 3 length :: [a] -> Int length [] = 0 length (_:xs) = 1 + length xs -- (reverse xs) es la inversa de xs. Por ejemplo, -- reverse [2,5,3] == [3,5,2] reverse :: [a] -> [a] reverse [] = [] reverse (x:xs) = reverse xs ++ [x] -- (xs ++ ys) es la concatenación de xs e ys. Por ejemplo, -- [2,5] ++ [3,5,6] == [2,5,3,5,6] (++) :: [a] -> [a] -> [a] [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) -- (inserta e xs) inserta el elemento e en la lista xs delante del -- primer elemento de xs mayor o igual que e. Por ejemplo, -- inserta 5 [2,4,7,3,6,8,10] == [2,4,5,7,3,6,8,10] inserta :: Ord a => a -> [a] -> [a] inserta e [] = [e] inserta e (x:xs) | e <= x = e : (x:xs) | otherwise = x : inserta e xs -- (ordena_por_insercion xs) es la lista xs ordenada mediante inserción, -- Por ejemplo, -- ordena_por_insercion [2,4,3,6,3] == [2,3,3,4,6] ordena_por_insercion :: Ord a => [a] -> [a] ordena_por_insercion [] = [] ordena_por_insercion (x:xs) = inserta x (ordena_por_insercion xs) -- --------------------------------------------------------------------- -- Recursión sobre varios argumentos -- -- --------------------------------------------------------------------- -- (zip xs ys) es la lista de los pares de los elementos de xs e ys en -- la misma posición. Por ejemplo, -- zip [1,3,5] [2,4,6,8] == [(1,2),(3,4),(5,6)] zip :: [a] -> [b] -> [(a, b)] zip [] _ = [] zip _ [] = [] zip (x:xs) (y:ys) = (x,y) : zip xs ys |