{"id":1800,"date":"2011-12-20T17:13:04","date_gmt":"2011-12-20T17:13:04","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1800"},"modified":"2013-03-08T05:48:57","modified_gmt":"2013-03-08T05:48:57","slug":"i1m2011-ejercicios-de-definiciones-por-plegado","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2011-ejercicios-de-definiciones-por-plegado\/","title":{"rendered":"I1M2011: Ejercicios de definiciones por plegado"},"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> se han explicado las soluciones de los 3 primeros ejercicios de la  <a href=\"https:\/\/www.glc.us.es\/~jalonso\/ejerciciosI1M2011G1\/imag<!--more-->es\/0\/0a\/Rel_10.hs&#8221;>10\u00aa relaci\u00f3n<\/a> que 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 y\n<li> la inversa de una lista.\n<\/ul>\n<p>Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:<\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\n\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\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.1. Definir, mediante recursi\u00f3n, la funci\u00f3n\r\n--    inversaR :: [a] -> [a]\r\n-- tal que (inversaR xs) es la inversa de la lista xs. Por ejemplo,\r\n--    inversaR [3,5,2,4,7]  ==  [7,4,2,5,3]\r\n-- ---------------------------------------------------------------------\r\n\r\ninversaR :: [a] -> [a]\r\ninversaR []     = []\r\ninversaR (x:xs) = (inversaR xs) ++ [x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.2. Definir, mediante plegado, la funci\u00f3n\r\n--    inversaP :: [a] -> [a]\r\n-- tal que (inversaP xs) es la inversa de la lista xs. Por ejemplo,\r\n--    inversaP [3,5,2,4,7]  ==  [7,4,2,5,3]\r\n-- ---------------------------------------------------------------------\r\n\r\ninversaP :: [a] -> [a]\r\ninversaP = foldr f []\r\n    where f x y = y ++ [x]\r\n\r\n-- La definici\u00f3n anterior puede simplificarse a\r\ninversaP_2 :: [a] -> [a]\r\ninversaP_2 = foldr f []\r\n    where f x = (++ [x])\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.3. Definir, por recursi\u00f3n con acumulador, la funci\u00f3n\r\n--    inversaR' :: [a] -> [a]\r\n-- tal que (inversaR' xs) es la inversa de la lista xs. Por ejemplo,\r\n--    inversaR' [3,5,2,4,7]  ==  [7,4,2,5,3]\r\n-- ---------------------------------------------------------------------\r\n\r\ninversaR' :: [a] -> [a]\r\ninversaR' xs = inversaAux [] xs\r\n    where inversaAux ys []     = ys\r\n          inversaAux ys (x:xs) = inversaAux (x:ys) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.4. La funci\u00f3n de plegado foldl est\u00e1 definida por\r\n--    foldl :: (a -> b -> a) -> a -> [b] -> a\r\n--    foldl f ys xs = aux ys xs\r\n--        where aux ys []     = ys\r\n--              aux ys (x:xs) = aux (f ys x) xs\r\n-- Definir, mediante plegado con foldl, la funci\u00f3n\r\n--    inversaP' :: [a] -> [a]\r\n-- tal que (inversaP' xs) es la inversa de la lista xs. Por ejemplo,\r\n--    inversaP' [3,5,2,4,7]  ==  [7,4,2,5,3]\r\n-- ---------------------------------------------------------------------\r\n\r\ninversaP' :: [a] -> [a]\r\ninversaP' = foldl f []\r\n    where f ys x = x:ys\r\n\r\n-- La definici\u00f3n anterior puede simplificarse lambda:\r\ninversaP'_2 :: [a] -> [a]\r\ninversaP'_2= foldl (\\ys x -> x:ys) []\r\n\r\n-- La definici\u00f3n puede simplificarse usando flip:\r\ninversaP'_3 :: [a] -> [a]\r\ninversaP'_3 = foldl (flip(:)) []\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.5. Comprobar con QuickCheck que las funciones reverse,\r\n-- inversaP e inversaP' son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_inversa :: Eq a => [a] -> Bool\r\nprop_inversa xs =\r\n    inversaP xs == ys &&\r\n    inversaP' xs == ys \r\n    where ys = reverse xs\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_inversa\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.6. Comparar la eficiencia de inversaP e inversaP'\r\n-- calculando el tiempo y el espacio que usado en evaluar las siguientes\r\n-- expresiones: \r\n--    head (inversaP [1..100000])\r\n--    head (inversaP' [1..100000])\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La sesi\u00f3n es\r\n--    ghci> :set +s\r\n--    ghci> head (inversaP [1..100000])\r\n--    100000\r\n--    (0.41 secs, 20882460 bytes)\r\n--    ghci> head (inversaP' [1..100000])\r\n--    1\r\n--    (0.00 secs, 525148 bytes)\r\n--    ghci> :unset +s\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>La clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han explicado las soluciones de los 3 primeros ejercicios de la<\/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\/1800"}],"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=1800"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1800\/revisions"}],"predecessor-version":[{"id":2879,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1800\/revisions\/2879"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1800"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1800"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1800"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}