{"id":6460,"date":"2019-01-22T18:05:56","date_gmt":"2019-01-22T17:05:56","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6460"},"modified":"2019-01-26T08:07:02","modified_gmt":"2019-01-26T07:07:02","slug":"i1m2018-3o-examen-de-programacion-funcional-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-3o-examen-de-programacion-funcional-con-haskell\/","title":{"rendered":"I1M2018: 3\u00ba examen de programaci\u00f3n funcional con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 3\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-18\">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, Grupos 4 y 5)\n-- 3\u00ba examen de evaluaci\u00f3n continua (22 de enero de 2019)\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.List\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n\n--    nParejas :: Ord a => [a] -> Int\n-- tal que (nParejas xs) es el n\u00famero de parejas de elementos iguales en\n-- xs. Por rjemplo,\n--    nParejas [1,2,2,1,1,3,5,1,2]        ==  3\n--    nParejas [1,2,1,2,1,3,2]            ==  2\n--    nParejas [1..2*10^6]                ==  0\n--    nParejas2 ([1..10^6] ++ [1..10^6])  ==  1000000\n-- En el primer ejemplos las parejas son (1,1), (1,1) y (2,2). En el\n-- segundo ejemplo, las parejas son (1,1) y (2,2).\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nnParejas :: Ord a => [a] -> Int\nnParejas []     = 0\nnParejas (x:xs) | x `elem` xs = 1 + nParejas (xs \\\\ [x])\n                | otherwise   = nParejas xs\n\n-- 2\u00aa soluci\u00f3n\nnParejas2 :: Ord a => [a] -> Int\nnParejas2 xs =\n  sum [length ys `div` 2 | ys <- group (sort xs)]\n\n-- 3\u00aa soluci\u00f3n\nnParejas3 :: Ord a => [a] -> Int\nnParejas3 = sum . map (`div` 2) . map length . group . sort\n\n-- 4\u00aa soluci\u00f3n\nnParejas4 :: Ord a => [a] -> Int\nnParejas4 = sum . map ((`div` 2) . length) . group . sort\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    maximos :: Ord a => [a] -> [a]\n-- tal que (maximos xs) es la lista de los elementos de xs que son\n-- mayores que todos sus anteriores. Por ejemplo, \n--    maximos [1,-3,5,2,3,4,7,6,7]                         ==  [1,5,7]\n--    maximos \"bafcdegag\"                                  ==  \"bfg\"\n--    maximos (concat (replicate (10^6) \"adxbcde\")++\"yz\")  ==  \"adxyz\"\n--    length (maximos [1..10^6])                           ==  1000000\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nmaximos :: Ord a => [a] -> [a]\nmaximos xs =\n  [x | (ys,x) <- zip (inits xs) xs, all (<x) ys]\n\n-- 2\u00aa soluci\u00f3n\nmaximos2 :: Ord a => [a] -> [a]\nmaximos2 [] = []\nmaximos2 (x:xs) = x : maximos2 (filter (>x) xs)\n\n-- 3\u00aa soluci\u00f3n\nmaximos3 :: Ord a => [a] -> [a]\nmaximos3 [] = []\nmaximos3 (x:xs) = aux xs [x] x\n    where aux [] zs _ = reverse zs\n          aux (y:ys) zs m | y > m     = aux ys (y:zs) y\n                          | otherwise = aux ys zs m \n\n-- 4\u00aa soluci\u00f3n\nmaximos4 :: Ord a => [a] -> [a]\nmaximos4 = nub . scanl1 max \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. La sucesi\u00f3n de los primeros factoriales es\n--    1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, ...\n-- El factorial m\u00e1s cercano a un n\u00famero x es el menor elemento y de la\n-- sucesi\u00f3n de los factoriales tal que el valor absoluto de la\n-- diferencia entre x e y es la menor posible. Por ejemplo,\n-- + el factorial m\u00e1s cercano a 3 es 2 porque |3-2| < |3-6|\n-- + el factorial m\u00e1s cercano a 4 es 2 porque |4-2| = |4-6| y 2 < \n-- + el factorial m\u00e1s cercano a 5 es 6 porque |5-2| > |5-6|\n-- + el factorial m\u00e1s cercano a 5 es 6 porque 6 es un factorial.\n--\n-- Definir la funci\u00f3n\n--    factorialMasCercano :: Integer -> Integer\n-- tal que (factorialMasCercano n) es el factorial m\u00e1s cercano a n. Por\n-- ejemplo, \n--    factorialMasCercano 3  ==  2\n--    factorialMasCercano 4  ==  2\n--    factorialMasCercano 5  ==  6\n--    factorialMasCercano 6  ==  6\n--    factorialMasCercano 2019  ==  720\n-- ---------------------------------------------------------------------\n\nfactorialMasCercano :: Integer -> Integer\nfactorialMasCercano n\n  | b == n                 = n\n  | abs (n-a) <= abs (n-b) = a\n  | otherwise              = b\n  where (xs,b:ys) = span (<n) factoriales\n        a = last xs\n\nfactoriales :: [Integer]\nfactoriales = scanl1 (*) [1..]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Las expresiones aritm\u00e9ticas. generales se contruyen con\n-- las sumas generales (sumatorios) y productos generales (productorios).\n-- Su tipo es \n--    data Expresion = N Int\n--                   | S [Expresion]\n--                   | P [Expresion]\n--      deriving Show\n-- Por ejemplo, la expresi\u00f3n (2 * (1 + 2 + 1) * (2 + 3)) + 1 se\n-- representa por S [P [N 2, S [N 1, N 2, N 1], S [N 2, N 3]], N 1]\n--\n-- Definir la funci\u00f3n\n--    valor :: Expresion -> Int\n-- tal que (valor e) es el valor de la expresi\u00f3n e. Por ejemplo,\n--    \u03bb> valor (S [P [N 2, S [N 1, N 2, N 1], S [N 2, N 3]], N 1])\n--    41\n-- ---------------------------------------------------------------------\n\ndata Expresion = N Int\n               | S [Expresion]\n               | P [Expresion]\n  deriving Show\n\n-- 1\u00aa soluci\u00f3n\nvalor :: Expresion -> Int\nvalor (N x)  = x\nvalor (S es) = sum (map valor es)\nvalor (P es) = product (map valor es)\n\n-- 2\u00aa soluci\u00f3n\nvalor2 :: Expresion -> Int\nvalor2 (N x)  = x\nvalor2 (S es) = sum [valor2 e | e <- es]\nvalor2 (P es) = product [valor2 e | e <- es]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 3\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":[320],"tags":[270,321],"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\/6460"}],"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=6460"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6460\/revisions"}],"predecessor-version":[{"id":6461,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6460\/revisions\/6461"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6460"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6460"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6460"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}