{"id":5160,"date":"2015-11-06T18:11:24","date_gmt":"2015-11-06T17:11:24","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5160"},"modified":"2015-11-12T18:12:22","modified_gmt":"2015-11-12T17:12:22","slug":"i1m2015-1o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2015-1o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2015: 1\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 1\u00ba examen del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-15\">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 Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir la funci\u00f3n\n--    repiteElementos :: Int -> [a] -> [a]\n-- tal que (repiteElementos k xs) es la lista obtenida repitiendo cada\n-- elemento de xs k veces. Por ejemplo,\n--    repiteElementos 3 [5,2,7,4]  ==  [5,5,5,2,2,2,7,7,7,4,4,4]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n):\nrepiteElementos1 :: Int -> [a] -> [a]\nrepiteElementos1 k xs = concat [replicate k x | x <- xs]\n\n-- 2\u00aa definici\u00f3n (con map)\nrepiteElementos2 :: Int -> [a] -> [a]\nrepiteElementos2 k xs = concat (map (replicate k) xs)\n\n-- 3\u00aa definici\u00f3n (con concatMap):\nrepiteElementos3 :: Int -> [a] -> [a]\nrepiteElementos3 k = concatMap (replicate k)\n\n-- 4\u00aa definici\u00f3n (por recursi\u00f3n):\nrepiteElementos4 :: Int -> [a] -> [a]\nrepiteElementos4 k []     = []\nrepiteElementos4 k (x:xs) = replicate k x ++ repiteElementos4 k xs\n\n-- 5\u00aa definici\u00f3n (por plegado):\nrepiteElementos5 :: Int -> [a] -> [a]\nrepiteElementos5 k = foldr ((++) . replicate k) []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Comprobar con QuickCheck que, para todo n\u00famero natural\n-- k y toda lista xs, el n\u00famero de elementos de (repiteElementos k xs)\n-- es k veces el n\u00famero de elementos de xs.\n--\n-- Nota. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como\n-- se indica a continuaci\u00f3n\n--    quickCheckWith (stdArgs {maxSize=7}) prop_repiteElementos\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_repiteElementos :: Int -> [Int] -> Property\nprop_repiteElementos k xs =\n    k >= 0 ==> length (repiteElementos1 k xs) == k * length xs \n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_repiteElementos\n--    +++ OK, passed 100 tests.\n\n-- ----------------------------------------------------------------------\n-- Ejercicio 2. Todo n\u00famero entero positivo n se puede escribir como\n-- 2^k*m, con m impar. Se dice que m es la parte impar de n. Por\n-- ejemplo, la parte impar de 40 es 5 porque 40 = 5*2^3.\n-- \n-- Definir la funci\u00f3n \n--    parteImpar :: Integer -> Integer\n-- tal que (parteImpar n) es la parte impar de n. Por ejemplo,\n--    parteImpar 40  ==  5\n-- ----------------------------------------------------------------------\n\nparteImpar :: Integer -> Integer\nparteImpar n | even n    = parteImpar (n `div` 2)\n             | otherwise = n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    refinada :: [Float] -> [Float]\n-- tal que (refinada xs) es la lista obtenida intercalando entre cada\n-- dos elementos consecutivos de xs su media aritm\u00e9tica. Por ejemplo,\n--    refinada [2,7,1,8]  ==  [2.0,4.5,7.0,4.0,1.0,4.5,8.0]\n--    refinada [2]        ==  [2.0]\n--    refinada []         ==  []\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n):\nrefinada :: [Float] -> [Float]\nrefinada (x:y:zs) = x : (x+y)\/2 : refinada (y:zs)\nrefinada xs       = xs\n\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n);\nrefinada2 :: [Float] -> [Float]\nrefinada2 []     = []\nrefinada2 (x:xs) = x : concat [[(a+b)\/2,b] | (a,b) <- zip (x:xs) xs]  \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Se dice que en una sucesi\u00f3n de n\u00fameros x(1),x(2),...,x(n) \n-- hay una inversi\u00f3n cuando existe un par de n\u00fameros x(i) > x(j), siendo\n-- i < j. Por ejemplo, en la sucesi\u00f3n 2, 1, 4, 3 hay dos inversiones (2\n-- antes que 1 y 4 antes que 3) y en la sucesi\u00f3n 4, 3, 1, 2 hay cinco\n-- inversiones (4 antes 3, 4 antes 1, 4 antes 2, 3 antes 1, 3 antes 2).\n-- \n-- Definir la funci\u00f3n \n--    numeroInversiones :: Ord a => [a] -> Int  \n-- tal que (numeroInversiones xs) es el n\u00famero de inversiones de xs. Por\n-- ejemplo, \n--    numeroInversiones [2,1,4,3]  ==  2\n--    numeroInversiones [4,3,1,2]  ==  5\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa soluci\u00f3n (por recursi\u00f3n)\nnumeroInversiones1 :: Ord a => [a] -> Int  \nnumeroInversiones1 [] = 0\nnumeroInversiones1 (x:xs) =\n    length [y | y <- xs, y < x] + numeroInversiones1 xs\n\n-- 2\u00aa soluci\u00f3n (por comprensi\u00f3n)\nnumeroInversiones2 :: Ord a => [a] -> Int  \nnumeroInversiones2 xs =\n    length [(i,j) | i <- [0..n-2], j <- [i+1..n-1], xs!!i > xs!!j]\n    where n = length xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. Definir la funci\u00f3n\n--    producto :: [[a]] -> [[a]]\n-- tal que (producto xss) es el producto cartesiano de los conjuntos xss. \n-- 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--    ghci> producto [[x] | x <- [1..10]]\n--    [[1,2,3,4,5,6,7,8,9,10]]\n-- ---------------------------------------------------------------------\n\nproducto :: [[a]] -> [[a]]\nproducto []       = [[]]\nproducto (xs:xss) = [x:ys | x <- xs, ys <- producto xss]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Comprobar con QuickCheck que el n\u00famero de elementos de\n-- (producto xss) es el producto de los n\u00fameros de elementos de los\n-- elementos de xss.\n--\n-- Nota. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como\n-- se indica a continuaci\u00f3n\n--    quickCheckWith (stdArgs {maxSize=7}) prop_producto\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_producto :: [[Int]] -> Bool\nprop_producto xss = \n    length (producto xss) == product [length xs | xs <- xss]\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_producto\n--    +++ OK, passed 100 tests.\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 1\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":[250],"tags":[270,310],"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\/5160"}],"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=5160"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5160\/revisions"}],"predecessor-version":[{"id":5161,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5160\/revisions\/5161"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}