{"id":6555,"date":"2019-03-13T09:23:21","date_gmt":"2019-03-13T08:23:21","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6555"},"modified":"2019-03-18T09:23:47","modified_gmt":"2019-03-18T08:23:47","slug":"i1m2018-4o-examen-de-programacion-funcional-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2018-4o-examen-de-programacion-funcional-con-haskell\/","title":{"rendered":"I1M2018: 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-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-- ---------------------------------------------------------------------\n-- \u00a7 Librer\u00edas auxiliares                                             --\n-- ---------------------------------------------------------------------\n\nimport Data.Array\nimport Test.QuickCheck\nimport Text.Printf\nimport Data.List\nimport System.Timeout\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1 [2.5 puntos] Los \u00e1rboles binarios se pueden representar\n-- con \n--    data Arbol a = H a\n--                 | Nodo a (Arbol a) (Arbol a)\n--      deriving (Show, Eq)\n--\n-- Definir la funci\u00f3n\n--    arboles  :: Integer -> a -> [Arbol a]\n-- tales que (arboles n x) es la lista de todos los \u00e1rboles binarios con\n-- n elementos iguales a x. Por ejemplo,\n--    \u03bb> arboles 0 7\n--    []\n--    \u03bb> arboles 1 7\n--    [H 7]\n--    \u03bb> arboles 2 7\n--    []\n--    \u03bb> arboles 3 7\n--    [Nodo 7 (H 7) (H 7)]\n--    \u03bb> arboles 4 7\n--    []\n--    \u03bb> arboles 5 7\n--    [Nodo 7 (H 7) (Nodo 7 (H 7) (H 7)),\n--     Nodo 7 (Nodo 7 (H 7) (H 7)) (H 7)]\n--    \u03bb> arboles 6 7\n--    []\n--    \u03bb> arboles 7 7\n--    [Nodo 7 (H 7) (Nodo 7 (H 7) (Nodo 7 (H 7) (H 7))),\n--     Nodo 7 (H 7) (Nodo 7 (Nodo 7 (H 7) (H 7)) (H 7)),\n--     Nodo 7 (Nodo 7 (H 7) (H 7)) (Nodo 7 (H 7) (H 7)),\n--     Nodo 7 (Nodo 7 (H 7) (Nodo 7 (H 7) (H 7))) (H 7),\n--     Nodo 7 (Nodo 7 (Nodo 7 (H 7) (H 7)) (H 7)) (H 7)]\n-- ---------------------------------------------------------------------\n\ndata Arbol a = H a\n             | Nodo a (Arbol a) (Arbol a)\n  deriving (Show, Eq)\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\narboles :: Integer -> a -> [Arbol a]\narboles 0 _ = []\narboles 1 x = [H x]\narboles n x = [Nodo x i d | k <- [0..n-1],\n                            i <- arboles k x,\n                            d <- arboles (n-1-k) x]\n\n-- 2\u00aa definici\u00f3n\n-- =============\n\narboles2 :: Integer -> a -> [Arbol a]\narboles2 0 _ = []\narboles2 1 x = [H x]\narboles2 n x = [Nodo x i d | k <- [1,3..n-1],\n                             i <- arboles2 k x,\n                             d <- arboles2 (n-1-k) x]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. [2.5 puntos]. Un camino es una sucesi\u00f3n de pasos en una\n-- de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una\n-- direcci\u00f3n y a continuaci\u00f3n en la opuesta es un esfuerzo que se puede\n-- reducir. Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir\n-- a [Este,Sur]. \n--\n-- Un camino se dice que es reducido si no tiene dos pasos consecutivos\n-- en direcciones opuesta. \n--\n-- En Haskell, las direcciones y los caminos se pueden definir por\n--    data Direccion = N | S | E | O deriving (Show, Eq)\n--    type Camino = [Direccion]\n--\n-- Definir la funci\u00f3n \n--    reducido :: Camino -> Camino\n-- tal que (reducido ds) es el camino reducido equivalente al camino\n-- ds. Por ejemplo,\n--    reducido []                              ==  []\n--    reducido [N]                             ==  [N]\n--    reducido [N,O]                           ==  [N,O]\n--    reducido [N,O,E]                         ==  [N]\n--    reducido [N,O,E,S]                       ==  [] \n--    reducido [N,O,S,E]                       ==  [N,O,S,E]\n--    reducido [S,S,S,N,N,N]                   ==  []\n--    reducido [N,S,S,E,O,N]                   ==  []\n--    reducido [N,S,S,E,O,N,O]                 ==  [O]\n--\n-- N\u00f3tese que en el \u00faltimo ejemplo las reducciones son\n--        [N,S,S,E,O,N,O]  \n--    --> [S,E,O,N,O]  \n--    --> [S,N,O]  \n--    --> [O]  \n-- ---------------------------------------------------------------------\n\ndata Direccion = N | S | E | O deriving (Show, Eq)\n\ntype Camino = [Direccion]\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nreducido :: Camino -> Camino\nreducido [] = []\nreducido (d:ds)\n  | null ds'                = [d]\n  | d == opuesta (head ds') = tail ds'\n  | otherwise               = d:ds'\n  where ds' = reducido ds\n\nopuesta :: Direccion -> Direccion\nopuesta N = S\nopuesta S = N\nopuesta E = O\nopuesta O = E\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nreducido2 :: Camino -> Camino\nreducido2 = foldr aux []\n    where aux N (S:xs) = xs\n          aux S (N:xs) = xs\n          aux E (O:xs) = xs\n          aux O (E:xs) = xs\n          aux x xs     = x:xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nreducido3 :: Camino -> Camino\nreducido3 []       = []\nreducido3 (N:S:ds) = reducido3 ds\nreducido3 (S:N:ds) = reducido3 ds\nreducido3 (E:O:ds) = reducido3 ds\nreducido3 (O:E:ds) = reducido3 ds\nreducido3 (d:ds)\n  | null ds'                = [d]\n  | d == opuesta (head ds') = tail ds'\n  | otherwise               = d:ds'\n  where ds' = reducido3 ds\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nreducido4 :: Camino -> Camino\nreducido4 ds = reverse (aux ([],ds)) where \n    aux (N:xs, S:ys) = aux (xs,ys)\n    aux (S:xs, N:ys) = aux (xs,ys)\n    aux (E:xs, O:ys) = aux (xs,ys)\n    aux (O:xs, E:ys) = aux (xs,ys)\n    aux (  xs, y:ys) = aux (y:xs,ys)\n    aux (  xs,   []) = xs\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    ghci> reducido (take (10^6) (cycle [N,E,O,S]))\n--    []\n--    (3.87 secs, 460160736 bytes)\n--    ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))\n--    []\n--    (1.16 secs, 216582880 bytes)\n--    ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))\n--    []\n--    (0.58 secs, 98561872 bytes)\n--    ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))\n--    []\n--    (0.64 secs, 176154640 bytes)\n--    \n--    ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))\n--    []\n--    (5.43 secs, 962694784 bytes)\n--    ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))\n--    []\n--    (9.29 secs, 1722601528 bytes)\n-- \n--    ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])\n--    400002\n--    (4.52 secs, 547004960 bytes)\n--    ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])\n--    400002\n--    \n--    ghci> let n=10^6 in reducido (replicate n N ++ replicate n S)\n--    []\n--    (7.35 secs, 537797096 bytes)\n--    ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)\n--    []\n--    (2.30 secs, 244553404 bytes)\n--    ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)\n--    []\n--    (8.08 secs, 545043608 bytes)\n--    ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)\n--    []\n--    (1.96 secs, 205552240 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. [1.5 puntos] Una serie infinita para el c\u00e1lculo de pi,\n-- publicada por Nilakantha en el siglo XV, es\n--               4       4       4       4   \n--    pi = 3 + ----- - ----- + ----- - ------ + \u00b7\u00b7\u00b7 \n--             2x3x4   4x5x6   6x7x8   8x9x10 \n--\n-- Definir la funci\u00f3n\n--    aproximacionPi :: Int -> Double\n-- tal que (aproximacionPi n) es la n-\u00e9sima aproximaci\u00f3n de pi obtenida\n-- sumando los n primeros t\u00e9rminos de la serie de Nilakantha. Por\n-- ejemplo, \n--    aproximacionPi 0        ==  3.0\n--    aproximacionPi 1        ==  3.1666666666666665\n--    aproximacionPi 2        ==  3.1333333333333333\n--    aproximacionPi 3        ==  3.145238095238095\n--    aproximacionPi 4        ==  3.1396825396825396\n--    aproximacionPi 5        ==  3.1427128427128426\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\naproximacionPi :: Int -> Double\naproximacionPi n = serieNilakantha !! n\n\nserieNilakantha :: [Double]\nserieNilakantha = scanl1 (+) terminosNilakantha\n\nterminosNilakantha :: [Double]\nterminosNilakantha = zipWith (\/) numeradores denominadores\n  where numeradores   = 3 : cycle [4,-4]\n        denominadores = 1 : [n*(n+1)*(n+2) | n <- [2,4..]]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\naproximacionPi2 :: Int -> Double\naproximacionPi2 = aux 3 2 1\n  where aux x _ _ 0 = x\n        aux x y z m =\n          aux (x+4\/product[y..y+2]*z) (y+2) (negate z) (m-1)\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\naproximacionPi3 :: Int -> Double\naproximacionPi3 x =\n  3 + sum [(((-1)**(n+1))*4)\/(2*n*(2*n+1)*(2*n+2))\n          | n <- [1..fromIntegral x]]\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> aproximacionPi (10^6)\n--    3.141592653589787\n--    (1.35 secs, 729,373,160 bytes)\n--    \u03bb> aproximacionPi2 (10^6)\n--    3.141592653589787\n--    (2.96 secs, 2,161,766,096 bytes)\n--    \u03bb> aproximacionPi3 (10^6)\n--    3.1415926535897913\n--    (2.02 secs, 1,121,372,536 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2 [1 punto]. Definir la funci\u00f3n\n--    tabla :: FilePath -> [Int] -> IO ()\n-- tal que (tabla f ns) escribe en el fichero f las n-\u00e9simas\n-- aproximaciones de pi, donde n toma los valores de la lista ns, junto\n-- con sus  errores. Por ejemplo, al evaluar la expresi\u00f3n\n--    tabla \"AproximacionesPi.txt\" [0,10..100]\n-- hace que el contenido del fichero \"AproximacionesPi.txt\" sea\n--      +------+----------------+----------------+\n--      | n    | Aproximaci\u00f3n   | Error          |\n--      +------+----------------+----------------+\n--      |    0 | 3.000000000000 | 0.141592653590 |\n--      |   10 | 3.141406718497 | 0.000185935093 |\n--      |   20 | 3.141565734659 | 0.000026918931 |\n--      |   30 | 3.141584272675 | 0.000008380915 |\n--      |   40 | 3.141589028941 | 0.000003624649 |\n--      |   50 | 3.141590769850 | 0.000001883740 |\n--      |   60 | 3.141591552546 | 0.000001101044 |\n--      |   70 | 3.141591955265 | 0.000000698325 |\n--      |   80 | 3.141592183260 | 0.000000470330 |\n--      |   90 | 3.141592321886 | 0.000000331704 |\n--      |  100 | 3.141592410972 | 0.000000242618 |\n--      +------+----------------+----------------+\n-- ---------------------------------------------------------------------\n\ntabla :: FilePath -> [Int] -> IO ()\ntabla f ns = writeFile f (tablaAux ns)\n\ntablaAux :: [Int] -> String\ntablaAux ns =\n     linea\n  ++ cabecera\n  ++ linea\n  ++ concat [printf \"| %4d | %.12f | %.12f |\\n\" n a e\n            | n <- ns\n            , let a = aproximacionPi n\n            , let e = abs (pi - a)]\n  ++ linea\n\nlinea :: String\nlinea = \"+------+----------------+----------------+\\n\"\n\ncabecera :: String\ncabecera = \"| n    | Aproximaci\u00f3n   | Error          |\\n\"\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1 [1 punto]. El n\u00famero 7 tiene 4 descomposiciones como\n-- suma de cuadrados de enteros positivos \n--    7 = 1^2 + 1^2 + 1^2 + 2^2\n--    7 = 1^2 + 1^2 + 2^2 + 1^2\n--    7 = 1^2 + 2^2 + 1^2 + 1^2\n--    7 = 2^2 + 1^2 + 1^2 + 1^2]]\n-- \n-- Definir la funci\u00f3n\n--    nDescomposiciones       :: Int -> Int\n-- tal que (nDescomposiciones x) es el n\u00famero de listas de los cuadrados\n-- de cuatro n\u00fameros enteros positivos cuya suma es x. Por ejemplo.  \n--      nDescomposiciones 7      ==  4\n--      nDescomposiciones 4      ==  1\n--      nDescomposiciones 5      ==  0\n--      nDescomposiciones 10     ==  6\n--      nDescomposiciones 15     ==  12\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nnDescomposiciones :: Int -> Int\nnDescomposiciones = length . descomposiciones\n\n-- (descomposiciones x) es la lista de las listas de los cuadrados de\n-- cuatro n\u00fameros enteros positivos cuya suma es x. Por  ejemplo. \n--    \u03bb> descomposiciones 4\n--    [[1,1,1,1]]\n--    \u03bb> descomposiciones 5\n--    []\n--    \u03bb> descomposiciones 7\n--    [[1,1,1,4],[1,1,4,1],[1,4,1,1],[4,1,1,1]]\n--    \u03bb> descomposiciones 10\n--    [[1,1,4,4],[1,4,1,4],[1,4,4,1],[4,1,1,4],[4,1,4,1],[4,4,1,1]]\n--    \u03bb> descomposiciones 15\n--    [[1,1,4,9],[1,1,9,4],[1,4,1,9],[1,4,9,1],[1,9,1,4],[1,9,4,1],\n--     [4,1,1,9],[4,1,9,1],[4,9,1,1],[9,1,1,4],[9,1,4,1],[9,4,1,1]]\ndescomposiciones :: Int -> [[Int]]\ndescomposiciones x = aux x 4\n  where \n    aux 0 1 = []\n    aux 1 1 = [[1]]\n    aux 2 1 = []\n    aux 3 1 = []\n    aux y 1 | esCuadrado y = [[y]]\n            | otherwise    = []\n    aux y n = [x^2 : zs | x <- [1..raizEntera y]\n                        , zs <- aux (y - x^2) (n-1)]\n\n-- (esCuadrado x) se verifica si x es un n\u00famero al cuadrado. Por\n-- ejemplo,\n--    esCuadrado 25  ==  True\n--    esCuadrado 26  ==  False\nesCuadrado :: Int -> Bool\nesCuadrado x = (raizEntera x)^2 == x\n\n-- (raizEntera n) es el mayor entero cuya ra\u00edz cuadrada es menor o igual\n-- que n. Por ejemplo,\n--    raizEntera 15  ==  3\n--    raizEntera 16  ==  4\n--    raizEntera 17  ==  4\nraizEntera :: Int -> Int\nraizEntera = floor . sqrt . fromIntegral \n\n-- 2\u00aa soluci\u00f3n\n-- =============\n\nnDescomposiciones2 :: Int -> Int\nnDescomposiciones2 = length . descomposiciones2\n\ndescomposiciones2 :: Int -> [[Int]]\ndescomposiciones2 x = a ! (x,4)\n  where\n    a = array ((0,1),(x,4)) [((i,j), f i j) | i <- [0..x], j <- [1..4]]\n    f 0 1 = []\n    f 1 1 = [[1]]\n    f 2 1 = []\n    f 3 1 = []\n    f i 1 | esCuadrado i = [[i]]\n          | otherwise    = []\n    f i j = [x^2 : zs | x <- [1..raizEntera i]\n                      , zs <- a ! (i - x^2,j-1)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nnDescomposiciones3 :: Int -> Int\nnDescomposiciones3 x = aux x 4\n  where\n    aux 0 1 = 0\n    aux 1 1 = 1\n    aux 2 1 = 0\n    aux 3 1 = 0\n    aux y 1 | esCuadrado y = 1\n            | otherwise    = 0\n    aux y n = sum [aux (y - x^2) (n-1) | x <- [1..raizEntera y]]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nnDescomposiciones4 :: Int -> Int\nnDescomposiciones4 x = a ! (x,4)\n  where\n    a = array ((0,1),(x,4)) [((i,j), f i j) | i <- [0..x], j <- [1..4]]\n    f 0 1 = 0\n    f 1 1 = 1\n    f 2 1 = 0\n    f 3 1 = 0\n    f i 1 | esCuadrado i = 1\n          | otherwise    = 0\n    f i j = sum [a ! (i- x^2,j-1) | x <- [1..raizEntera i]]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_nDescomposiciones :: Positive Int -> Bool\nprop_nDescomposiciones (Positive x) =\n  all (== nDescomposiciones x) [f x | f <- [ nDescomposiciones2\n                                           , nDescomposiciones3\n                                           , nDescomposiciones4]]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_nDescomposiciones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> nDescomposiciones 20000\n--    1068\n--    (3.69 secs, 3,307,250,128 bytes)\n--    \u03bb> nDescomposiciones2 20000\n--    1068\n--    (0.72 secs, 678,419,328 bytes)\n--    \u03bb> nDescomposiciones3 20000\n--    1068\n--    (3.94 secs, 3,485,725,552 bytes)\n--    \u03bb> nDescomposiciones4 20000\n--    1068\n--    (0.74 secs, 716,022,456 bytes)\n--    \n--    \u03bb> nDescomposiciones2 50000\n--    5682\n--    (2.64 secs, 2,444,206,000 bytes)\n--    \u03bb> nDescomposiciones4 50000\n--    5682\n--    (2.77 secs, 2,582,443,448 bytes)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2 [1.5 puntos]. Con la definici\u00f3n del apartado anterior,\n-- evaluar (en menos de 2 segundos),\n--    nDescomposiciones (2*10^4)\n-- ---------------------------------------------------------------------\n\n-- El c\u00e1lculo es\n--    \u03bb> timeout (2*10^6) (return $! (nDescomposiciones4 (2*10^4)))\n--    Just 1068\n--    (1.13 secs, 715,951,808 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":[320],"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\/6555"}],"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=6555"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6555\/revisions"}],"predecessor-version":[{"id":6556,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6555\/revisions\/6556"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6555"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6555"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6555"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}