I1M2013: 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 sobre varios argumento, recursión múltiple y de recursión mutua. También hemos comentado el método para construir funciones recursivas.
Las transparencias usadas en la clase son las las páginas 10 a 24 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 79 80 81 82 83 84 |
-- --------------------------------------------------------------------- -- 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) -- --------------------------------------------------------------------- -- Recursión múltiple -- -- --------------------------------------------------------------------- -- (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 -- --------------------------------------------------------------------- -- Heurísticas para las definiciones recursivas -- -- --------------------------------------------------------------------- -- (init xs) es la lista xs sin el último elemento. Por ejemplo, -- init [3,2,5] == [2,5] init :: [a] -> [a] init [_] = [] init (x:xs) = x : init xs |