{"id":1155,"date":"2011-01-10T08:00:53","date_gmt":"2011-01-10T08:00:53","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1155"},"modified":"2013-03-08T05:50:04","modified_gmt":"2013-03-08T05:50:04","slug":"i1m2010-ejercicios-de-haskell-relaciones-12-y-13","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2010-ejercicios-de-haskell-relaciones-12-y-13\/","title":{"rendered":"I1M2010: Ejercicios de Haskell (relaciones 12 y 13)"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado la resoluci\u00f3n de ejercicios de la 12\u00aa relaci\u00f3n<\/a> y de ka 13\u00aa relaci\u00f3n<\/a>.<\/p>\n

Los ejercicios de la relaci\u00f3n 12 y su soluci\u00f3n se muestran a continuaci\u00f3n
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir, usando foldr, la funci\u00f3n\r\n--    inversaFR :: [a] -> [a]\r\n-- tal que (inversaFR xs) es la inversa de la lista xs. Por ejemplo,\r\n--    inversaFR [3,5,2,4,7]  =>  [7,4,2,5,3]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\ninversaR :: [a] -> [a]\r\ninversaR [] = []\r\ninversaR (x:xs) = (inversaR xs) ++ [x]\r\n\r\n-- La definici\u00f3n con foldR es\r\ninversaFR :: [a] -> [a]\r\ninversaFR = foldr f []\r\n    where f x y = y ++ [x]\r\n\r\n-- La definici\u00f3n anterior puede simplificarse a\r\ninversaFR' :: [a] -> [a]\r\ninversaFR' = foldr f []\r\n    where f x = (++ [x])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir, usando foldl, la funci\u00f3n\r\n--    inversaFL :: [a] -> [a]\r\n-- tal que (inversaFL xs) es la inversa de la lista xs. Por ejemplo,\r\n--    inversaFL [3,5,2,4,7]  ==  [7,4,2,5,3]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n con acumulador es\r\ninversaR' :: [a] -> [a]\r\ninversaR' xs = inversaAux [] xs\r\n    where inversaAux a []     = a\r\n          inversaAux a (x:xs) = inversaAux (x:a) xs\r\n\r\n-- La definici\u00f3n de foldl es\r\n--    foldl :: (a -> b -> a) -> a -> [b] -> a\r\n--    foldl f z0 xs0 = aux z0 xs0\r\n--        where aux z []     = z\r\n--              aux z (x:xs) = aux (f z x) xs\r\n\r\n-- La definci\u00f3n de inversaFL es\r\ninversaFL :: [a] -> [a]\r\ninversaFL = foldl (\\a x -> x:a) []\r\n\r\n-- La definci\u00f3n de inversaFL puede simplificarse usando flip:\r\ninversaFL' :: [a] -> [a]\r\ninversaFL' = foldl (flip(:)) []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Comprobar con QuickCheck que las funciones reverse,\r\n-- inversaFR e inversaFL son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_inversa :: Eq a => [a] -> Bool\r\nprop_inversa xs =\r\n    inversaFR xs == ys &&\r\n    inversaFL xs == ys \r\n    where ys = reverse xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_inversa\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Comparar la eficiencia de inversaFR e inversaFL\r\n-- calculando el tiempo y el espacio que usado en evaluar las siguientes\r\n-- expresiones: \r\n--    head (inversaFR [1..100000])\r\n--    head (inversaFL [1..100000])\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La sesi\u00f3n es\r\n--    *Main> :set +s\r\n--    *Main> head (inversaFR [1..100000])\r\n--    100000\r\n--    (0.41 secs, 20882460 bytes)\r\n--    *Main> head (inversaFL [1..100000])\r\n--    1\r\n--    (0.00 secs, 525148 bytes)\r\n--    *Main> :unset +s\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir, la funci\u00f3n\r\n--    dec2ent :: [Int] -> Int\r\n-- tal que (dec2ent xs) es el entero correspondiente a la expresi\u00f3n\r\n-- decimal xs. Por ejemplo,\r\n--    dec2ent [2,3,4,5]  ==  2345\r\n-- Escribir dos definiciones:\r\n-- * dec2entR por recursi\u00f3n\r\n-- * dec2entF usando foldl\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\ndec2entR :: [Int] -> Int\r\ndec2entR xs = dec2entR' 0 xs\r\n    where dec2entR' a []     = a\r\n          dec2entR' a (x:xs) = dec2entR' (10*a+x) xs\r\n\r\n-- La definici\u00f3n usando foldl es\r\ndec2entF :: [Int] -> Int\r\ndec2entF = foldl f 0\r\n    where f a x = 10*a+x\r\n\r\n-- La definici\u00f3n usando foldl y lambda es\r\ndec2entF' :: [Int] -> Int\r\ndec2entF' = foldl (\\a x -> 10*a+x) 0\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir, mediante plegado, la funci\u00f3n\r\n--    sumll :: Num a => [[a]] -> a\r\n-- tal que (sumll xss) es la suma de las sumas de las listas de xss. Por\r\n-- ejemplo, \r\n--    sumll [[1,3],[2,5]]  ==  11\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\nsumllR :: Num a => [[a]] -> a\r\nsumllR [] = 0\r\nsumllR (x:xs) = sum x + sumllR xs\r\n\r\n-- La definici\u00f3n por plegado es\r\nsumll :: Num a => [[a]] -> a\r\nsumll = foldr (\\x y -> sum x + y) 0\r\n\r\n-- La anterior definici\u00f3n puede simplificarse, teniendo en cuenta que\r\n--   sum = foldr (+) 0\r\n-- como sigue\r\n--    sumll = foldr (\\x y -> sum x + y) 0\r\n--          = foldr (\\x y -> ((foldr (+) 0) x) + y) 0\r\n--          = foldl (\\x y -> ((foldl (+) y) x)) 0\r\n--          = foldl (foldl (+)) 0\r\nsumll' :: Num a => [[a]] -> a\r\nsumll' = foldl (foldl (+)) 0\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir, mediante plegado, la funci\u00f3n\r\n--    borra :: Eq a => a -> a -> [a]\r\n-- tal que (borra y xs) es la lista obtenida borrando las ocurrencias de\r\n-- y en xs. Por ejemplo, \r\n--    borra 5 [2,3,5,6]    ==  [2,3,6]\r\n--    borra 5 [2,3,5,6,5]  ==  [2,3,6]\r\n--    borra 7 [2,3,5,6,5]  ==  [2,3,5,6,5]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n de borra por recursi\u00f3n es\r\nborraR :: Eq a => a -> [a] -> [a]\r\nborraR z [] = []\r\nborraR z (x:xs) | z == x    = borraR z xs\r\n                | otherwise = x : borraR z xs\r\n\r\n-- La definici\u00f3n por plegado es\r\nborra :: Eq a => a -> [a] -> [a]\r\nborra z = foldr f []\r\n    where f x y | z == x    = y\r\n                | otherwise = x:y\r\n\r\n-- La definici\u00f3n por plegado con lambda es es\r\nborra' :: Eq a => a -> [a] -> [a]\r\nborra' z = foldr (\\x y -> if z==x then y else x:y) []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir, mediante plegado, la funci\u00f3n\r\n--    diferencia :: Eq a => [a] -> [a] -> [a]\r\n-- tal que (diferencia xs ys) es la diferencia del conjunto xs e ys; es\r\n-- decir el conjunto de los elementos de xs que no pertenecen a ys. Por\r\n-- ejemplo,  \r\n--    diferencia [2,3,5,6] [5,2,7]  ==  [3,6]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\ndiferenciaR :: Eq a => [a] -> [a] -> [a]\r\ndiferenciaR xs ys = aux xs xs ys\r\n    where aux a xs []     = a\r\n          aux a xs (y:ys) = aux (borra y a) xs ys \r\n\r\n-- La definici\u00f3n, para aproximarse al patr\u00f3n foldr, se puede escribir como\r\ndiferenciaR' :: Eq a => [a] -> [a] -> [a]\r\ndiferenciaR' xs ys = aux xs xs ys\r\n    where aux a xs []     = a\r\n          aux a xs (y:ys) = aux (flip borra a y) xs ys \r\n\r\n-- La definici\u00f3n por plegado es\r\ndiferencia :: Eq a => [a] -> [a] -> [a]\r\ndiferencia xs ys = foldl (flip borra) xs ys\r\n\r\n-- La definici\u00f3n anterior puede simplificarse a\r\ndiferencia' :: Eq a => [a] -> [a] -> [a]\r\ndiferencia' = foldl (flip borra)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. En el tema se ha definido la funci\u00f3n\r\n--    composicionLista :: [a -> a] -> (a -> a)\r\n-- tal que (composicionLista fs) es la composici\u00f3n de la lista de\r\n-- funciones fs. Por ejemplo,\r\n--    composicionLista [(*2),(^2)] 3        ==  18\r\n--    composicionLista [(^2),(*2)] 3        ==  36\r\n--    composicionLista [(\/9),(^2),(*2)] 3   ==  4.0\r\n-- La definici\u00f3n es\r\n--    composicionLista = foldr (.) id\r\n-- \r\n-- Explicar por qu\u00e9 la siguiente definici\u00f3n no es v\u00e1lida: \r\n--    sumaCuadradosPares = \r\n--        composicionLista [sum, map (^2), filter even]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El argumento de composicionLista tiene que ser una lista de funciones\r\n-- del mismo tipo y las funciones de la lista \r\n--    [sum, map (^2), filter even]\r\n-- no tienen el mismo tipo. En efecto,\r\n--    sum         :: [Int] -> Int\r\n--    map (^2)    :: [Int] -> [Int]\r\n--    filter even :: [Int] -> [Int]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Se define el siguiente patr\u00f3n\r\n--    unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]\r\n--    unfold p h t x | p x       = []\r\n--                   | otherwise = h x : unfold p h t (t x)\r\n-- Con el patr\u00f3n unfold pueden simplificarse algunas definiciones. Por\r\n-- ejemplo, en el tema se ha definido la funci\u00f3n \r\n--    int2bin :: Int -> [Int]\r\n-- tal que (int2bin x) es el n\u00famero binario correspondiente al n\u00famero\r\n-- decimal x. Por ejemplo,\r\n--    int2bin 13  =>  [1,0,1,1]\r\n-- La definici\u00f3n en el tema es\r\n--    int2bin 0 = []\r\n--    int2bin n = n `mod` 2 : int2bin (n `div` 2)\r\n-- Usando unfold, int2bin puede definirse como\r\n--    int2bin = unfold (== 0) (`mod` 2) (`div` 2)\r\n-- ---------------------------------------------------------------------\r\n\r\nunfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]\r\nunfold p h t x | p x       = []\r\n               | otherwise = h x : unfold p h t (t x)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Redefinir, usando unfold, la funci\u00f3n definida en el\r\n-- tema \r\n--    separaOctetos :: [Int] -> [[Int]]\r\n-- tal que (separaOctetos bs) es la lista obtenida separando la lista de\r\n-- bits bs en listas de 8 elementos. Por ejemplo,\r\n--    *Main> separaOctetos [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0]\r\n--    [[1,0,0,0,0,1,1,0],[0,1,0,0,0,1,1,0]]\r\n-- Comprobar con quickCheck la equivalencia de las definiciones.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n en el tema es\r\nseparaOctetos :: [Int] -> [[Int]]\r\nseparaOctetos [] = []\r\nseparaOctetos bs = take 8 bs : separaOctetos (drop 8 bs)\r\n\r\n-- La definici\u00f3n con unfold es\r\nseparaOctetos' :: [Int] -> [[Int]]\r\nseparaOctetos' = unfold null (take 8) (drop 8)\r\n\r\n-- La propiedad es\r\nprop_separaOctetos xs =\r\n    separaOctetos' xs == separaOctetos xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_separaOctetos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Redefinir, usando unfold, la funci\u00f3n map. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n es\r\nmap'' :: (a -> b) -> [a] -> [b]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. En este ejercicio se va a modificar el programa de\r\n-- transmisi\u00f3n de cadenas para detectar errores de transmisi\u00f3n sencillos\r\n-- usando bits de paridad. Es decir, cada octeto de ceros y unos\r\n-- generado durante la codificaci\u00f3n se extiende con un bit de paridad\r\n-- que ser\u00e1 un uno si el n\u00famero contiene un n\u00famero impar de unos y cero\r\n-- en caso contrario. En la decodificaci\u00f3n, en cada n\u00famero binario de 9\r\n-- cifras debe comprobarse que la paridad es correcta, en cuyo caso se\r\n-- descarta el bit de paridad. En caso contrario, debe generarse un\r\n-- mensaje de error en la paridad. \r\n-- \r\n-- Se usar\u00e1n las siguientes definiciones del tema\r\n-- ---------------------------------------------------------------------\r\n\r\ntype Bit = Int  \r\n\r\nbin2int :: [Bit] -> Int\r\nbin2int =  foldr (\\x y -> x + 2*y) 0\r\n\r\nint2bin :: Int -> [Bit]\r\nint2bin 0 =  []\r\nint2bin n =  n `mod` 2 : int2bin (n `div` 2)\r\n\r\ncreaOcteto :: [Bit] -> [Bit]\r\ncreaOcteto bs =  take 8 (bs ++ repeat 0)\r\n\r\n-- La definici\u00f3n anterior puede simplificarse a\r\ncreaOcteto' :: [Bit] -> [Bit]\r\ncreaOcteto' =  take 8 . (++ repeat 0)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 16. Definir la funci\u00f3n\r\n--    paridad :: [Bit] -> Bit\r\n-- tal que (paridad bs) es el bit de paridad de bs; es decir, 1 si bs\r\n-- contiene un n\u00famero impar de unos y 0 en caso contrario. Por ejemplo, \r\n--    paridad [0,1,1]      =>  0\r\n--    paridad [0,1,1,0,1]  =>  1\r\n-- ---------------------------------------------------------------------\r\n\r\nparidad :: [Bit] -> Bit\r\nparidad bs | odd (sum bs)  = 1\r\n           | otherwise     = 0\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 17. Definir la funci\u00f3n\r\n--    agregaParidad :: [Bit] -> [Bit]\r\n-- tal que (agregaParidad bs) es la lista obtenida a\u00f1adiendo al\r\n-- principio de bs su paridad. Por ejemplo,\r\n--    agregaParidad [0,1,1]      =>  [0,0,1,1]\r\n--    agregaParidad [0,1,1,0,1]  =>  [1,0,1,1,0,1]\r\n-- ---------------------------------------------------------------------\r\n\r\nagregaParidad :: [Bit] -> [Bit]\r\nagregaParidad bs = (paridad bs) : bs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 18. Definir la funci\u00f3n\r\n--    codifica :: String -> [Bit]\r\n-- tal que (codifica c) es la codificaci\u00f3n de la cadena c como una lista\r\n-- de bits obtenida convirtiendo cada car\u00e1cter en un n\u00famero Unicode,\r\n-- convirtiendo cada uno de dichos n\u00fameros en un octeto con su paridad y\r\n-- concatenando los octetos con paridad para obtener una lista de\r\n-- bits. Por ejemplo, \r\n--    *Main> codifica \"abc\"\r\n--    [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]\r\n-- ---------------------------------------------------------------------\r\n\r\ncodifica :: String -> [Bit]\r\ncodifica = concat . map (agregaParidad . creaOcteto . int2bin . ord)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 19. Definir la funci\u00f3n\r\n--    separa9 :: [Bit] -> [[Bit]]\r\n-- tal que (separa9 bs)} es la lista obtenida separando la lista de bits\r\n-- bs en listas de 9 elementos. Por ejemplo, \r\n--    *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]\r\n--    [[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]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsepara9 :: [Bit] -> [[Bit]]\r\nsepara9 []   = []\r\nsepara9 bits = take 9 bits : separa9 (drop 9 bits)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 20. Definir la funci\u00f3n\r\n--    compruebaParidad :: [Bit] -> [Bit ]\r\n-- tal que (compruebaParidad bs) es el resto de bs si el primer elemento\r\n-- de bs es el bit de paridad del resto de bs y devuelve error de\r\n-- paridad en caso contrario. Por ejemplo,\r\n--    *Main> compruebaParidad [1,1,0,0,0,0,1,1,0]\r\n--    [1,0,0,0,0,1,1,0]\r\n--    *Main> compruebaParidad [0,1,0,0,0,0,1,1,0]\r\n--    *** Exception: paridad erronea\r\n-- Usar la funci\u00f3n del preludio\r\n--    error :: String -> a\r\n-- tal que (error c) devuelve la cadena c.\r\n-- ---------------------------------------------------------------------\r\n\r\ncompruebaParidad :: [Bit] -> [Bit ]\r\ncompruebaParidad (b:bs)\r\n    | b == paridad bs = bs\r\n    | otherwise       = error \"paridad erronea\"\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 21. Definir la funci\u00f3n\r\n--    descodifica :: [Bit] -> String\r\n-- tal que (descodifica bs) es la cadena correspondiente a la lista de\r\n-- bits con paridad. Para ello, en cada n\u00famero binario de 9 cifras debe\r\n-- comprobarse que la paridad es correcta, en cuyo caso se descarta el\r\n-- bit de paridad. En caso contrario, debe generarse un mensaje de error\r\n-- en la paridad. Por ejemplo,   \r\n--    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]\r\n--    =>  \"abc\"\r\n--    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]\r\n--    =>  \"*** Exception: paridad erronea\r\n-- ---------------------------------------------------------------------\r\n   \r\ndescodifica :: [Bit] -> String\r\ndescodifica = map (chr . bin2int . compruebaParidad) . separa9\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 22. Se define la funci\u00f3n\r\ntransmite :: ([Bit] -> [Bit]) -> String -> String\r\ntransmite canal =  descodifica . canal . codifica\r\n-- tal que (transmite c t) es la cadena obtenida transmitiendo la cadena\r\n-- t a trav\u00e9s del canal c. Calcular el reultado de trasmitir la cadena\r\n-- \"Conocete a ti mismo\" por el canal identidad (id) y del canal que\r\n-- olvida el primer bit (tail).\r\n-- ---------------------------------------------------------------------\r\n\r\n--    *Main> transmite id \"Conocete a ti mismo\"\r\n--    \"Conocete a ti mismo\"\r\n--    *Main> transmite tail \"Conocete a ti mismo\"\r\n--    \"*** Exception: paridad erronea\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 23. [La identidad de Bezout] Definir la funci\u00f3n\r\n--    bezout :: Integer -> Integer -> (Integer, Integer)\r\n-- tal que (bezout a b) es un par de n\u00fameros x e y tal que a*x+b*y es el\r\n-- m\u00e1ximo com\u00fan divisor de a y b. Por ejemplo,\r\n--    bezout 12 30  ==  (-2,1)\r\n-- Indicaci\u00f3n: Se puede usar la funci\u00f3n quotRem tal que (quotRem x y) es\r\n-- el par formado por el ciciente y el resto de dividir x entre y.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Ejemplo de c\u00e1lculo\r\n--    a  b   q r  \r\n--    12 30  0 12  (-1,1-0*(-1)) = (-1,1)\r\n--    30 12  1 18  (1,0-1*1)     = (1,-1)\r\n--    12 18  0 18  (0,1-0*0)     = (0,1)\r\n--    18 18  1  0  (1,0) \r\n\r\nbezout :: Integer -> Integer -> (Integer, Integer)\r\nbezout _ 0 = (1,0)\r\nbezout _ 1 = (0,1)\r\nbezout a b = (y, x - q*y)\r\n    where (x,y) = bezout b r\r\n          (q,r) = quotRem a b\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 24. Comprobar con QuickCheck que si a>0, b>0 y \r\n-- (x,y) es el valor de (bezout a b), entonces a*x+b*y es igual al\r\n-- m\u00e1ximo com\u00fan divisor de a y b.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_Bezout :: Integer -> Integer -> Property\r\nprop_Bezout a b = a>0 && b>0 ==> a*x+b*y == gcd a b\r\n    where (x,y) = bezout a b          \r\n\r\n-- La comprobaci\u00f3n es\r\n--   Main> quickCheck prop_Bezout\r\n--   OK, passed 100 tests.\r\n<\/pre>\n
Los ejercicios de la relaci\u00f3n 13 y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n
\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n \r\n--    ullman :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\n-- tal que (ullman t k xs) se verifica si xs tiene un subconjunto con k \r\n-- elementos cuya suma sea menor que t. Por ejemplo,\r\n--    ullman 9 3 [1..10] == True\r\n--    ullman 5 3 [1..10] == False\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa soluci\u00f3n (corta y eficiente)\r\nullman :: (Ord a, Num a) => a -> Int -> [a] -> Bool\r\nullman t k xs = sum (take k (sort xs)) < t\r\n\r\n-- 2\u00aa soluci\u00f3n (larga e ineficiente)\r\nullman2 :: (Num a, Ord a) => a -> Int -> [a] -> Bool\r\nullman2 t k xs = \r\n    [ys | ys <- subconjuntos xs, length ys == k, sum ys < t] \/= []\r\n\r\n-- (subconjuntos xs) es la lista de los subconjuntos de xs. Por \r\n-- ejemplo,\r\n--    subconjuntos \"bc\"  ==  [\"\",\"c\",\"b\",\"bc\"]\r\n--    subconjuntos \"abc\" ==  [\"\",\"c\",\"b\",\"bc\",\"a\",\"ac\",\"ab\",\"abc\"]\r\nsubconjuntos :: [a] -> [[a]]\r\nsubconjuntos [] = [[]]\r\nsubconjuntos (x:xs) = zss++[x:ys | ys <- zss]\r\n    where zss = subconjuntos xs\r\n\r\n-- Los siguientes ejemplos muestran la diferencia en la eficencia:\r\n--    *Main> ullman 9 3 [1..20]\r\n--    True\r\n--    (0.02 secs, 528380 bytes)\r\n--    *Main> ullman2 9 3 [1..20]\r\n--    True\r\n--    (4.08 secs, 135267904 bytes)\r\n--    *Main> ullman 9 3 [1..100]\r\n--    True\r\n--    (0.02 secs, 526360 bytes)\r\n--    *Main> ullman2 9 3 [1..100]\r\n--      C-c C-cInterrupted.\r\n--    Agotado\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n--    sumasDe2Cuadrados :: Integer -> [(Integer, Integer)]\r\n-- tal que (sumasDe2Cuadrados n) es la lista de los pares de n\u00fameros\r\n-- tales que la suma de sus cuadrados es n y el primer elemento del par\r\n-- es mayor o igual que el segundo. Por ejemplo,\r\n--    sumasDe2Cuadrados 25  ==  [(5,0),(4,3)]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Primera definici\u00f3n:\r\nsumasDe2Cuadrados_1 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_1 n = \r\n    [(x,y) | x <- [n,n-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n\r\n-- Segunda definici\u00f3n:\r\nsumasDe2Cuadrados_2 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_2 n = \r\n    [(x,y) | x <- [a,a-1..0],\r\n             y <- [0..x],\r\n             x*x+y*y == n]\r\n    where a = ceiling (sqrt (fromIntegral n))\r\n\r\n-- Tercera definici\u00f3n:\r\nsumasDe2Cuadrados_3 :: Integer -> [(Integer, Integer)]\r\nsumasDe2Cuadrados_3 n = aux (ceiling (sqrt (fromIntegral n))) 0 where\r\n    aux x y | x < y          = [] \r\n            | x*x + y*y <  n = aux x (y+1)\r\n            | x*x + y*y == n = (x,y) : aux (x-1) (y+1)\r\n            | otherwise      = aux (x-1) y\r\n\r\n-- Comparaci\u00f3n\r\n--    +----------+---------------+---------------+---------------+\r\n--    | n        | 1\u00aa definici\u00f3n | 2\u00aa definici\u00f3n | 3\u00aa definici\u00f3n |\r\n--    +----------+---------------+---------------+---------------+\r\n--    |      999 | 2.17 segs     |   0.02 segs   | 0.01 segs     |  \r\n--    | 48612265 |               | 140.38 segs   | 0.13 segs     |\r\n--    +----------+---------------+---------------+---------------+\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. (Basado en el problema 145 del Proyecto Euler). Se dice\r\n-- que un n\u00famero n es reversible si su \u00faltima cifra es distinta de 0 y\r\n-- la suma de n y el n\u00famero obtenido escribiendo las cifras de n en\r\n-- orden inverso es un n\u00famero que tiene todas sus cifras impares. Por\r\n-- ejemplo, 36 es reversible porque 36+63=99 tiene todas sus cifras\r\n-- impares, 409 es reversible porque 409+904=1313 tiene todas sus cifras\r\n-- impares,  243 no es reversible porque 243+342=585 no tiene todas sus\r\n-- cifras impares. \r\n-- Definir la funci\u00f3n \r\n--    reversiblesMenores :: Int -> Int\r\n-- tal que (reversiblesMenores n) es la cantidad de n\u00fameros reversibles\r\n-- menores que n. Por ejemplo,\r\n--    reversiblesMenores 10   == 0\r\n--    reversiblesMenores 100  == 20\r\n--    reversiblesMenores 1000 == 120\r\n-- ---------------------------------------------------------------------\r\n\r\nreversiblesMenores :: Int -> Int\r\nreversiblesMenores n = length [x | x <- [1..n-1], esReversible x]\r\n\r\n-- (esReversible n) se verifica si n es reversible; es decir, si su\r\n-- \u00faltima cifra es distinta de 0 y la suma de n y el n\u00famero obtenido\r\n-- escribiendo las cifras de n en orden inverso es un n\u00famero que tiene\r\n-- todas sus cifras impares. Por ejemplo,\r\n--    esReversible 36  == True\r\n--    esReversible 409 == True\r\nesReversible :: Int -> Bool\r\nesReversible n = rem n 10 \/= 0 && impares (cifras (n + (inverso n)))\r\n\r\n-- (impares xs) se verifica si xs es una lista de n\u00fameros impares. Por\r\n-- ejemplo, \r\n--    impares [3,5,1] == True\r\n--    impares [3,4,1] == False\r\nimpares :: [Int] -> Bool\r\nimpares xs = and [odd x | x <- xs]\r\n\r\n-- (inverso n) es el n\u00famero obtenido escribiendo las cifras de n en\r\n-- orden inverso. Por ejemplo,\r\n--    inverso 3034 == 4303\r\ninverso :: Int -> Int\r\ninverso n = read (reverse (show n))\r\n\r\n-- (cifras n) es la lista de las cifras del n\u00famero n. Por ejemplo,\r\n--    cifras 3034 == [3,0,3,4]\r\ncifras :: Int -> [Int]\r\ncifras n = [read [x] | x <- show n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, usando funciones de orden superior, la funci\u00f3n\r\n--    grafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]\r\n-- tal que (grafoReducido f p xs) es la lista (sin repeticiones) de los\r\n-- pares formados por los elementos de xs que verifican el predicado p\r\n-- y sus im\u00e1genes. Por ejemplo, \r\n--    grafoReducido (^2) even [1..9]  ==  [(2,4),(4,16),(6,36),(8,64)]\r\n--    grafoReducido (+4) even (replicate 40 1) == []\r\n--    grafoReducido (*5) even (replicate 40 2) == [(2,10)]\r\n-- ---------------------------------------------------------------------\r\n\r\ngrafoReducido :: Eq a => (a -> b) -> (a -> Bool) -> [a] -> [(a,b)]\r\ngrafoReducido f p xs = [(x,f x) | x <- nub xs, p x]\r\n\r\n-- -------------------------------------------------------------------\r\n-- Ejercicio 6.1. Un n\u00famero natural n se denomina semiperfecto si es la\r\n-- suma de algunos de sus divisores propios. Por ejemplo, 18 es\r\n-- semiperfecto ya que sus divisores son 1, 2, 3, 6, 9 y se cumple que\r\n-- 3+6+9=18.  \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    esSemiPerfecto :: Int -> Bool\r\n-- tal que (esSemiPerfecto n) se verifica si n es semiperfecto. Por\r\n-- ejemplo, \r\n--    esSemiPerfecto 18 == True\r\n--    esSemiPerfecto 9  == False\r\n--    esSemiPerfecto 24 == True\r\n-- ---------------------------------------------------------------------\r\n\r\nesSemiPerfecto :: Int -> Bool\r\nesSemiPerfecto n =\r\n    or [sum ys == n | ys <- subconjuntos (divisores n)]\r\n\r\n-- (divisores n) es la lista de los divisores propios de n. Por ejemplo,\r\n--    divisores 18 == [1,2,3,6,9]\r\ndivisores :: Int -> [Int]\r\ndivisores n = [x | x <- [1..n-1], mod n x == 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6.2. Definir la constante primerSemiPerfecto tal que su\r\n-- valor es el primer n\u00famero semiperfecto. \r\n-- ---------------------------------------------------------------------\r\n\r\nprimerSemiPerfecto :: Int\r\nprimerSemiPerfecto = head [n | n <- [1..], esSemiPerfecto n]\r\n\r\n-- La evaluaci\u00f3n es\r\n--    *Main> primerSemiPerfecto\r\n--    6\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6.3. Definir la funci\u00f3n \r\n--    semiPerfecto :: Int -> Int\r\n-- tal que (semiPerfecto n) es el n-\u00e9simo n\u00famero semiperfecto. Por\r\n-- ejemplo, \r\n--    semiPerfecto 1   == 6\r\n--    semiPerfecto 4   == 20\r\n--    semiPerfecto 100 == 414\r\n-- ---------------------------------------------------------------------\r\n\r\nsemiPerfecto :: Int -> Int\r\nsemiPerfecto n = semiPerfectos !! n\r\n\r\n-- semiPerfectos es la lista de los n\u00fameros semiPerfectos. Por ejemplo, \r\n--    take 4 semiPerfectos  ==  [6,12,18,20]\r\nsemiPerfectos = [n | n <- [1..], esSemiPerfecto n]\r\n\r\n-- -------------------------------------------------------------------\r\n-- Ejercicio 7.1. Definir mediante plegado la funci\u00f3n \r\n--    producto :: Num a => [a] -> a\r\n-- tal que (producto xs) es el producto de los elementos de la lista\r\n-- xs. Por ejemplo, \r\n--    producto [2,1,-3,4,5,-6] == 720\r\n-- ---------------------------------------------------------------------\r\n\r\nproducto :: Num a => [a] -> a\r\nproducto = foldr (*) 1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.2. Definir mediante plegado la funci\u00f3n \r\n--    productoPred :: Num a => (a -> Bool) -> [a] -> a\r\n-- tal que (productoPred p xs) es el producto de los elementos de la\r\n-- lista xs que verifican el predicado p. Por ejemplo, \r\n--    productoPred even [2,1,-3,4,-5,6] == 48\r\n-- ---------------------------------------------------------------------\r\n\r\nproductoPred :: Num a => (a -> Bool) -> [a] -> a\r\nproductoPred p = foldr (\\x y -> if p x then x*y else y) 1\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7.3. Definir la funci\u00f3n \r\n--    productoPos :: (Num a, Ord a) => [a] -> a\r\n-- tal que (productoPos xs) esel producto de los elementos estr\u00edctamente\r\n-- positivos de la lista xs. Por ejemplo,\r\n--    productoPos [2,1,-3,4,-5,6] == 48\r\n-- ---------------------------------------------------------------------\r\n\r\nproductoPos :: (Num a, Ord a) => [a] -> a\r\nproductoPos = productoPred (>0)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Las relaciones finitas se pueden representar mediante\r\n-- listas de pares. Por ejemplo,\r\n--    r1, r2, r3 :: [(Int, Int)]\r\n--    r1 = [(1,3), (2,6), (8,9), (2,7)]\r\n--    r2 = [(1,3), (2,6), (8,9), (3,7)]\r\n--    r3 = [(1,3), (2,6), (8,9), (3,6)]\r\n-- Definir la funci\u00f3n \r\n--    esFuncion :: (Eq a, Eq b) => [(a,b)] -> Bool\r\n-- tal que (esFuncion r) se verifica si la relaci\u00f3n r es una funci\u00f3n (es\r\n-- decir, a cada elemento del dominio de la relaci\u00f3n r le corresponde un\r\n-- \u00fanico elemento). Por ejemplo, \r\n--    esFuncion r1 == False\r\n--    esFuncion r2 == True\r\n--    esFuncion r3 == True\r\n-- ---------------------------------------------------------------------\r\n\r\nr1, r2, r3 :: [(Int, Int)]\r\nr1 = [(1,3), (2,6), (8,9), (2,7)]\r\nr2 = [(1,3), (2,6), (8,9), (3,7)]\r\nr3 = [(1,3), (2,6), (8,9), (3,6)]\r\n\r\nesFuncion :: (Eq a, Eq b) => [(a,b)] -> Bool\r\nesFuncion [] = True\r\nesFuncion ((x,y):r) = \r\n    [y' | (x',y') <- r, x == x', y \/= y'] == [] && esFuncion r \r\n\r\n-- -------------------------------------------------------------------\r\n-- Ejercicio 9.1. Se denomina cola de una lista l a una sublista no\r\n-- vac\u00eda de l formada por un elemento y los siguientes hasta el\r\n-- final. Por ejemplo, [3,4,5] es una cola de la lista [1,2,3,4,5]. \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    colas :: [a] -> [[a]]\r\n-- tal que (colas xs) es la lista de las colas\r\n-- de la lista xs. Por ejemplo, \r\n--    colas []        == [[]]\r\n--    colas [1,2]     == [[1,2],[2],[]]\r\n--    colas [4,1,2,5] == [[4,1,2,5],[1,2,5],[2,5],[5],[]]\r\n-- ---------------------------------------------------------------------\r\n\r\ncolas :: [a] -> [[a]]\r\ncolas []     = [[]]\r\ncolas (x:xs) = (x:xs) : colas xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9.2. Comprobar con QuickCheck que las funciones colas y\r\n-- tails son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_colas :: [Int] -> Bool\r\nprop_colas xs = colas xs == tails xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_colas\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10.1. Se denomina cabeza de una lista l a una sublista no\r\n-- vac\u00eda de la formada por el primer elemento y los siguientes hasta uno\r\n-- dado. Por ejemplo, [1,2,3] es una cabeza de [1,2,3,4,5]. \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    cabezas :: [a] -> [[a]]\r\n-- tal que (cabezas xs) es la lista de las cabezas de la lista xs. Por\r\n-- ejemplo, \r\n--    cabezas []          == [[]] \r\n--    cabezas [1,4]       == [[],[1],[1,4]] \r\n--    cabezas [1,4,5,2,3] == [[],[1],[1,4],[1,4,5],[1,4,5,2],[1,4,5,2,3]] \r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1. Por recursi\u00f3n\r\ncabezas :: [a] -> [[a]]\r\ncabezas []     = [[]]\r\ncabezas (x:xs) = [] : [x:ys | ys <- cabezas xs]\r\n\r\n-- 2. Usando patrones de plegado.\r\ncabezasP :: [a] -> [[a]]\r\ncabezasP = foldr (\\x y -> [x]:[x:ys | ys <- y]) []\r\n\r\n-- 3. Usando colas y funciones de orden superior.\r\ncabezas3 :: [a] -> [[a]]\r\ncabezas3 xs = reverse (map reverse (colas (reverse xs)))\r\n\r\n-- La anterior definici\u00f3n puede escribirse sin argumentos como \r\ncabezas3' :: [a] -> [[a]]\r\ncabezas3' = reverse . map reverse . (colas . reverse)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10.2. Comprobar con QuickCheck que las funciones cabezas y\r\n-- inits son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_cabezas :: [Int] -> Bool\r\nprop_cabezas xs = cabezas xs == inits xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_cabezas\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado la resoluci\u00f3n de ejercicios de la 12\u00aa relaci\u00f3n y de ka 13\u00aa relaci\u00f3n. Los ejercicios de la relaci\u00f3n 12 y su soluci\u00f3n se muestran a continuaci\u00f3n<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[133],"tags":[287],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1155"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1155"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1155\/revisions"}],"predecessor-version":[{"id":2951,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1155\/revisions\/2951"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1155"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1155"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1155"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}