{"id":1783,"date":"2011-12-14T16:48:48","date_gmt":"2011-12-14T16:48:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1783"},"modified":"2013-03-08T05:48:58","modified_gmt":"2013-03-08T05:48:58","slug":"i1m2011-ejercicios-sobre-funciones-de-orden-superior-y-plegados","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-ejercicios-sobre-funciones-de-orden-superior-y-plegados\/","title":{"rendered":"I1M2011: Ejercicios sobre funciones de orden superior y plegados"},"content":{"rendered":"<p>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 comentando las soluciones de ejercicios de la 3\u00aa  y 4\u00aa parte de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_9.hs\">9\u00aa relaci\u00f3n<\/a> y los 2 primeros de la <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/images\/0\/0a\/Rel_10.hs\">10\u00aa relaci\u00f3n<\/a><\/p>\n<p>La 3\u00aa parte contiene ejercicios sobre funciones de orden superior. En concreto, se estudian funciones para calcular<\/p>\n<ul>\n<li> el segmento inicial cuyos elementos verifican una propiedad y\n<li> el complementario del segmento inicial cuyos elementos verifican una propiedad.\n<\/ul>\n<p>La 4\u00aa parte contiene ejercicios sobre definiciones mediante map, filter y plegado. En concreto, se estudian funciones para calcular <\/p>\n<ul>\n<li> la lista de los valores de los elementos que cumplen una propiedad,\n<li> la concatenaci\u00f3n de una lista de listas,\n<li> la redefinici\u00f3n de la funci\u00f3n map y\n<li> la redefinici\u00f3n de la funci\u00f3n filter.\n<\/ul>\n<p> La 10\u00aa relaci\u00f3n contiene ejercicios con definiciones mediante<br \/>\nplegado. En concreto, se estudian definiciones por plegado para<br \/>\ncalcular <\/p>\n<ul>\n<li> el m\u00e1ximo elemento de una lista,\n<li> el m\u00ednimo elemento de una lista,\n<\/ul>\n<p>Estos ejercicios corresponden al <a href\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-11\/temas\/tema-7.pdf\">tema 7<\/a>.   <\/p>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n.<br \/>\n<!--more--><\/p>\n<p>Los ejercicios de la 9\u00aa relaci\u00f3n son<\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Funciones de orden superior                                        --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Redefinir por recursi\u00f3n la funci\u00f3n\r\n--    takeWhile :: (a -> Bool) -> [a] -> [a]\r\n-- tal que (takeWhile p xs) es la lista de los elemento de xs hasta el\r\n-- primero que no cumple la propiedad p. Por ejemplo,\r\n--    takeWhile (<7) [2,3,9,4,5]  ==  [2,3]\r\n-- ---------------------------------------------------------------------\r\n\r\ntakeWhile' :: (a -> Bool) -> [a] -> [a]\r\ntakeWhile' _ [] = []\r\ntakeWhile' p (x:xs) \r\n    | p x       = x : takeWhile' p xs\r\n    | otherwise = []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Redefinir por recursi\u00f3n la funci\u00f3n\r\n--    dropWhile :: (a -> Bool) -> [a] -> [a]\r\n-- tal que (dropWhile p xs) es la lista de eliminando los elemento de xs\r\n-- hasta el primero que cumple la propiedad p. Por ejemplo,\r\n--    dropWhile (<7) [2,3,9,4,5]  =>  [9,4,5]\r\n-- ---------------------------------------------------------------------\r\n\r\ndropWhile' :: (a -> Bool) -> [a] -> [a]\r\ndropWhile' _ [] = []\r\ndropWhile' p (x:xs)\r\n    | p x       = dropWhile' p xs\r\n    | otherwise = x:xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- 4. Definiciones mediante map, filter y plegado                     --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Se considera la funci\u00f3n \r\n--    filtraAplica :: (a -> b) -> (a -> Bool) -> [a] -> [b]\r\n-- tal que (filtraAplica f p xs) es la lista obtenida aplic\u00e1ndole a los\r\n-- elementos de xs que cumplen el predicado p la funci\u00f3n f. Por ejemplo,\r\n--    filtraAplica (4+) (<3) [1..7]  =>  [5,6]\r\n-- Se pide, definir la funci\u00f3n\r\n-- 1. por comprensi\u00f3n,\r\n-- 2. usando map y filter,\r\n-- 3. por recursi\u00f3n y\r\n-- 4. por plegado (con foldr).\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n con lista de comprensi\u00f3n es\r\nfiltraAplica_1 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\r\nfiltraAplica_1 f p xs = [f x | x <- xs, p x]\r\n\r\n-- La definici\u00f3n con map y filter es\r\nfiltraAplica_2 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\r\nfiltraAplica_2 f p xs = map f (filter p xs)\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\nfiltraAplica_3 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\r\nfiltraAplica_3 f p [] = []\r\nfiltraAplica_3 f p (x:xs) | p x       = f x : filtraAplica_3 f p xs\r\n                          | otherwise = filtraAplica_3 f p xs\r\n\r\n-- La definici\u00f3n por plegado es\r\nfiltraAplica_4 :: (a -> b) -> (a -> Bool) -> [a] -> [b]\r\nfiltraAplica_4 f p = foldr g []\r\n                     where g x y | p x       = f x : y\r\n                                 | otherwise = y\r\n\r\n-- La definici\u00f3n por plegado usando lambda es\r\nfiltraAplica_4' :: (a -> b) -> (a -> Bool) -> [a] -> [b]\r\nfiltraAplica_4' f p = \r\n    foldr (\\x y -> if p x then (f x : y) else y) []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Redefinir, usando foldr, la funci\u00f3n concat. Por ejemplo, \r\n--    concat' [[1,3],[2,4,6],[1,9]]  ==  [1,3,2,4,6,1,9]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es \r\nconcatR :: [[a]] -> [a]\r\nconcatR [] = []\r\nconcatR (xs:xss) = xs ++ concatR xss\r\n\r\n-- La definici\u00f3n por plegado es\r\nconcat' :: [[a]] -> [a]\r\nconcat' = foldr (++) []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 14. Redefinir, usando foldr, la funci\u00f3n map. Por ejemplo,\r\n--    map' (+2) [1,7,3]  ==  [3,9,5]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\nmapR :: (a -> b) -> [a] -> [b]\r\nmapR f [] = []\r\nmapR f (x:xs) = f x : mapR f xs\r\n\r\n-- La definici\u00f3n por plegado es\r\nmap' :: (a -> b) -> [a] -> [b]\r\nmap' f = foldr g []\r\n         where g x xs = f x : xs\r\n\r\n-- La definici\u00f3n por plegado usando lambda es\r\nmap'' :: (a -> b) -> [a] -> [b]\r\nmap'' f = foldr (\\x y -> f x:y) []\r\n\r\n-- Otra definici\u00f3n es\r\nmap''' :: (a -> b) -> [a] -> [b]\r\nmap''' f = foldr ((:) . f) []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 15. Redefinir, usando foldr, la funci\u00f3n filter. Por\r\n-- ejemplo, \r\n--    filter' (<4) [1,7,3,2]  =>  [1,3,2]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La definici\u00f3n por recursi\u00f3n es\r\nfilterR :: (a -> Bool) -> [a] -> [a]\r\nfilterR p [] = []\r\nfilterR p (x:xs) | p x       = x : filterR p xs\r\n                 | otherwise = filterR p xs\r\n\r\n-- La definici\u00f3n por plegado es\r\nfilter' :: (a -> Bool) -> [a] -> [a]\r\nfilter' p = foldr g []\r\n            where g x y | p x       = x:y \r\n                        | otherwise = y\r\n\r\n-- La definici\u00f3n por plegado y lambda es\r\nfilter' :: (a -> Bool) -> [a] -> [a]\r\nfilter' p = foldr (\\x y -> if (p x) then (x:y) else y) []\r\n<\/pre>\n<p>Los ejercicios de la 10\u00aa relaci\u00f3n son<\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.1. Definir, mediante recursi\u00f3n, la funci\u00f3n\r\n--    maximumR :: Ord a => [a] -> a\r\n-- tal que (maximumR xs) es el m\u00e1ximo de la lista xs. Por ejemplo,\r\n--    maximumR [3,7,2,5]  ==  7\r\n-- Nota: La funci\u00f3n maximumR es equivalente a la predefinida maximum.\r\n-- ---------------------------------------------------------------------\r\n\r\nmaximumR :: Ord a => [a] -> a\r\nmaximumR [x]      = x\r\nmaximumR (x:y:ys) = max x (maximumR (y:ys))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.2. La funci\u00f3n de plegado foldr1 est\u00e1 definida por \r\n--    foldr1 :: (a -> a -> a) -> [a] -> a\r\n--    foldr1 _ [x]    =  x\r\n--    foldr1 f (x:xs) =  f x (foldr1 f xs)\r\n-- \r\n-- Definir, mediante plegado con foldr1, la funci\u00f3n\r\n--    maximumP :: Ord a => [a] -> a\r\n-- tal que (maximumR xs) es el m\u00e1ximo de la lista xs. Por ejemplo,\r\n--    maximumP [3,7,2,5]  ==  7\r\n-- Nota: La funci\u00f3n maximumP es equivalente a la predefinida maximum.\r\n-- ---------------------------------------------------------------------\r\n\r\nmaximumP :: Ord a => [a] -> a\r\nmaximumP = foldr1 max\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir, mediante plegado con foldr1, la funci\u00f3n\r\n--    minimunP :: Ord a => [a] -> a\r\n-- tal que (minimunR xs) es el m\u00e1ximo de la lista xs. Por ejemplo,\r\n--    minimunP [3,7,2,5]  ==  7\r\n-- Nota: La funci\u00f3n minimunP es equivalente a la predefinida minimun.\r\n-- ---------------------------------------------------------------------\r\n\r\nminimumP :: Ord a => [a] -> a\r\nminimumP = foldr1 min\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentando las soluciones de ejercicios de la 3\u00aa y 4\u00aa parte de la 9\u00aa relaci\u00f3n y los 2 primeros de la 10\u00aa relaci\u00f3n La 3\u00aa parte contiene ejercicios sobre funciones de orden superior. En concreto, se estudian funciones para calcular el segmento&#8230;<\/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\/1783"}],"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=1783"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1783\/revisions"}],"predecessor-version":[{"id":2885,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1783\/revisions\/2885"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}