I1M2011: Patrones de definiciones por recursión en Haskell
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos visto los siguientes patrones de recursión:
- recursión sobre varios argumentos,
- recursión múltiple y
- recursión mutua.
Además, hemos visto una heurística para definir funciones por recursión.
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 13 y 30 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 |
-- --------------------------------------------------------------------- -- 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) -- (ordena xs) es la lista obtenida ordenando xs meciante el algoritmo -- de ordenación rápida. Por ejemplo, -- ordena [2,5,4,7] == [2,4,5,7] ordena :: (Ord a) => [a] -> [a] ordena [] = [] ordena (x:xs) = (ordena menores) ++ [x] ++ (ordena mayores) where menores = [a | a <- xs, a <= x] mayores = [b | b <- xs, b > x] -- --------------------------------------------------------------------- -- Recursión mutua -- -- --------------------------------------------------------------------- -- (par x) se verifica si x es par e (impar x) se verifica si x es -- impar. Por ejemplo, -- par 3 == False -- impar 3 == True par :: Int -> Bool par 0 = True par (n+1) = impar n impar :: Int -> Bool impar 0 = False impar (n+1) = par n -- (pares xs) son los elementos de xs que ocupan posiciones pares e -- (impares xs) son los elementos de xs que ocupan posiciones -- impares. Por ejemplo, -- pares [1,3,5,7] == [1,5] pares :: [a] -> [a] pares [] = [] pares (x:xs) = x : impares xs impares :: [a] -> [a] impares [] = [] impares (_:xs) = pares xs |