{"id":4325,"date":"2014-05-16T20:22:14","date_gmt":"2014-05-16T18:22:14","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4325"},"modified":"2014-05-19T20:24:29","modified_gmt":"2014-05-19T18:24:29","slug":"im2013-5o-examen-de-programacion-con-haskel","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/im2013-5o-examen-de-programacion-con-haskel\/","title":{"rendered":"IM2013: 5\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>En la clase de hoy del curso <a href=\"ttp:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas)<\/a> se ha realizado el 5\u00ba examen del curso.<\/p>\n<p>Las soluciones de los ejercicios del examen son<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- Inform\u00e1tica (1\u00ba del Grado en Matem\u00e1ticas)\n-- 5\u00ba examen de evaluaci\u00f3n continua (16 de mayo de 2014)\n-- ---------------------------------------------------------------------\n\nimport Data.Array\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. [2 puntos] Un m\u00ednimo local de una lista es un elemento\n-- de la lista que es menor que su predecesor y que su sucesor en la\n-- lista. Por ejemplo, 1 es un m\u00ednimo local de [3,2,1,3,7,7,1,0,2] ya\n-- que es menor  que 2 (su predecesor) y que 3 (su sucesor).\n-- \n-- Definir la funci\u00f3n\n--    minimosLocales :: Ord a => [a] -> [a]\n-- tal que (minimosLocales xs) es la lista de los m\u00ednimos locales de la\n-- lista xs. Por ejemplo,\n--    minimosLocales [3,2,1,3,7,7,9,6,8]  ==  [1,6]\n--    minimosLocales [1..100]             ==  []\n--    minimosLocales \"mqexvzat\"           ==  \"eva\"\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n):\nminimosLocales1 :: Ord a => [a] -> [a]\nminimosLocales1 (x:y:z:xs) | y < x &#038;&#038; y < z = y : minimosLocales1 (z:xs)\n                           | otherwise      = minimosLocales1 (y:z:xs)\nminimosLocales1 _                           = []\n\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n):\nminimosLocales2 :: Ord a => [a] -> [a]\nminimosLocales2 xs = \n    [y | (x,y,z) <- zip3 xs (tail xs) (drop 2 xs), y < x, y < z]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. [2 puntos] Definir la funci\u00f3n\n--    sumaExtremos :: Num a => [a] -> [a]\n-- tal que (sumaExtremos xs) es la lista sumando el primer elemento de\n-- xs con el \u00faltimo, el segundo con el pen\u00faltimo y as\u00ed\n-- sucesivamente. Por ejemplo,\n--    sumaExtremos [6,5,3,1]              ==  [7,8]\n--    sumaExtremos [6,5,3]                ==  [9,10]\n--    sumaExtremos [3,2,3,2]              ==  [5,5]\n--    sumaExtremos [6,5,3,1,2,0,4,7,8,9]  ==  [15,13,10,5,2]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n):\nsumaExtremos1 :: Num a => [a] -> [a]\nsumaExtremos1 []     = []\nsumaExtremos1 [x]    = [x+x]\nsumaExtremos1 (x:xs) = (x + last xs) : sumaExtremos1 (init xs)\n\n\n-- 2\u00aa definici\u00f3n (por recursi\u00f3n):\nsumaExtremos2 :: Num a => [a] -> [a]\nsumaExtremos2 xs = aux (take n xs) (take n (reverse xs))\n    where aux [] []         = []\n          aux (x:xs) (y:ys) = x+y : aux xs ys\n          m = length xs\n          n | even m    = m `div` 2\n            | otherwise = 1 + (m `div` 2)\n\n-- 3\u00aa definici\u00f3n (con zip):\nsumaExtremos3 :: Num a => [a] -> [a]\nsumaExtremos3 xs = take n [x+y | (x,y) <- zip xs (reverse xs)]\n    where m = length xs\n          n | even m    = m `div` 2\n            | otherwise = 1 + (m `div` 2)\n\n-- 4\u00aa definici\u00f3n (con zipWith):\nsumaExtremos4 :: Num a => [a] -> [a]\nsumaExtremos4 xs = take n (zipWith (+) xs (reverse xs))\n    where m = length xs\n          n | even m    = m `div` 2\n            | otherwise = 1 + (m `div` 2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. [2 puntos] Definir la funci\u00f3n\n--    listaRectangular :: Int -> Int -> a -> [a] -> [[a]] \n-- tal que (listaRectangular m n x xs) es una lista de m listas de\n-- longitud n formadas con los elementos de xs completada con x, si no\n-- xs no tiene suficientes elementos. Por ejemplo,\n--    listaRectangular 2 4 7 [0,3,5,2,4]  ==  [[0,3,5,2],[4,7,7,7]]\n--    listaRectangular 4 2 7 [0,3,5,2,4]  ==  [[0,3],[5,2],[4,7],[7,7]]\n--    listaRectangular 2 3 7 [0..]        ==  [[0,1,2],[3,4,5]]\n--    listaRectangular 3 2 7 [0..]        ==  [[0,1],[2,3],[4,5]]\n--    listaRectangular 3 2 'p' \"eva\"      ==  [\"ev\",\"ap\",\"pp\"]\n--    listaRectangular 3 2 'p' ['e'..]    ==  [\"ef\",\"gh\",\"ij\"]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n):\nlistaRectangular1 :: Int -> Int -> a -> [a] -> [[a]] \nlistaRectangular1 m n x xs =\n    take m (grupos n (xs ++ repeat x))\n\n-- (grupos n xs) es la lista obtenida agrupando los elementos de xs en\n-- grupos de n elementos, salvo el \u00faltimo que puede tener menos. Por\n-- ejemplo, \n--    grupos 2 [4,2,5,7,6]     ==  [[4,2],[5,7],[6]]\n--    take 3 (grupos 3 [1..])  ==  [[1,2,3],[4,5,6],[7,8,9]]\ngrupos :: Int -> [a] -> [[a]]\ngrupos _ [] = []\ngrupos n xs = take n xs : grupos n (drop n xs)\n\n-- 2\u00aa definici\u00f3n (por comprensi\u00f3n)\nlistaRectangular2 :: Int -> Int -> a -> [a] -> [[a]]\nlistaRectangular2 m n x xs = \n    take m [take n ys | m <- [0,n..n^2],\n                        ys <- [drop m xs ++ (replicate m x)]]\n\n-- 3\u00aa definici\u00f3n (por iteraci\u00f3n):\nlistaRectangular3 :: Int -> Int -> a -> [a] -> [[a]] \nlistaRectangular3 m n x xs =\n    take n [take n ys | ys <- iterate (drop n) (xs ++ repeat x)]\n\n-- 4\u00aa definici\u00f3n (sin el 4\u00ba argumento):\nlistaRectangular4 :: Int -> Int -> a -> [a] -> [[a]] \nlistaRectangular4 m n x = \n    take m . map (take n) . iterate (drop n) . (++ repeat x)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4 [2 puntos] Las expresiones aritm\u00e9ticas se pueden definir\n-- usando el siguiente tipo de datos\n--    data Expr = N Int \n--              | S Expr Expr \n--              | P Expr Expr \n--              deriving (Eq, Show)\n-- Por ejemplo, la expresi\u00f3n \n--    3*5 + 6*7\n-- se puede definir por\n--    S (P (N 3) (N 5)) (P (N 6) (N 7))\n-- \n-- Definir la funci\u00f3n  \n--    aplica :: (Int -> Int) -> Expr -> Expr\n-- tal que (aplica f e) es la expresi\u00f3n obtenida aplicando la funci\u00f3n f\n-- a cada uno de los n\u00fameros de la expresi\u00f3n e. Por ejemplo, \n--    ghci> aplica (+2) (S (P (N 3) (N 5)) (P (N 6) (N 7)))\n--    S (P (N 5) (N 7)) (P (N 8) (N 9))\n--    ghci> aplica (*2) (S (P (N 3) (N 5)) (P (N 6) (N 7)))\n--    S (P (N 6) (N 10)) (P (N 12) (N 14))\n-- ---------------------------------------------------------------------\n\ndata Expr = N Int \n          | S Expr Expr \n          | P Expr Expr \n          deriving (Eq, Show)\n\naplica :: (Int -> Int) -> Expr -> Expr\naplica f (N x)     = N (f x)\naplica f (S e1 e2) = S (aplica f e1) (aplica f e2)\naplica f (P e1 e2) = P (aplica f e1) (aplica f e2)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. [2 puntos] Las matrices enteras se pueden representar\n-- mediante tablas con \u00edndices enteros: \n--    type Matriz = Array (Int,Int) Int\n-- Por ejemplo, la matriz\n--    |4 1 3|\n--    |1 2 8|\n--    |6 5 7|\n-- se puede definir por\n--    listArray ((1,1),(3,3)) [4,1,3, 1,2,8, 6,5,7]     \n-- \n-- Definir la funci\u00f3n\n--    sumaColumnas :: Matriz -> Matriz\n-- tal que (sumaColumnas p) es la matriz obtenida sumando a cada columna\n-- la anterior salvo a la primera que le suma la \u00faltima columna. Por\n-- ejemplo, \n--    ghci> sumaColumnas (listArray ((1,1),(3,3)) [4,1,3, 1,2,8, 6,5,7])\n--    array ((1,1),(3,3)) [((1,1),7), ((1,2),5), ((1,3),4),\n--                         ((2,1),9), ((2,2),3), ((2,3),10),\n--                         ((3,1),13),((3,2),11),((3,3),12)]\n-- es decir, el resultado es la matriz\n--    | 7  5  4|\n--    | 9  3 10|\n--    |13 11 12|\n-- ------------------------------------------------------------------\n\ntype Matriz = Array (Int,Int) Int\n\nsumaColumnas :: Matriz -> Matriz\nsumaColumnas p =  \n    array ((1,1),(m,n)) \n          [((i,j), f i j) | i <- [1..m], j <- [1..n]] \n    where (_,(m,n)) = bounds p\n          f i 1 = p!(i,1) + p!(i,m)\n          f i j = p!(i,j) + p!(i,j-1)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy del curso Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas) se ha realizado el 5\u00ba examen del curso. Las soluciones de los ejercicios del examen son<\/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":[222],"tags":[270,300],"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\/4325"}],"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=4325"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4325\/revisions"}],"predecessor-version":[{"id":4327,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4325\/revisions\/4327"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4325"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4325"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4325"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}