{"id":4937,"date":"2015-06-15T19:39:04","date_gmt":"2015-06-15T17:39:04","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=4937"},"modified":"2015-06-17T09:39:55","modified_gmt":"2015-06-17T07:39:55","slug":"i1m2014-6o-examen-de-programacion-con-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2014-6o-examen-de-programacion-con-haskell\/","title":{"rendered":"I1M2014: 6\u00ba examen de programaci\u00f3n con Haskell"},"content":{"rendered":"<p>Hoy se ha realizado el 6\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: 6\u00ba examen de evaluaci\u00f3n continua (15 de junio de 2015)\n-- ---------------------------------------------------------------------\n\nimport Data.List \nimport qualified Data.Map as M \nimport I1M.BusquedaEnEspaciosDeEstados\nimport I1M.Grafo\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1. Una inversi\u00f3n de una lista xs es un par de elementos\n-- (x,y) de xs tal que y est\u00e1 a la derecha de x en xs y adem\u00e1s y es\n-- menor que x. Por ejemplo, en la lista [1,7,4,9,5] hay tres\n-- inversiones: (7,4), (7,5) y (9,5). \n-- \n-- Definir la funci\u00f3n \n--    inversiones :: Ord a -> [a] -> [(a,a)]\n-- tal que (inversiones xs) es la lista de las inversiones de xs. Por\n-- ejemplo, \n--    inversiones [1,7,4,9,5]  ==  [(7,4),(7,5),(9,5)]\n--    inversiones \"esto\"       ==  [('s','o'),('t','o')]\n-- ---------------------------------------------------------------------\n\ninversiones :: Ord a => [a] -> [(a,a)]\ninversiones []     = []\ninversiones (x:xs) = [(x,y) | y <- xs, y < x] ++ inversiones xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2. Las expresiones aritm\u00e9ticas se pueden representar como\n-- \u00e1rboles con n\u00fameros en las hojas y operaciones en los nodos. Por\n-- ejemplo, la expresi\u00f3n \"9-2*4\" se puede representar por el \u00e1rbol\n--      - \n--     \/ \\\n--    9   *\n--       \/ \\\n--      2   4\n-- \n-- Definiendo el tipo de dato Arbol por \n--    data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol\n-- la representaci\u00f3n del \u00e1rbol anterior es\n--    N (-) (H 9) (N (*) (H 2) (H 4))\n--\n-- Definir la funci\u00f3n\n--    valor :: Arbol -> Int\n-- tal que (valor a) es el valor de la expresi\u00f3n aritm\u00e9tica\n-- correspondiente al \u00e1rbol a. Por ejemplo, \n--    valor (N (-) (H 9) (N (*) (H 2) (H 4)))    ==  1\n--    valor (N (+) (H 9) (N (*) (H 2) (H 4)))    ==  17\n--    valor (N (+) (H 9) (N (div) (H 4) (H 2)))  ==  11\n--    valor (N (+) (H 9) (N (max) (H 4) (H 2)))  ==  13\n-- ---------------------------------------------------------------------\n\ndata Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol\n\nvalor :: Arbol -> Int\nvalor (H x)     = x\nvalor (N f i d) = f (valor i) (valor d)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3. Definir la funci\u00f3n\n--    agrupa :: Ord c => (a -> c) -> [a] -> M.Map c [a]\n-- tal que (agrupa f xs) es el diccionario obtenido agrupando los\n-- elementos de xs seg\u00fan sus valores mediante la funci\u00f3n f. Por ejemplo,\n--    ghci> agrupa length [\"hoy\", \"ayer\", \"ana\", \"cosa\"]\n--    fromList [(3,[\"hoy\",\"ana\"]),(4,[\"ayer\",\"cosa\"])]\n--    ghci> agrupa head [\"claro\", \"ayer\", \"ana\", \"cosa\"]\n--    fromList [('a',[\"ayer\",\"ana\"]),('c',[\"claro\",\"cosa\"])]\n--    ghci> agrupa length (words \"suerte en el examen\")\n--    fromList [(2,[\"en\",\"el\"]),(6,[\"suerte\",\"examen\"])]\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n (por recursi\u00f3n)\nagrupa1 :: Ord c => (a -> c) -> [a] -> M.Map c [a]\nagrupa1 _ []     = M.empty\nagrupa1 f (x:xs) = M.insertWith (++) (f x) [x] (agrupa1 f xs)\n\n-- 2\u00aa definici\u00f3n (por plegado)\nagrupa2 :: Ord c => (a -> c) -> [a] -> M.Map c [a]\nagrupa2 f = foldr (\\x -> M.insertWith (++) (f x) [x]) M.empty\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4. Los primeros t\u00e9rminos de la sucesi\u00f3n de Fibonacci son\n--    0, 1, 1, 2, 3, 5, 8, 13, 21, 34\n-- Se observa que el 6\u00ba t\u00e9rmino de la sucesi\u00f3n (comenzando a contar en\n-- 0) es el n\u00famero 8.\n--\n-- Definir la funci\u00f3n\n--    indiceFib :: Integer -> Maybe Integer\n-- tal que (indiceFib x) es justo el n\u00famero n si x es el n-\u00e9simo\n-- t\u00e9rminos de la sucesi\u00f3n de Fibonacci o Nothing en el caso de que x no\n-- pertenezca a la sucesi\u00f3n. Por ejemplo,\n--    indiceFib 8        ==  Just 6\n--    indiceFib 9        ==  Nothing\n--    indiceFib 21       ==  Just 8\n--    indiceFib 22       ==  Nothing\n--    indiceFib 9227465  ==  Just 35\n--    indiceFib 9227466  ==  Nothing\n-- ---------------------------------------------------------------------\n\nindiceFib :: Integer -> Maybe Integer\nindiceFib x | y == x    = Just n\n            | otherwise = Nothing\n    where (y,n) = head (dropWhile (\\(z,m) -> z < x) fibsNumerados)\n\n-- fibs es la lista de los t\u00e9rminos de la sucesi\u00f3n de Fibonacci. Por\n-- ejemplo, \n--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]\nfibs :: [Integer]\nfibs = 0 : 1 : [x+y | (x,y) <- zip fibs (tail fibs)]\n\n-- fibsNumerados es la lista de los t\u00e9rminos de la sucesi\u00f3n de Fibonacci\n-- juntos con sus posiciones. Por ejemplo,\n--    ghci> take 10 fibsNumerados\n--    [(0,0),(1,1),(1,2),(2,3),(3,4),(5,5),(8,6),(13,7),(21,8),(34,9)]\nfibsNumerados :: [(Integer,Integer)]\nfibsNumerados = zip fibs [0..]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5. Definir las funciones\n--    grafo   :: [(Int,Int)] -> Grafo Int Int\n--    caminos :: Grafo Int Int -> Int -> Int -> [[Int]]\n-- tales que \n-- + (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por\n--   ejemplo, \n--      ghci> grafo [(2,4),(4,5)]\n--      G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])\n-- + (caminos g a b) es la lista los caminos en el grafo g desde a hasta\n--   b sin pasar dos veces por el mismo nodo. Por ejemplo,\n--      ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)\n--      [[1,3,5,7],[1,3,7]]\n--      ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)\n--      [[2,5,3,7],[2,5,7]]\n--      ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)\n--      [[1,3,5,2],[1,3,7,5,2]]\n--      ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4\n--      []\n-- ---------------------------------------------------------------------\n\ngrafo :: [(Int,Int)] -> Grafo Int Int\ngrafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]\n    where ns = map fst as ++ map snd as\n          m  = minimum ns\n          n  = maximum ns\n\n-- 1\u00aa soluci\u00f3n (mediante espacio de estados)\ncaminos1 :: Grafo Int Int -> Int -> Int -> [[Int]]\ncaminos1 g a b = buscaEE sucesores esFinal inicial\n    where inicial          = [b]\n          sucesores (x:xs) = [z:x:xs | z <- adyacentes g x\n                                     , z `notElem` (x:xs)] \n          esFinal (x:xs)   = x == a\n\n-- 2\u00aa soluci\u00f3n (sin espacio de estados)\ncaminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]\ncaminos2 g a b = aux [[b]] where \n    aux [] = []\n    aux ((x:xs):yss)\n        | x == a    = (x:xs) : aux yss\n        | otherwise = aux ([z:x:xs | z <- adyacentes g x\n                                   , z `notElem` (x:xs)] \n                           ++ yss) \n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Hoy se ha realizado el 6\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],"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\/4937"}],"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=4937"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4937\/revisions"}],"predecessor-version":[{"id":4938,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/4937\/revisions\/4938"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=4937"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=4937"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=4937"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}