{"id":5861,"date":"2017-11-29T19:17:53","date_gmt":"2017-11-29T18:17:53","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5861"},"modified":"2017-12-02T09:20:51","modified_gmt":"2017-12-02T08:20:51","slug":"i1m2017-2o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-2o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2017: 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-17\">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 (29 de noviembre de 2017)\n-- ---------------------------------------------------------------------\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas                                                        --\n-- ---------------------------------------------------------------------\n\nimport Data.List\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Definir la funci\u00f3n \n--    biparticiones :: Integer -> [(Integer,Integer)]\n-- tal que (biparticiones n) es la lista de pares de n\u00fameros formados\n-- por las primeras cifras de n y las restantes. Por ejemplo, \n--    biparticiones  2025  ==  [(202,5),(20,25),(2,25)]\n--    biparticiones 10000  ==  [(1000,0),(100,0),(10,0),(1,0)]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones1 :: Integer -> [(Integer,Integer)]\nbiparticiones1 x = [(read y, read z) | (y,z) <- biparticionesL1 xs]\n  where xs = show x\n\n-- (biparticionesL1 xs) es la lista de los pares formados por los\n-- prefijos no vac\u00edo de xs y su resto. Por ejemplo,\n--    biparticionesL1 \"2025\" == [(\"2\",\"025\"),(\"20\",\"25\"),(\"202\",\"5\")]\nbiparticionesL1 :: [a] -> [([a],[a])]\nbiparticionesL1 xs = [splitAt k xs | k <- [1..length xs - 1]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones2 :: Integer -> [(Integer,Integer)]\nbiparticiones2 x = [(read y, read z) | (y,z) <- biparticionesL2 xs]\n  where xs = show x\n\n-- (biparticionesL2 xs) es la lista de los pares formados por los\n-- prefijos no vac\u00edo de xs y su resto. Por ejemplo,\n--    biparticionesL2 \"2025\" == [(\"2\",\"025\"),(\"20\",\"25\"),(\"202\",\"5\")]\nbiparticionesL2 :: [a] -> [([a],[a])]\nbiparticionesL2 xs =\n  takeWhile (not . null . snd) [splitAt n xs | n <- [1..]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones3 :: Integer -> [(Integer,Integer)]\nbiparticiones3 a =\n  takeWhile ((>0) . fst) [divMod a (10^n) | n <- [1..]] \n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones4 :: Integer -> [(Integer,Integer)]\nbiparticiones4 n =\n  [quotRem n (10^x) | x <- [1..length (show n) -1]]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones5 :: Integer -> [(Integer,Integer)]\nbiparticiones5 n =\n  takeWhile (\/= (0,n)) [divMod n (10^x) | x <- [1..]]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> numero n = (read (replicate n '2')) :: Integer\n--    (0.00 secs, 0 bytes)\n--    \u03bb> length (biparticiones1 (numero 10000))\n--    9999\n--    (0.03 secs, 10,753,192 bytes)\n--    \u03bb> length (biparticiones2 (numero 10000))\n--    9999\n--    (1.89 secs, 6,410,513,136 bytes)\n--    \u03bb> length (biparticiones3 (numero 10000))\n--    9999\n--    (0.54 secs, 152,777,680 bytes)\n--    \u03bb> length (biparticiones4 (numero 10000))\n--    9999\n--    (0.01 secs, 7,382,816 bytes)\n--    \u03bb> length (biparticiones5 (numero 10000))\n--    9999\n--    (2.11 secs, 152,131,136 bytes)\n--    \n--    \u03bb> length (biparticiones1 (numero (10^7)))\n--    9999999\n--    (14.23 secs, 10,401,100,848 bytes)\n--    \u03bb> length (biparticiones4 (numero (10^7)))\n--    9999999\n--    (11.43 secs, 7,361,097,856 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n\n--    producto :: [[a]] -> [[a]]\n-- tal que (producto xss) es el producto cartesiano de los conjuntos\n-- xss. Por ejemplo,\n--    ghci> producto [[1,3],[2,5]]\n--    [[1,2],[1,5],[3,2],[3,5]]\n--    ghci> producto [[1,3],[2,5],[6,4]]\n--    [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]\n--    ghci> producto [[1,3,5],[2,4]]\n--    [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]]\n--    ghci> producto []\n--    [[]]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\nproducto :: [[a]] -> [[a]]\nproducto []       = [[]]\nproducto (xs:xss) = [x:ys | x <- xs, ys <- producto xss]\n\n-- 2\u00aa soluci\u00f3n\nproducto2 :: [[a]] -> [[a]]\nproducto2 = foldr f [[]]\n  where f xs xss = [x:ys | x <- xs, ys <- xss]\n\n-- 3\u00aa soluci\u00f3n\nproducto3 :: [[a]] -> [[a]]\nproducto3 = foldr aux [[]] \n  where aux [] _      = []\n        aux (x:xs) ys = map (x:) ys ++ aux xs ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Los \u00e1rboles binarios con valores enteros se pueden\n-- representar con el tipo de dato algebraico \n--    data Arbol = H\n--               | N a Arbol Arbol\n-- Por ejemplo, los \u00e1rboles\n--        3                7     \n--       \/ \\              \/ \\    \n--      2   4            5   8   \n--     \/ \\   \\          \/ \\   \\  \n--    1   3   5        6   4   10\n--                        \/   \/\n--                       9   1\n-- se representan por\n--    ej1, ej2 :: Arbol \n--    ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))\n--    ej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))\n--\n-- Definir la funci\u00f3n\n--    suma :: Arbol -> Int\n-- tal que (suma a) es la suma de todos los nodos a una distancia par\n-- de la ra\u00edz del \u00e1rbol a menos la suma de todos los nodos a una\n-- distancia impar de la ra\u00edz. Por ejemplo,\n--    suma ej1  ==  6\n--    suma ej2  ==  4\n-- ya que\n--     (3 + 1+3+5) - (2+4)        = 6\n--     (7 + 6+4+10) - (5+8 + 9+1) = 4 \n-- ---------------------------------------------------------------------\n\ndata Arbol = H\n           | N Int Arbol Arbol\n\nej1, ej2 :: Arbol \nej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))\nej2 = N 7 (N 5 (N 6 H H) (N 4 (N 9 H H) H)) (N 8 H (N 10 (N 1 H H) H))\n\nsuma :: Arbol -> Int\nsuma H         = 0\nsuma (N x i d) = x - suma i - suma d\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    cercano :: (a -> Bool) -> Int -> [a] -> Maybe a\n-- tal que (cercano p n xs) es el elemento de xs m\u00e1s cercano a n que\n-- verifica la propiedad p. La b\u00fasqueda comienza en n y los elementos se\n-- analizan en el siguiente orden: n, n+1, n-1, n+2, n-2,... Por ejemplo, \n--    cercano (`elem` \"aeiou\") 6 \"Sevilla\"     ==  Just 'a'\n--    cercano (`elem` \"aeiou\") 1 \"Sevilla\"     ==  Just 'e'\n--    cercano (`elem` \"aeiou\") 2 \"Sevilla\"     ==  Just 'i'\n--    cercano (`elem` \"aeiou\") 5 \"Sevilla\"     ==  Just 'a'\n--    cercano (`elem` \"aeiou\") 9 \"Sevilla\"     ==  Just 'a'\n--    cercano (`elem` \"aeiou\") (-3) \"Sevilla\"  ==  Just 'e'\n--    cercano (`elem` \"obcd\")  1 \"Sevilla\"     ==  Nothing\n--    cercano (>100) 4 [200,1,150,2,4]         ==  Just 150\n--    cercano even 5 [1,3..99]                 ==  Nothing\n--    cercano even 2 [1,4,6,8,0]               ==  Just 6\n--    cercano even 2 [1,4,7,8,0]               ==  Just 8\n--    cercano even 2 [1,4,7,5,0]               ==  Just 4\n--    cercano even 2 [1,3,7,5,0]               ==  Just 0\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ncercano :: (a -> Bool) -> Int -> [a] -> Maybe a\ncercano p n xs | null ys   = Nothing\n               | otherwise = Just (head ys)\n    where ys = filter p (ordenaPorCercanos xs n)\n\n-- (ordenaPorCercanos xs n) es la lista de los elementos de xs que\n-- ocupan las posiciones n, n+1, n-1, n+2, n-2... Por ejemplo, \n--    ordenaPorCercanos [0..9] 4     ==  [4,5,3,6,2,7,1,8,0,9]\n--    ordenaPorCercanos [0..9] 7     ==  [7,8,6,9,5,4,3,2,1,0]\n--    ordenaPorCercanos [0..9] 2     ==  [2,3,1,4,0,5,6,7,8,9]\n--    ordenaPorCercanos [0..9] (-3)  ==  [0,1,2,3,4,5,6,7,8,9]\n--    ordenaPorCercanos [0..9] 20    ==  [9,8,7,6,5,4,3,2,1,0]\nordenaPorCercanos :: [a] -> Int -> [a]\nordenaPorCercanos xs n \n    | n < 0          = xs\n    | n >= length xs = reverse xs\n    | otherwise      = z : intercala zs (reverse ys)\n    where (ys,(z:zs)) = splitAt n xs\n\n-- (intercala xs ys) es la lista obtenida intercalando los elementos de\n-- las lista xs e ys. Por ejemplo,\n--    intercala [1..4] [5..10]   ==  [1,5,2,6,3,7,4,8,9,10]\n--    intercala [5..10] [1..4]   ==  [5,1,6,2,7,3,8,4,9,10]\nintercala :: [a] -> [a] -> [a]\nintercala [] ys         = ys\nintercala xs []         = xs\nintercala (x:xs) (y:ys) = x : y : intercala xs ys\n\n-- 2\u00aa soluci\u00f3n (usando find)\n-- =========================\n\ncercano2 :: (a -> Bool) -> Int -> [a] -> Maybe a\ncercano2 p n xs = find p (ordenaPorCercanos xs n)\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":[265],"tags":[270,316],"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\/5861"}],"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=5861"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5861\/revisions"}],"predecessor-version":[{"id":5863,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5861\/revisions\/5863"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5861"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5861"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5861"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}