{"id":1690,"date":"2011-11-16T17:32:04","date_gmt":"2011-11-16T17:32:04","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1690"},"modified":"2013-03-08T05:49:00","modified_gmt":"2013-03-08T05:49:00","slug":"i1m2011-ejercicios-de-definiciones-por-recursion-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-ejercicios-de-definiciones-por-recursion-en-haskell\/","title":{"rendered":"I1M2011: Ejercicios de definiciones por recursi\u00f3n en Haskell (1)"},"content":{"rendered":"<p>En la clase de hoy de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los 12 primeros ejercicios de la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_6.hs\">6\u00aa relaci\u00f3n<\/a>, que tratan sobre definiciones por recursi\u00f3n.<\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- I1M 2011-12: Rel_6_sol.hs (8 de Noviembre de 2011)\r\n-- Definiciones por recursi\u00f3n.\r\n-- Departamento de Ciencias de la Computaci\u00f3n e I.A.\r\n-- Universidad de Sevilla\r\n-- =====================================================================\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- En esta relaci\u00f3n se presentan ejercicios con definiciones por\r\n-- recursi\u00f3n correspondientes al tema 6 cuyas transparencias se \r\n-- encuentran en  \r\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-6.pdf\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    potencia :: Integer -> Integer -> Integer\r\n-- tal que (potencia x n) es x elevado al n\u00famero natural n. Por ejemplo,  \r\n--    potencia 2 3  ==  8\r\n-- ---------------------------------------------------------------------\r\n\r\npotencia :: Integer -> Integer -> Integer\r\npotencia m 0     = 1\r\npotencia m (n+1) = m*(potencia m n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir por recursi\u00f3n la funci\u00f3n\r\n--    and' :: [Bool] -> Bool\r\n-- tal que (and' xs) se verifica si todos los elementos de xs son\r\n-- verdadero. Por ejemplo,\r\n--    and' [1+2 < 4, 2:[3] == [2,3]]  ==  True\r\n--    and' [1+2 < 3, 2:[3] == [2,3]]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nand' :: [Bool] -> Bool\r\nand' []     = True\r\nand' (b:bs) = b && and' bs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir por recursi\u00f3n la funci\u00f3n\r\n--    concat' :: [[a]] -> [a]\r\n-- tal que (concat' xss) es la lista obtenida concatenando las listas de\r\n-- xss. Por ejemplo,\r\n--    concat' [[1..3],[5..7],[8..10]]  ==  [1,2,3,5,6,7,8,9,10]\r\n-- ---------------------------------------------------------------------\r\n \r\nconcat' :: [[a]] -> [a]\r\nconcat' []       = []\r\nconcat' (xs:xss) = xs ++ concat' xss\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir por recursi\u00f3n la funci\u00f3n\r\n--    replicate' :: Int -> a -> [a]\r\n-- tal que (replicate' n x) es la lista formado por n copias del\r\n-- elemento x. Por ejemplo,\r\n--    replicate' 3 2  ==  [2,2,2]\r\n-- ---------------------------------------------------------------------\r\n \r\nreplicate' :: Int -> a -> [a]\r\nreplicate' 0 _     = []\r\nreplicate' (n+1) x = x : replicate' n x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir por recursi\u00f3n la funci\u00f3n\r\n--    selecciona :: [a] -> Int -> a\r\n-- tal que (selecciona xs n) es el n-\u00e9simo elemento de xs. Por ejemplo,\r\n--    selecciona [2,3,5,7] 2  ==  5 \r\n-- ---------------------------------------------------------------------\r\n\r\nselecciona :: [a] -> Int -> a\r\nselecciona (x:_)  0     = x\r\nselecciona (_:xs) (n+1) = selecciona xs n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir por recursi\u00f3n la funci\u00f3n\r\n--    elem' :: Eq a => a -> [a] -> Bool\r\n-- tal que (elem' x xs) se verifica si x pertenece a la lista xs. Por\r\n-- ejemplo, \r\n--    elem' 3 [2,3,5]  ==  True\r\n--    elem' 4 [2,3,5]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nelem' :: Eq a => a -> [a] -> Bool\r\nelem' x []                 = False\r\nelem' x (y:ys) | x == y    = True\r\n               | otherwise = elem' x ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir por recursi\u00f3n la funci\u00f3n\r\n--    mezcla :: Ord a => [a] -> [a] -> [a] \r\n-- tal que (mezcla xs ys) es la lista obtenida mezclando las listas\r\n-- ordenadas xs e ys. Por ejemplo,  \r\n--    mezcla [2,5,6] [1,3,4]  ==  [1,2,3,4,5,6]\r\n-- ---------------------------------------------------------------------\r\n\r\nmezcla :: Ord a => [a] -> [a] -> [a] \r\nmezcla []     ys                 = ys\r\nmezcla xs     []                 = xs\r\nmezcla (x:xs) (y:ys) | x <= y    = x : mezcla xs (y:ys)\r\n                     | otherwise = y : mezcla (x:xs) ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir por recursi\u00f3n la funci\u00f3n\r\n--    ordenada :: Ord a => [a] -> Bool\r\n-- tal que (ordenada xs) se verifica si xs es una lista ordenada. Por\r\n-- ejemplo, \r\n--    ordenada [2,3,5]  ==  True\r\n--    ordenada [2,5,3]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nordenada :: Ord a => [a] -> Bool\r\nordenada []       = True\r\nordenada [_]      = True\r\nordenada (x:y:xs) = x <= y &#038;&#038; ordenada (y:xs)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir por recursi\u00f3n la funci\u00f3n\r\n--    borra :: Eq a => a -> [a] -> [a]\r\n-- tal que (borra x xs) es la lista obtenida borrando una ocurrencia de\r\n-- x en la lista xs. Por ejemplo, \r\n--    borra 1 [1,2,1]  ==  [2,1]\r\n--    borra 3 [1,2,1]  ==  [1,2,1]\r\n-- ---------------------------------------------------------------------\r\n\r\nborra :: Eq a => a -> [a] -> [a]\r\nborra x []                 = []\r\nborra x (y:ys) | x == y    = ys\r\n               | otherwise = y : borra x ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir por recursi\u00f3n la funci\u00f3n \r\n--    esPermutacion :: Eq a => [a] -> [a] -> Bool\r\n-- tal que (esPermutacion xs ys) se verifica si xs es una permutaci\u00f3n de\r\n-- ys. Por ejemplo, \r\n--    esPermutacion [1,2,1] [2,1,1]  ==  True\r\n--    esPermutacion [1,2,1] [1,2,2]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nesPermutacion :: Eq a => [a] -> [a] -> Bool\r\nesPermutacion []     []     = True\r\nesPermutacion []     (y:ys) = False\r\nesPermutacion (x:xs) ys     = elem x ys && esPermutacion xs (borra x ys)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n \r\n--    mitades :: [a] -> ([a],[a]) \r\n-- tal que (mitades xs) es el par formado por las dos mitades en que se\r\n-- divide xs tales que sus longitudes difieren como m\u00e1ximo en uno. Por\r\n-- ejemplo, \r\n--    mitades [2,3,5,7,9]  ==  ([2,3],[5,7,9])\r\n-- ---------------------------------------------------------------------\r\n\r\nmitades :: [a] -> ([a],[a]) \r\nmitades xs = splitAt (length xs `div` 2) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir por recursi\u00f3n la funci\u00f3n \r\n--    ordMezcla :: Ord a => [a] -> [a]\r\n-- tal que (ordMezcla xs) es la lista obtenida ordenado xs por mezcla\r\n-- (es decir, considerando que la lista vac\u00eda y las listas unitarias\r\n-- est\u00e1n ordenadas y cualquier otra lista se ordena mezclando las dos\r\n-- listas que resultan de ordenar sus dos mitades por separado). Por\r\n-- ejemplo, \r\n--    ordMezcla [5,2,3,1,7,2,5]  =>  [1,2,2,3,5,5,7]\r\n-- ---------------------------------------------------------------------\r\n\r\nordMezcla :: Ord a => [a] -> [a]\r\nordMezcla []  = []\r\nordMezcla [x] = [x]\r\nordMezcla xs  = mezcla (ordMezcla ys) (ordMezcla zs)\r\n                where (ys,zs) = mitades xs\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los 12 primeros ejercicios de la 6\u00aa relaci\u00f3n, que tratan sobre definiciones por recursi\u00f3n. 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":[186],"tags":[295],"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\/1690"}],"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=1690"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1690\/revisions"}],"predecessor-version":[{"id":2911,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1690\/revisions\/2911"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1690"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1690"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1690"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}