I1M2010: Ejercicios de definiciones por plegado (2)
En la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la resolución de ejercicios por plegado, resaltando el paso de las definiciones por recursión a las correspondientes definiciones por plegados. Los ejercicios comentados son el 13 de la 11ª relación y los cuatro primeros de la 12ª relación.
Los ejercicios y su solución se muestran a continuación
|
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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
-- --------------------------------------------------------------------- -- Ejercicio 14. Redefinir, usando foldr, la función filter. Por -- ejemplo, -- filter' (<4) [1,7,3,2] => [1,3,2] -- --------------------------------------------------------------------- -- La definición por recursión es filterR :: (a -> Bool) -> [a] -> [a] filterR p [] = [] filterR p (x:xs) | p x = x : filterR p xs | otherwise = filterR p xs -- La definición por plegado es filter' :: (a -> Bool) -> [a] -> [a] filter' p = foldr g [] where g x y | p x = x:y | otherwise = y -- La definición por plegado y lambda es filter' :: (a -> Bool) -> [a] -> [a] filter' p = foldr (\x y -> if (p x) then (x:y) else y) [] -- --------------------------------------------------------------------- -- Ejercicio 1. Redefinir, mediante plegado, la función maximum. -- --------------------------------------------------------------------- -- La definición por recursión es maximumR :: Ord a => [a] -> a maximumR [x] = x maximumR (x:y:ys) = max y (maximumR (x:ys)) -- La definición por plegado con foldr es maximum' :: Ord a => [a] -> a maximum' (x:xs) = (foldr max x) xs -- La definición de foldr1 es -- foldr1 :: (a -> a -> a) -> [a] -> a -- foldr1 _ [x] = x -- foldr1 f (x:xs) = f x (foldr1 f xs) -- Otra definición por recursión es maximumR' :: Ord a => [a] -> a maximumR' [x] = x maximumR' (x:y:ys) = max x (maximumR' (y:ys)) -- Otra definición, usando foldr1, es maximum'' :: Ord a => [a] -> a maximum'' = foldr1 max -- --------------------------------------------------------------------- -- Ejercicio 2. Redefinir por plegado la función minimum. -- --------------------------------------------------------------------- -- Por analogía con el anterior. -- Definición con foldr: minimum' :: Ord a => [a] -> a minimum' (x:xs) = (foldr min x) xs -- Otra definición, usando foldr1, es minimum'' :: Ord a => [a] -> a minimum'' = foldr1 min -- --------------------------------------------------------------------- -- Ejercicio 3. Definir, usando foldr, la función -- inversaFR :: [a] -> [a] -- tal que (inversaFR xs) es la inversa de la lista xs. Por ejemplo, -- inversaFR [3,5,2,4,7] => [7,4,2,5,3] -- --------------------------------------------------------------------- -- La definición por recursión es inversaR :: [a] -> [a] inversaR [] = [] inversaR (x:xs) = (inversaR xs) ++ [x] -- La definición con foldR es inversaFR :: [a] -> [a] inversaFR = foldr f [] where f x y = y ++ [x] -- La definición anterior puede simplificarse a inversaFR' :: [a] -> [a] inversaFR' = foldr f [] where f x = (++ [x]) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir, usando foldl, la función -- inversaFL :: [a] -> [a] -- tal que (inversaFL xs) es la inversa de la lista xs. Por ejemplo, -- inversaFL [3,5,2,4,7] == [7,4,2,5,3] -- --------------------------------------------------------------------- -- La definición por recursión con acumulador es inversaR' :: [a] -> [a] inversaR' xs = inversaAux [] xs where inversaAux a [] = a inversaAux a (x:xs) = inversaAux (x:a) xs -- La definición de foldl es -- foldl :: (a -> b -> a) -> a -> [b] -> a -- foldl f z0 xs0 = aux z0 xs0 -- where aux z [] = z -- aux z (x:xs) = aux (f z x) xs -- La definción de inversaFL es inversaFL :: [a] -> [a] inversaFL = foldl (\a x -> x:a) [] -- La definción de inversaFL puede simplificarse usando flip: inversaFL' :: [a] -> [a] inversaFL' = foldl (flip(:)) [] |