I1M2011: Ejercicios con funciones de orden superior en Haskel1
La clase de hoy de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los restantes ejercicios de la 10ª relación y los 6 primeros de la 11ª relación
Los ejercicios, y sus soluciones, se muestran a continuación. Los de la relación 10 son
|
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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 |
-- --------------------------------------------------------------------- -- Ejercicio 4.1. Definir, por recursión con acumulador, la función -- dec2entR :: [Int] -> Int -- tal que (dec2entR xs) es el entero correspondiente a la expresión -- decimal xs. Por ejemplo, -- dec2entR [2,3,4,5] == 2345 -- --------------------------------------------------------------------- dec2entR :: [Int] -> Int dec2entR xs = dec2entR' 0 xs where dec2entR' a [] = a dec2entR' a (x:xs) = dec2entR' (10*a+x) xs -- --------------------------------------------------------------------- -- Ejercicio 4.2. Definir, por plegado con foldl, la función -- dec2entP :: [Int] -> Int -- tal que (dec2entP xs) es el entero correspondiente a la expresión -- decimal xs. Por ejemplo, -- dec2entP [2,3,4,5] == 2345 -- --------------------------------------------------------------------- dec2entP :: [Int] -> Int dec2entP = foldl f 0 where f a x = 10*a+x -- La definición puede simplificarse usando lambda: dec2entP' :: [Int] -> Int dec2entP' = foldl (\a x -> 10*a+x) 0 -- --------------------------------------------------------------------- -- Ejercicio 5.1. Definir, mediante recursión, la función -- sumllR :: Num a => [[a]] -> a -- tal que (sumllR xss) es la suma de las sumas de las listas de xss. -- Por ejemplo, -- sumllR [[1,3],[2,5]] == 11 -- --------------------------------------------------------------------- sumllR :: Num a => [[a]] -> a sumllR [] = 0 sumllR (xs:xss) = sum xs + sumllR xss -- --------------------------------------------------------------------- -- Ejercicio 5.2. Definir, mediante plegado, la función -- sumllP :: Num a => [[a]] -> a -- tal que (sumllP xss) es la suma de las sumas de las listas de xss. Por -- ejemplo, -- sumllP [[1,3],[2,5]] == 11 -- --------------------------------------------------------------------- sumllP :: Num a => [[a]] -> a sumllP = foldr f 0 where f xs n = sum xs + n -- La definición anterior puede simplificarse usando lambda sumllP' :: Num a => [[a]] -> a sumllP' = foldr (\xs n -> sum xs + n) 0 -- --------------------------------------------------------------------- -- Ejercicio 6.1. Definir, mediante recursión, la función -- borraR :: Eq a => a -> a -> [a] -- tal que (borraR y xs) es la lista obtenida borrando las ocurrencias de -- y en xs. Por ejemplo, -- borraR 5 [2,3,5,6] == [2,3,6] -- borraR 5 [2,3,5,6,5] == [2,3,6] -- borraR 7 [2,3,5,6,5] == [2,3,5,6,5] -- --------------------------------------------------------------------- borraR :: Eq a => a -> [a] -> [a] borraR z [] = [] borraR z (x:xs) | z == x = borraR z xs | otherwise = x : borraR z xs -- --------------------------------------------------------------------- -- Ejercicio 6.2. Definir, mediante plegado, la función -- borraP :: Eq a => a -> a -> [a] -- tal que (borraP y xs) es la lista obtenida borrando las ocurrencias de -- y en xs. Por ejemplo, -- borraP 5 [2,3,5,6] == [2,3,6] -- borraP 5 [2,3,5,6,5] == [2,3,6] -- borraP 7 [2,3,5,6,5] == [2,3,5,6,5] -- --------------------------------------------------------------------- borraP :: Eq a => a -> [a] -> [a] borraP z = foldr f [] where f x y | z == x = y | otherwise = x:y -- La definición por plegado con lambda es es borraP' :: Eq a => a -> [a] -> [a] borraP' z = foldr (\x y -> if z==x then y else x:y) [] -- --------------------------------------------------------------------- -- Ejercicio 7.1. Definir, mediante recursión, la función -- diferenciaR :: Eq a => [a] -> [a] -> [a] -- tal que (diferenciaR xs ys) es la diferencia del conjunto xs e ys; es -- decir el conjunto de los elementos de xs que no pertenecen a ys. Por -- ejemplo, -- diferenciaR [2,3,5,6] [5,2,7] == [3,6] -- --------------------------------------------------------------------- diferenciaR :: Eq a => [a] -> [a] -> [a] diferenciaR xs ys = aux xs xs ys where aux a xs [] = a aux a xs (y:ys) = aux (borra y a) xs ys -- La definición, para aproximarse al patrón foldr, se puede escribir como diferenciaR' :: Eq a => [a] -> [a] -> [a] diferenciaR' xs ys = aux xs xs ys where aux a xs [] = a aux a xs (y:ys) = aux (flip borra a y) xs ys -- --------------------------------------------------------------------- -- Ejercicio 7.2. Definir, mediante plegado con foldl, la función -- diferenciaP :: Eq a => [a] -> [a] -> [a] -- tal que (diferenciaP xs ys) es la diferencia del conjunto xs e ys; es -- decir el conjunto de los elementos de xs que no pertenecen a ys. Por -- ejemplo, -- diferenciaP [2,3,5,6] [5,2,7] == [3,6] -- --------------------------------------------------------------------- diferenciaP :: Eq a => [a] -> [a] -> [a] diferenciaP xs ys = foldl (flip borra) xs ys -- La definición anterior puede simplificarse a diferenciaP' :: Eq a => [a] -> [a] -> [a] diferenciaP' = foldl (flip borra) |
Los de la relación 11 son
|
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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
-- --------------------------------------------------------------------- -- Introducción -- -- --------------------------------------------------------------------- -- En esta relación se va a modificar el programa de transmisión de -- cadenas para detectar errores de transmisión sencillos usando bits de -- paridad. Es decir, cada octeto de ceros y unos generado durante la -- codificación se extiende con un bit de paridad que será un uno si el -- número contiene un número impar de unos y cero en caso contrario. En -- la decodificación, en cada número binario de 9 cifras debe -- comprobarse que la paridad es correcta, en cuyo caso se descarta el -- bit de paridad. En caso contrario, debe generarse un mensaje de error -- en la paridad. -- -- Los ejercicios de esta relación corresponden al tema 7 cuyas -- transparencias se encuentran en -- http://www.cs.us.es/~jalonso/cursos/i1m-10/temas/tema-7.pdf -- --------------------------------------------------------------------- -- Importación de librerías auxiliares -- -- --------------------------------------------------------------------- import Data.Char -- --------------------------------------------------------------------- -- Notas. Se usarán las siguientes definiciones del tema -- --------------------------------------------------------------------- type Bit = Int bin2int :: [Bit] -> Int bin2int = foldr (\x y -> x + 2*y) 0 int2bin :: Int -> [Bit] int2bin 0 = [] int2bin n = n `mod` 2 : int2bin (n `div` 2) creaOcteto :: [Bit] -> [Bit] creaOcteto bs = take 8 (bs ++ repeat 0) -- La definición anterior puede simplificarse a creaOcteto' :: [Bit] -> [Bit] creaOcteto' = take 8 . (++ repeat 0) -- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- paridad :: [Bit] -> Bit -- tal que (paridad bs) es el bit de paridad de bs; es decir, 1 si bs -- contiene un número impar de unos y 0 en caso contrario. Por ejemplo, -- paridad [0,1,1] => 0 -- paridad [0,1,1,0,1] => 1 -- --------------------------------------------------------------------- paridad :: [Bit] -> Bit paridad bs | odd (sum bs) = 1 | otherwise = 0 -- --------------------------------------------------------------------- -- Ejercicio 2. Definir la función -- agregaParidad :: [Bit] -> [Bit] -- tal que (agregaParidad bs) es la lista obtenida añadiendo al -- principio de bs su paridad. Por ejemplo, -- agregaParidad [0,1,1] => [0,0,1,1] -- agregaParidad [0,1,1,0,1] => [1,0,1,1,0,1] -- --------------------------------------------------------------------- agregaParidad :: [Bit] -> [Bit] agregaParidad bs = (paridad bs) : bs -- --------------------------------------------------------------------- -- Ejercicio 3. Definir la función -- codifica :: String -> [Bit] -- tal que (codifica c) es la codificación de la cadena c como una lista -- de bits obtenida convirtiendo cada carácter en un número Unicode, -- convirtiendo cada uno de dichos números en un octeto con su paridad y -- concatenando los octetos con paridad para obtener una lista de -- bits. Por ejemplo, -- *Main> codifica "abc" -- [1,1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0] -- --------------------------------------------------------------------- codifica :: String -> [Bit] codifica = concat . map (agregaParidad . creaOcteto . int2bin . ord) -- --------------------------------------------------------------------- -- Ejercicio 4. Definir la función -- separa9 :: [Bit] -> [[Bit]] -- tal que (separa9 bs)} es la lista obtenida separando la lista de bits -- bs en listas de 9 elementos. Por ejemplo, -- *Main> separa9 [1,1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0] -- [[1,1,0,0,0,0,1,1,0],[1,0,1,0,0,0,1,1,0],[0,1,1,0,0,0,1,1,0]] -- --------------------------------------------------------------------- separa9 :: [Bit] -> [[Bit]] separa9 [] = [] separa9 bits = take 9 bits : separa9 (drop 9 bits) -- --------------------------------------------------------------------- -- Ejercicio 5. Definir la función -- compruebaParidad :: [Bit] -> [Bit ] -- tal que (compruebaParidad bs) es el resto de bs si el primer elemento -- de bs es el bit de paridad del resto de bs y devuelve error de -- paridad en caso contrario. Por ejemplo, -- *Main> compruebaParidad [1,1,0,0,0,0,1,1,0] -- [1,0,0,0,0,1,1,0] -- *Main> compruebaParidad [0,1,0,0,0,0,1,1,0] -- *** Exception: paridad erronea -- Usar la función del preludio -- error :: String -> a -- tal que (error c) devuelve la cadena c. -- --------------------------------------------------------------------- compruebaParidad :: [Bit] -> [Bit ] compruebaParidad (b:bs) | b == paridad bs = bs | otherwise = error "paridad erronea" -- --------------------------------------------------------------------- -- Ejercicio 6. Definir la función -- descodifica :: [Bit] -> String -- tal que (descodifica bs) es la cadena correspondiente a la lista de -- bits con paridad. Para ello, en cada número binario de 9 cifras debe -- comprobarse que la paridad es correcta, en cuyo caso se descarta el -- bit de paridad. En caso contrario, debe generarse un mensaje de error -- en la paridad. Por ejemplo, -- descodifica [1,1,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0] -- => "abc" -- descodifica [1,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,1,1,0,0,0,1,1,0] -- => *** Exception: paridad erronea -- --------------------------------------------------------------------- descodifica :: [Bit] -> String descodifica = map (chr . bin2int . compruebaParidad) . separa9 |