{"id":1580,"date":"2015-06-22T06:00:31","date_gmt":"2015-06-22T04:00:31","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1580"},"modified":"2015-10-28T15:15:30","modified_gmt":"2015-10-28T13:15:30","slug":"maximos-de-una-lista","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/maximos-de-una-lista\/","title":{"rendered":"M\u00e1ximos de una lista"},"content":{"rendered":"

Definir la funci\u00f3n<\/p>\n

\n   maximos :: Ord a => [a] -> [a]\n<\/pre>\n
tal que (maximos xs) es la lista de los elementos de xs que son mayores que todos sus anteriores. Por ejemplo,<\/p>\n
\n   maximos [1,-3,5,2,3,4,7,6,7]                         ==  [1,5,7]\n   maximos \"bafcdegag\"                                  ==  \"bfg\"\n   maximos (concat (replicate (10^6) \"adxbcde\")++\"yz\")  ==  \"adxyz\"\n   length (maximos [1..10^6])                           ==  1000000\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.List (inits, nub)\n\n-- 1\u00aa definici\u00f3n (por comprensi\u00f3n)\nmaximos1 :: Ord a => [a] -> [a]\nmaximos1 xs =\n    [x | (ys,x) <- zip (inits xs) xs, all ( [a] -> [a]\nmaximos2 [] = []\nmaximos2 (x:xs) = x : maximos2 (filter (>x) xs)\n\n-- 3\u00aa definici\u00f3n (por recursi\u00f3n con acumulador)\nmaximos3 :: Ord a => [a] -> [a]\nmaximos3 [] = []\nmaximos3 (x:xs) = aux xs [x] x\n    where aux [] zs _ = reverse zs\n          aux (y:ys) zs m | y > m     = aux ys (y:zs) y\n                          | otherwise = aux ys zs m \n\n-- 4\u00aa definici\u00f3n (con scanl1):\nmaximos4 :: Ord a => [a] -> [a]\nmaximos4 = nub . scanl1 max \n\n-- Comparaci\u00f3n de eficiencia\n--    ghci> maximos1 (concat (replicate (10^3) \"adxbcde\") ++ \"yz\")\n--    \"adxyz\"\n--    (5.82 secs, 2859603952 bytes)\n--    ghci> maximos2 (concat (replicate (10^3) \"adxbcde\") ++ \"yz\")\n--    \"adxyz\"\n--    (0.02 secs, 5879664 bytes)\n--    ghci> maximos3 (concat (replicate (10^3) \"adxbcde\") ++ \"yz\")\n--    \"adxyz\"\n--    (0.03 secs, 4153680 bytes)\n--    ghci> maximos4 (concat (replicate (10^3) \"adxbcde\") ++ \"yz\")\n--    \"adxyz\"\n--    (0.02 secs, 4163296 bytes)\n--    \n--    ghci> maximos2 (concat (replicate (10^6) \"adxbcde\") ++ \"yz\")\n--    \"adxyz\"\n--    (3.64 secs, 1314485320 bytes)\n--    ghci> maximos3 (concat (replicate (10^6) \"adxbcde\") ++ \"yz\")\n--    \"adxyz\"\n--    (6.59 secs, 1706434544 bytes)\n--    ghci> maximos4 (concat (replicate (10^6) \"adxbcde\") ++ \"yz\")\n--    \"adxyz\"\n--    (0.89 secs, 1594567000 bytes)\n--    \n--    ghci> length (maximos2 [1..10^4])\n--    10000\n--    (17.34 secs, 4302913816 bytes)\n--    ghci> length (maximos3 [1..10^4])\n--    10000\n--    (0.03 secs, 6602488 bytes)\n--    ghci> length (maximos4 [1..10^4])\n--    10000\n--    (1.37 secs, 6820408 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n maximos :: Ord a => [a] -> [a] tal que (maximos xs) es la lista de los elementos de xs que son mayores que todos sus anteriores. Por ejemplo, maximos [1,-3,5,2,3,4,7,6,7] == [1,5,7] maximos \u00abbafcdegag\u00bb == \u00abbfg\u00bb maximos (concat (replicate (10^6) \u00abadxbcde\u00bb)++\u00bbyz\u00bb) == \u00abadxyz\u00bb length (maximos [1..10^6]) == 1000000 Soluciones import Data.List…<\/p>\n","protected":false},"author":1,"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":[5],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1580"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=1580"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1580\/revisions"}],"predecessor-version":[{"id":1645,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1580\/revisions\/1645"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1580"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1580"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1580"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}