{"id":4645,"date":"2014-12-03T13:02:30","date_gmt":"2014-12-03T12:02:30","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4645"},"modified":"2014-12-09T13:03:29","modified_gmt":"2014-12-09T12:03:29","slug":"i1m2014-2o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-2o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2014: 2\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-14\">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)\n-- 2\u00ba examen de evaluaci\u00f3n continua (3 de diciembre de 2014)\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir la funci\u00f3n \n--    trenza :: [a] -> [a] -> [a]\n-- tal que (trenza xs ys) es la lista obtenida intercalando los\n-- elementos de xs e ys. Por ejemplo,\n--    trenza [5,1] [2,7,4]             ==  [5,2,1,7]\n--    trenza [5,1,7] [2..]             ==  [5,2,1,3,7,4]\n--    trenza [2..] [5,1,7]             ==  [2,5,3,1,4,7]\n--    take 8 (trenza [2,4..] [1,5..])  ==  [2,1,4,5,6,9,8,13]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n):\ntrenza :: [a] -> [a] -> [a]\ntrenza xs ys = concat [[x,y] | (x,y) <- zip xs ys]\n\n-- 2\u00aa definici\u00f3n (por zipWith):\ntrenza2 :: [a] -> [a] -> [a]\ntrenza2 xs ys = concat (zipWith par xs ys)\n    where par x y = [x,y]\n\n-- 3\u00aa definici\u00f3n (por zipWith y sin argumentos):\ntrenza3 :: [a] -> [a] -> [a]\ntrenza3 = (concat .) . zipWith par\n    where par x y = [x,y]\n\n-- 4\u00aa definici\u00f3n (por recursi\u00f3n):\ntrenza4 :: [a] -> [a] -> [a]\ntrenza4 (x:xs) (y:ys) = x : y : trenza xs ys\ntrenza4 _      _      = []\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Comprobar con QuickCheck que el n\u00famero de elementos de\n-- (trenza xs ys) es el doble del m\u00ednimo de los n\u00fameros de elementos de\n-- xs e ys.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_trenza :: [Int] -> [Int] -> Bool\nprop_trenza xs ys =\n    length (trenza xs ys) == 2 * min (length xs) (length ys)\n            \n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_trenza\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Dado un n\u00famero cualquiera, llamamos MDI de ese n\u00famero\n-- a su mayor divisor impar. As\u00ed, el MDI de 12 es 3 y el MDI de 15 es 15. \n-- \n-- Definir la funci\u00f3n \n--    mdi :: Int -> Int\n-- tal que (mdi n) es el mayor divisor impar de n. Por ejemplo,\n--    mdi 12  ==  3\n--    mdi 15  ==  15\n-- ----------------------------------------------------------------------\n\nmdi :: Int -> Int\nmdi n | odd n     = n\n      | otherwise = head [x | x <- [n-1,n-3..1], n `rem` x == 0]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Comprobar con QuickCheck que la suma de los MDI de los\n-- n\u00fameros n+1, n+2, ..., 2n de cualquier entero positivo n siempre da\n-- n^2. \n-- \n-- Nota. Al hacer la comprobaci\u00f3n limitar el tama\u00f1o de las pruebas como\n-- se indica a continuaci\u00f3n\n--    ghci> quickCheckWith (stdArgs {maxSize=5}) prop_mdi\n--    +++ OK, passed 100 tests.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_mdi :: Int -> Property\nprop_mdi n =\n    n > 0 ==> sum [mdi x | x <- [n+1..2*n]] == n^2\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheckWith (stdArgs {maxSize=5}) prop_mdi\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1. Definir la funci\u00f3n \n--    reiteracion :: Int -> (a -> a) -> a -> a\n-- tal que (reiteracion n f x) es el resultado de aplicar n veces la\n-- funci\u00f3n f a x. Por ejemplo,\n--    reiteracion 10 (+1) 5  ==  15\n--    reiteracion 10 (+5) 0  ==  50\n--    reiteracion  4 (*2) 1  ==  16\n--    reiteracion  4 (5:) [] ==  [5,5,5,5]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n):\nreiteracion :: Int -> (a -> a) -> a -> a\nreiteracion 0 f x = x\nreiteracion n f x = f (reiteracion (n-1) f x)\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n sin el 3\u00aa argumento):\nreiteracion2 :: Int -> (a -> a) -> a -> a\nreiteracion2 0 f = id\nreiteracion2 n f = f . reiteracion2 (n-1) f\n\n-- 3\u00aa definici\u00f3n (con iterate):\nreiteracion3 :: Int -> (a -> a) -> a -> a\nreiteracion3 n f x = (iterate f x) !! n\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Comprobar con QuickCheck que se verifican las\n-- siguientes propiedades \n--    reiteracion 10 (+1) x  == 10 + x \n--    reiteracion 10 (+x) 0  == 10 * x \n--    reiteracion 10 (x:) [] == replicate 10 x  \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_reiteracion :: Int -> Bool\nprop_reiteracion x =\n    reiteracion 10 (+1) x  == 10 + x &&  \n    reiteracion 10 (+x) 0  == 10 * x &&\n    reiteracion 10 (x:) [] == replicate 10 x  \n    \n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_reiteracion\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. Definir la constante\n--    cadenasDe0y1 :: [String]\n-- tal que cadenasDe0y1 es la lista de todas las cadenas de ceros y\n-- unos. Por ejemplo, \n--    ghci> take 10 cadenasDe0y1\n--    [\"\",\"0\",\"1\",\"00\",\"10\",\"01\",\"11\",\"000\",\"100\",\"010\"]\n-- ---------------------------------------------------------------------\n\ncadenasDe0y1 :: [String]\ncadenasDe0y1 = \"\" : concat [['0':cs, '1':cs] | cs <- cadenasDe0y1]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Definir la funci\u00f3n\n--      posicion :: String -> Int\n-- tal que (posicion cs) es la posici\u00f3n de la cadena cs en la lista  \n-- cadenasDe0y1. Por ejemplo,\n--      posicion \"1\"   == 2\n--      posicion \"010\" == 9\n-- ---------------------------------------------------------------------\n\nposicion :: String -> Int\nposicion cs = \n    length (takeWhile (\/= cs) cadenasDe0y1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. El siguiente tipo de dato representa expresiones\n-- construidas con n\u00fameros, variables, sumas y productos\n--    data Expr = N Int\n--              | V String\n--              | S Expr Expr\n--              | P Expr Expr\n-- Por ejemplo, x*(5+z) se representa por (P (V \"x\") (S (N 5) (V \"z\"))) \n-- \n-- Definir la funci\u00f3n\n--    reducible :: Expr -> Bool\n-- tal que (reducible a) se verifica si a es una expresi\u00f3n reducible; es\n-- decir, contiene una operaci\u00f3n en la que los dos operandos son n\u00fameros. \n-- Por ejemplo,\n--    reducible (S (N 3) (N 4))             == True\n--    reducible (S (N 3) (V \"x\"))           == False\n--    reducible (S (N 3) (P (N 4) (N 5)))   == True\n--    reducible (S (V \"x\") (P (N 4) (N 5))) == True\n--    reducible (S (N 3) (P (V \"x\") (N 5))) == False\n--    reducible (N 3)                       == False\n--    reducible (V \"x\")                     == False\n-- ---------------------------------------------------------------------\n\ndata Expr = N Int\n          | V String\n          | S Expr Expr\n          | P Expr Expr\n\nreducible :: Expr -> Bool\nreducible (N _)           = False\nreducible (V _)           = False\nreducible (S (N _) (N _)) = True\nreducible (S a b)         = reducible a || reducible b\nreducible (P (N _) (N _)) = True\nreducible (P a b)         = reducible a || reducible b\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":"open","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":[238],"tags":[270,305,126],"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\/4645"}],"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=4645"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4645\/revisions"}],"predecessor-version":[{"id":4646,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4645\/revisions\/4646"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4645"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4645"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4645"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}