{"id":5985,"date":"2018-03-14T15:51:14","date_gmt":"2018-03-14T14:51:14","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5985"},"modified":"2018-03-14T15:51:14","modified_gmt":"2018-03-14T14:51:14","slug":"i1m2017-4o-examen-de-programacion-funcional-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2017-4o-examen-de-programacion-funcional-con-haskell\/","title":{"rendered":"I1M2017: 4\u00ba examen de programaci\u00f3n funcional con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 4\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-- 4\u00ba examen de evaluaci\u00f3n continua (14 de marzo de 2018)\n-- ---------------------------------------------------------------------\n\n-- Nota: La puntuaci\u00f3n de cada ejercicio es 2.5 puntos.\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas                                                        --\n-- ---------------------------------------------------------------------\n\n1import Data.List\nimport Data.Matrix\nimport Test.QuickCheck\nimport Graphics.Gnuplot.Simple\nimport Data.Function\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir la funci\u00f3n\n--    menorPotencia :: Integer -> (Integer,Integer)\n-- tal que (menorPotencia n) es el par (k,m) donde m es la menor\n-- potencia de 2 que empieza por n y k es su exponentes (es decir,\n-- 2^k = m). Por ejemplo, \n--    menorPotencia 3             ==  (5,32)\n--    menorPotencia 7             ==  (46,70368744177664)\n--    fst (menorPotencia 982)     ==  3973\n--    fst (menorPotencia 32627)   ==  28557\n--    fst (menorPotencia 158426)  ==  40000\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nmenorPotencia :: Integer -> (Integer,Integer)\nmenorPotencia n =\n  head [(k,m) | (k,m) <- zip [0..] potenciasDe2\n              , cs `isPrefixOf` show m]\n  where cs = show n\n\n-- potenciasDe 2 es la lista de las potencias de dos. Por ejemplo,\n--    take 12 potenciasDe2  ==  [1,2,4,8,16,32,64,128,256,512,1024,2048]\npotenciasDe2 :: [Integer]\npotenciasDe2 = iterate (*2) 1\n\n-- 2\u00aa definici\u00f3n \n-- =============\n\nmenorPotencia2 :: Integer -> (Integer,Integer)\nmenorPotencia2 n = aux (0,1)\n  where aux (k,m) | cs `isPrefixOf` show m = (k,m)\n                  | otherwise              = aux (k+1,2*m)\n        cs = show n\n\n-- 3\u00aa definici\u00f3n \n-- =============\n\nmenorPotencia3 :: Integer -> (Integer,Integer)\nmenorPotencia3 n =\n  until (isPrefixOf n1 . show . snd) (\\(x,y) -> (x+1,2*y)) (0,1)\n  where n1 = show n\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> maximum [fst (menorPotencia n) | n <- [1..1000]]\n--    3973\n--    (3.69 secs, 1,094,923,696 bytes)\n--    \u03bb> maximum [fst (menorPotencia2 n) | n <- [1..1000]]\n--    3973\n--    (5.13 secs, 1,326,382,872 bytes)\n--    \u03bb> maximum [fst (menorPotencia3 n) | n <- [1..1000]]\n--    3973\n--    (4.71 secs, 1,240,498,128 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Definir la funci\u00f3n\n--    graficaMenoresExponentes :: Integer -> IO () \n-- tal que (graficaMenoresExponentes n) dibuja la gr\u00e1fica de los\n-- exponentes de 2 en las menores potencias de los n primeros n\u00fameros\n-- enteros positivos. \n-- ---------------------------------------------------------------------\n\ngraficaMenoresExponentes :: Integer -> IO ()\ngraficaMenoresExponentes n =\n  plotList [ Key Nothing\n           , PNG \"Menor_potencia_de_2_que_comienza_por_n.png\"\n           ]\n           (map (fst . menorPotencia) [1..n])\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Definir la funci\u00f3n \n--    raizEnt :: Integer -> Integer -> Integer\n-- tal que (raizEnt x n) es la ra\u00edz entera n-\u00e9sima de x; es decir, el\n-- mayor n\u00famero entero y tal que y^n <= x. Por ejemplo,\n--    raizEnt  8 3      ==  2\n--    raizEnt  9 3      ==  2\n--    raizEnt 26 3      ==  2\n--    raizEnt 27 3      ==  3\n--    raizEnt (10^50) 2 ==  10000000000000000000000000\n--\n-- Comprobar con QuickCheck que para todo n\u00famero natural n, \n--     raizEnt (10^(2*n)) 2 == 10^n\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n\nraizEnt1 :: Integer -> Integer -> Integer\nraizEnt1 x n =\n  last (takeWhile (\\y -> y^n <= x) [0..])\n\n-- 2\u00aa definici\u00f3n         \nraizEnt2 :: Integer -> Integer -> Integer\nraizEnt2 x n =\n  floor ((fromIntegral x)**(1 \/ fromIntegral n))\n\n-- Nota. La definici\u00f3n anterior falla para n\u00fameros grandes. Por ejemplo,\n--    \u03bb> raizEnt2 (10^50) 2 == 10^25\n--    False\n          \n-- 3\u00aa definici\u00f3n          \nraizEnt3 :: Integer -> Integer -> Integer\nraizEnt3 x n = aux (1,x)\n  where aux (a,b) | d == x    = c\n                  | c == a    = c\n                  | d < x     = aux (c,b)\n                  | otherwise = aux (a,c) \n          where c = (a+b) `div` 2\n                d = c^n\n\n-- Comparaci\u00f3n de eficiencia\n--    \u03bb> raizEnt1 (10^14) 2\n--    10000000\n--    (6.15 secs, 6,539,367,976 bytes)\n--    \u03bb> raizEnt2 (10^14) 2\n--    10000000\n--    (0.00 secs, 0 bytes)\n--    \u03bb> raizEnt3 (10^14) 2\n--    10000000\n--    (0.00 secs, 25,871,944 bytes)\n--    \n--    \u03bb> raizEnt2 (10^50) 2\n--    9999999999999998758486016\n--    (0.00 secs, 0 bytes)\n--    \u03bb> raizEnt3 (10^50) 2\n--    10000000000000000000000000\n--    (0.00 secs, 0 bytes)\n                        \n-- La propiedad es                        \nprop_raizEnt :: (Positive Integer) -> Bool\nprop_raizEnt (Positive n) =\n  raizEnt3 (10^(2*n)) 2 == 10^n\n\n-- La comprobaci\u00f3n es              \n--    \u03bb> quickCheck prop_raizEnt\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Los \u00e1rboles se pueden representar mediante el siguiente\n-- tipo de datos  \n--    data Arbol a = N a [Arbol a]\n--                   deriving Show\n-- Por ejemplo, los \u00e1rboles\n--      1               3      \n--     \/ \\             \/|\\     \n--    2   3           \/ | \\    \n--        |          5  4  7   \n--        4          |    \/|\\  \n--                   6   2 8 6 \n-- se representan por\n--    ejArbol1, ejArbol2 :: Arbol Int\n--    ejArbol1 = N 1 [N 2 [], N 3 [N 4 []]]\n--    ejArbol2 = N 3 [N 5 [N 6 []], \n--                    N 4 [], \n--                    N 7 [N 2 [], N 8 [], N 6 []]]\n--\n-- Definir la funci\u00f3n\n--    nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]\n-- tal que (nodosSumaMaxima a) es la lista de los nodos del\n-- \u00e1rbol a cuyos hijos tienen m\u00e1xima suma. Por ejemplo,\n--    nodosSumaMaxima ejArbol1  ==  [1]\n--    nodosSumaMaxima ejArbol2  ==  [7,3]\n-- ---------------------------------------------------------------------\n\ndata Arbol a = N a [Arbol a]\n  deriving Show\n\nejArbol1, ejArbol2 :: Arbol Int\nejArbol1 = N 1 [N 2 [], N 3 [N 4 []]]\nejArbol2 = N 3 [N 5 [N 6 []], \n                N 4 [], \n                N 7 [N 2 [], N 8 [], N 6 []]]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]\nnodosSumaMaxima a =\n  [x | (s,x) <- ns, s == m]\n  where ns = reverse (sort (nodosSumas a))\n        m  = fst (head ns)\n\n-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del\n-- \u00e1rbol x y s es la suma de sus hijos. Por ejemplo,  \n--    \u03bb> nodosSumas ejArbol1\n--    [(5,1),(0,2),(4,3),(0,4)]\n--    \u03bb> nodosSumas ejArbol2\n--    [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]\nnodosSumas :: Num t => Arbol t -> [(t,t)]\nnodosSumas (N x []) = [(0,x)]\nnodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as\n\n-- (raices b) es la lista de las ra\u00edces del bosque b. Por ejemplo,\n--    raices [ejArbol1,ejArbol2]  ==  [1,3]\nraices :: [Arbol t] -> [t]\nraices = map raiz\n\n-- (raiz a) es la ra\u00edz del \u00e1rbol a. Por ejemplo,\n--    raiz ejArbol1  ==  1\n--    raiz ejArbol2  ==  3\nraiz :: Arbol t -> t\nraiz (N x _) = x\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nnodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]\nnodosSumaMaxima2 a =\n  [x | (s,x) <- ns, s == m]\n  where ns = sort (nodosOpSumas a)\n        m  = fst (head ns)\n\n-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del\n-- \u00e1rbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,  \n--    \u03bb> nodosOpSumas ejArbol1\n--    [(-5,1),(0,2),(-4,3),(0,4)]\n--    \u03bb> nodosOpSumas ejArbol2\n--    [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]\nnodosOpSumas :: Num t => Arbol t -> [(t,t)]\nnodosOpSumas (N x []) = [(0,x)]\nnodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as\n\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]\nnodosSumaMaxima3 a =\n  [x | (s,x) <- ns, s == m]\n  where ns = sort (nodosOpSumas a)\n        m  = fst (head ns)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nnodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]\nnodosSumaMaxima4 a =\n  map snd (head (groupBy (\\p q -> fst p == fst q)\n                         (sort (nodosOpSumas a))))\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nnodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]\nnodosSumaMaxima5 a =\n  map snd (head (groupBy ((==) `on` fst)\n                         (sort (nodosOpSumas a))))\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nnodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]\nnodosSumaMaxima6 =\n  map snd\n  . head\n  . groupBy ((==) `on` fst)\n  . sort\n  . nodosOpSumas\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Definir la funci\u00f3n\n--    ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a\n-- tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p\n-- repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si\n-- ejMatriz es la matriz definida por\n--    ejMatriz :: Matrix Char\n--    ejMatriz = fromLists [\" x \",\n--                          \"x x\",\n--                          \" x \"]\n-- entonces \n--    \u03bb> ampliaMatriz ejMatriz 1 2\n--    ( ' ' ' ' 'x' 'x' ' ' ' ' )\n--    ( 'x' 'x' ' ' ' ' 'x' 'x' )\n--    ( ' ' ' ' 'x' 'x' ' ' ' ' )\n--    \n--    \u03bb> (putStr . unlines . toLists) (ampliaMatriz ejMatriz 1 2)\n--      xx  \n--    xx  xx\n--      xx  \n--    \u03bb> (putStr . unlines . toLists) (ampliaMatriz ejMatriz 2 1)\n--     x \n--     x \n--    x x\n--    x x\n--     x \n--     x \n--    \u03bb> (putStr . unlines . toLists) (ampliaMatriz ejMatriz 2 2)\n--      xx  \n--      xx  \n--    xx  xx\n--    xx  xx\n--      xx  \n--      xx  \n--    \u03bb> (putStr . unlines . toLists) (ampliaMatriz ejMatriz 2 3)\n--       xxx   \n--       xxx   \n--    xxx   xxx\n--    xxx   xxx\n--       xxx   \n--       xxx   \n-- ---------------------------------------------------------------------\n\nejMatriz :: Matrix Char\nejMatriz = fromLists [\" x \",\n                      \"x x\",\n                      \" x \"]\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\nampliaMatriz :: Matrix a -> Int -> Int -> Matrix a\nampliaMatriz p f c =\n  ampliaColumnas (ampliaFilas p f) c\n\nampliaFilas :: Matrix a -> Int -> Matrix a\nampliaFilas p f =\n  matrix (f*m) n (\\(i,j) -> p!(1 + (i-1) `div` f, j))\n  where m = nrows p\n        n = ncols p\n\nampliaColumnas :: Matrix a -> Int -> Matrix a\nampliaColumnas p c =\n  matrix m (c*n) (\\(i,j) -> p!(i,1 + (j-1) `div` c))\n  where m = nrows p\n        n = ncols p\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\nampliaMatriz2 :: Matrix a -> Int -> Int -> Matrix a\nampliaMatriz2 p f c =\n  ( fromLists\n  . concatMap (map (concatMap (replicate c)) . replicate f)\n  . toLists) p\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\nejemplo :: Int -> Matrix Int\nejemplo n = fromList n n [1..]\n\n--    \u03bb> maximum (ampliaMatriz (ejemplo 10) 100 200)\n--    100\n--    (6.44 secs, 1,012,985,584 bytes)\n--    \u03bb> maximum (ampliaMatriz2 (ejemplo 10) 100 200)\n--    100\n--    (2.38 secs, 618,096,904 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 4\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\/5985"}],"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=5985"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5985\/revisions"}],"predecessor-version":[{"id":5986,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5985\/revisions\/5986"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5985"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5985"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5985"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}