{"id":6905,"date":"2019-12-18T12:16:32","date_gmt":"2019-12-18T11:16:32","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6905"},"modified":"2019-12-20T12:17:02","modified_gmt":"2019-12-20T11:17:02","slug":"i1m2019-2o-examen-de-programacion-funcional-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2019-2o-examen-de-programacion-funcional-con-haskell\/","title":{"rendered":"I1M2019: 2\u00ba examen de programaci\u00f3n funcional con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 2\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-19\">Inform\u00e1tica<\/a> (de 1\u00ba de Grado en Matem\u00e1ticas). Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<\/p>\n<p><!--more--><\/p>\n<pre lang=\"haskell\">\n-- Inform\u00e1tica (1\u00ba del Grado en Matem\u00e1ticas, Grupo 4)\n-- 2\u00ba examen de evaluaci\u00f3n continua (18 de diciembre de 2019)\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- Librer\u00edas auxiliares\n-- ---------------------------------------------------------------------\n\nimport Data.Char\nimport Data.List\nimport Data.Numbers.Primes\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir la funci\u00f3n\n--    ultimoNoNuloFactorial :: Integer -> Integer\n-- tal que (ultimoNoNuloFactorial n) es el \u00faltimo d\u00edgito no nulo del\n-- factorial de n. Por ejemplo,\n--    ultimoNoNuloFactorial  7  == 4\n--    ultimoNoNuloFactorial 10  == 8\n--    ultimoNoNuloFactorial 12  == 6\n--    ultimoNoNuloFactorial 97  == 2\n--    ultimoNoNuloFactorial  0  == 1\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nultimoNoNuloFactorial :: Integer -> Integer\nultimoNoNuloFactorial = ultimoNoNulo . factorial\n\n-- (factorial n) es el factorial de n. Por ejemplo,\n--    factorial 7  ==  5040\nfactorial :: Integer -> Integer\nfactorial n = product [1..n]\n\n-- (ultimoNoNulo n) es el \u00faltimo d\u00edgito no nulo de n. Por ejemplo,\n--    ultimoNoNulo 5040  ==  4\nultimoNoNulo :: Integer -> Integer\nultimoNoNulo n | r \/= 0    = r\n               | otherwise = ultimoNoNulo q\n  where (q,r) = n `quotRem` 10\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nultimoNoNuloFactorial2 :: Integer -> Integer\nultimoNoNuloFactorial2 = last . filter (\/= 0) . digitos . factorial\n\ndigitos :: Integer -> [Integer]\ndigitos n = [read [x] | x <- show n]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nultimoNoNuloFactorial3 :: Integer -> Integer\nultimoNoNuloFactorial3 = last . filter (\/= 0) . digitos3 . factorial3\n\ndigitos3 :: Integer -> [Integer]\ndigitos3 = map (fromIntegral . digitToInt) . show\n\nfactorial3 :: Integer -> Integer\nfactorial3 = product . enumFromTo 1\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nultimoNoNulo4 :: Integer -> Integer\nultimoNoNulo4 n = read [head (dropWhile (=='0') (reverse (show n)))]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nultimoNoNulo5 :: Integer -> Integer\nultimoNoNulo5 =\n  read . return . head . dropWhile ('0' ==) . reverse . show\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Comprobar con QuickCheck que si n es mayor que 4,\n-- entonces el \u00faltimo d\u00edgito no nulo del factorial de n es par.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_ultimoNoNuloFactorial :: Integer -> Property\nprop_ultimoNoNuloFactorial n = \n  n > 4 ==> even (ultimoNoNuloFactorial n)\n                  \n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_ultimoNoNuloFactorial\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Una forma de aproximar el n\u00famero \u03c0 es usando la\n-- siguiente igualdad:  \n--     \u03c0         1     1*2     1*2*3     1*2*3*4     \n--    --- = 1 + --- + ----- + ------- + --------- + ....\n--     2         3     3*5     3*5*7     3*5*7*9\n-- Es decir, la serie cuyo t\u00e9rmino general n-\u00e9simo es el cociente entre el\n-- producto de los primeros n n\u00fameros y los primeros n n\u00fameros impares:\n--                \u03a0 i   \n--    s(n) =  -----------\n--             \u03a0 (2*i+1)\n--\n-- Definir la funci\u00f3n\n--    aproximaPi :: Double -> Double\n-- tal que (aproximaPi n) es la aproximaci\u00f3n del n\u00famero \u03c0 calculada con la\n-- serie anterior hasta el t\u00e9rmino n-\u00e9simo. Por ejemplo,\n--    aproximaPi 10   ==  3.141106021601377\n--    aproximaPi\n30   ==  3.1415926533011587\n--    aproximaPi 50   ==  3.1415926535897922\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n (por comprensi\u00f3n):\naproximaPi :: Double -> Double\naproximaPi n = \n  2 * sum [product [1..i] \/ product [1,3..2*i+1] | i <- [0..n]]\n\n-- 2\u00aa soluci\u00f3n (por recursi\u00f3n):\naproximaPi2 :: Double -> Double\naproximaPi2 0 = 2\naproximaPi2 n = \n  aproximaPi2 (n-1) + 2 * product [1..n] \/ product [3,5..2*n+1]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. La descomposici\u00f3n prima de 600 es\n--    600 = 2\u00b3 * 3 * 5\u00b2\n-- \n-- Definir la funci\u00f3n\n--    factorizacion :: Integer -> [(Integer,Integer)]\n-- tal que (factorizacion x) ses la lista de las bases y exponentes de\n-- la descomposici\u00f3n prima de x. Por ejemplo,\n--    factorizacion 600  == [(2,3),(3,1),(5,2)]\n--    factorizacion 5500 == [(2,2),(5,3),(11,1)]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nfactorizacion :: Integer -> [(Integer,Integer)]\nfactorizacion n =\n  [(x,nOcurrencias x xs) | x <- elementos xs]\n  where xs = factoresPrimos n\n\n-- (factores primos n) es la lista de los factores primos de n. Por\n-- ejemplo, \n--   factoresPrimos 600  ==  [2,2,2,3,5,5]\nfactoresPrimos :: Integer -> [Integer]\nfactoresPrimos 1 = []\nfactoresPrimos n = x : factoresPrimos (n `div` x)\n  where x = menorFactor n\n\n-- (menorFactor n) es el menor factor primo de n. Por ejemplo,\n--   menorFactor 10  ==  2\n--   menorFactor 11  ==  11\nmenorFactor :: Integer -> Integer\nmenorFactor n = head [x | x <- [2..n], n `mod` x == 0]\n\n-- (elementos xs) es la lista de los elementos, sin repeticiones, de\n-- xs. Por ejemplo,\n--   elementos [3,2,3,5,2]  ==  [3,2,5]\nelementos :: Eq a => [a] -> [a]\nelementos [] = []\nelementos (x:xs) = x : elementos (filter (\/=x) xs)\n\n-- (nOcurrencias x ys) es el n\u00famero de ocurrencias de x en ys. Por\n-- ejemplo, \n--   nOcurrencias 'a' \"Salamanca\"  ==  4\nnOcurrencias :: Eq a => a -> [a] -> Integer\nnOcurrencias _ [] = 0\nnOcurrencias x (y:ys) | x == y    = 1 + nOcurrencias x ys\n                      | otherwise = nOcurrencias x ys\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nfactorizacion2 :: Integer -> [(Integer,Integer)]\nfactorizacion2 n =\n  [(head xs,genericLength xs) | xs <- group (primeFactors n)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nfactorizacion3 :: Integer -> [(Integer,Integer)]\nfactorizacion3 = map primeroYlongitud\n               . group\n               . primeFactors\n\n-- (primeroYlongitud xs) es el par formado por el primer elemento de xs\n-- y la longitud de xs. Por ejemplo,\n--    primeroYlongitud [3,2,5,7] == (3,4)\nprimeroYlongitud :: [a] -> (a,Integer)\nprimeroYlongitud (x:xs) =\n  (x, 1 + genericLength xs)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--   \u03bb> length (factorizacion (product [1..10^4]))\n--   1229\n--   (4.84 secs, 2,583,331,768 bytes)\n--   \u03bb> length (factorizacion2 (product [1..10^4]))\n--   1229\n--   (0.24 secs, 452,543,360 bytes)\n--   \u03bb> length (factorizacion3 (product [1..10^4]))\n--   1229\n--   (0.23 secs, 452,433,504 bytes)\n--   \n--   \u03bb> length (factorizacion (product (take (2*10^3) primes)))\n--   2000\n--   (6.58 secs, 3,415,098,552 bytes)\n--   \u03bb> length (factorizacion2 (product (take (2*10^3) primes)))\n--   2000\n--   (0.02 secs, 23,060,512 bytes)\n--   \u03bb> length (factorizacion3 (product (take (2*10^3) primes)))\n--   2000\n--   (0.02 secs, 22,882,080 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Las expresiones aritm\u00e9ticas se pueden representar como\n-- \u00e1rboles con n\u00fameros en las hojas y operaciones en los nodos. Por\n-- ejemplo, la expresi\u00f3n \"9-2*4\" se puede representar por el \u00e1rbol\n--      - \n--     \/ \\\n--    9   *\n--       \/ \\\n--      2   4\n-- \n-- Definiendo el tipo de dato Arbol por \n--    data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol\n-- la representaci\u00f3n del \u00e1rbol anterior es\n--    N (-) (H 9) (N (*) (H 2) (H 4))\n--\n-- Definir la funci\u00f3n\n--    valor :: Arbol -> Int\n-- tal que (valor a) es el valor de la expresi\u00f3n aritm\u00e9tica\n-- correspondiente al \u00e1rbol a. Por ejemplo,\n--    valor (N (-) (H 9) (N (*) (H 2) (H 4)))    ==  1\n--    valor (N (+) (H 9) (N (*) (H 2) (H 4)))    ==  17\n--    valor (N (+) (H 9) (N (div) (H 4) (H 2)))  ==  11\n--    valor (N (+) (H 9) (N (max) (H 4) (H 2)))  ==  13\n-- ---------------------------------------------------------------------\n\ndata Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol\n\nvalor :: Arbol -> Int\nvalor (H x)     = x\nvalor (N f i d) = f (valor i) (valor d)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 2\u00ba examen del curso de Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas). Los ejercicios, y sus soluciones, 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":[331],"tags":[],"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\/6905"}],"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=6905"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6905\/revisions"}],"predecessor-version":[{"id":6906,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6905\/revisions\/6906"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6905"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6905"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6905"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}