I1M2012: Definiciones por recursión (2)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos continuado el estudio de las definiciones por recursión en Haskell. Concretamente, hemos visto ejemplos de recursión con guardas, recursión sobre varios argumentos y recursión múltiple.
Las transparencias usadas en la clase son las comprendidas entre las páginas 10 y 13 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 |
-- (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 -- (drop n xs) es la lista obtenida eliminando los n primeros elementos -- de xs. Por ejemplo, -- drop 2 [5,7,9,4] == [9,4] -- drop 5 [1,4] == [] drop :: Int -> [a] -> [a] drop 0 xs = xs drop (n+1) [] = [] drop (n+1) (x:xs) = drop n xs -- --------------------------------------------------------------------- -- Recursión múltiple -- -- --------------------------------------------------------------------- -- (fibonacci n) es el n--ésimo término de la sucesión de Fibonacci. Por -- ejemplo, -- fibonacci 8 == 21 fibonacci :: Int -> Int fibonacci 0 = 0 fibonacci 1 = 1 fibonacci (n+2) = fibonacci n + fibonacci (n+1) |