I1M2013: Definiciones por recursión (1)
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 y recursión sobre listas.
Las transparencias usadas en la clase son las las páginas 1 a 10 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 |
-- --------------------------------------------------------------------- -- 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 -- -- --------------------------------------------------------------------- -- (producto xs) es el producto de los números de xs. Por ejemplo, -- producto [7,5,2] == 70 producto :: Num a => [a] -> a producto [] = 1 producto (n:ns) = n * producto ns -- (longitud xs) es el número de elementos de xs. Por ejemplo, -- longitud [2,4,5] == 3 longitud :: [a] -> Int longitud [] = 0 longitud (_:xs) = 1 + longitud xs -- (inversa xs) es la inversa de xs. Por ejemplo, -- inversa [2,5,3] == [3,5,2] inversa :: [a] -> [a] inversa [] = [] inversa (x:xs) = inversa xs ++ [x] -- (conc xs ys) es la concatenación de xs e ys. Por ejemplo, -- conc [2,5] [3,5,6] == [2,5,3,5,6] conc :: [a] -> [a] -> [a] conc [] ys = ys conc (x:xs) ys = x : conc 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) |
Como tarea se ha propuesto escribir de manera colaborativa las soluciones de los ejercicios de la 7ª relación.