{"id":6134,"date":"2021-03-04T06:00:30","date_gmt":"2021-03-04T04:00:30","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6134"},"modified":"2021-03-11T18:20:03","modified_gmt":"2021-03-11T16:20:03","slug":"suma-de-la-lista-reducida","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/suma-de-la-lista-reducida\/","title":{"rendered":"Suma de la lista reducida"},"content":{"rendered":"<p>Definir las siguientes funciones<\/p>\n<pre lang=\"text\">\n   transformada :: Integral a => [a] -> [a]\n   reducida     :: Integral a => [a] -> [a]\n   sumaReducida :: Integral a => [a] -> a\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(transformada xs) es la lista obtenida sustituyendo en el primer de elementos consecutivos de xs el mayor por su diferencia, donde se supone que xs es una lista de enteros positivos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     transformada [7,2,6]  ==  [5,2,6]\n     transformada [2,7,6]  ==  [2,5,6]\n     transformada [2,2,6]  ==  [2,2,4]\n     transformada [2,2,2]  ==  [2,2,2]\n<\/pre>\n<ul>\n<li>(reducida xs) es la lista obtenida aplicando la transformaci\u00f3n anterior mientras sea posible (es decir, mientras tenga elementos distintos), donde se supone que xs es una lista de enteros positivos. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     reducida [7,2,6]   ==  [1,1,1]\n     reducida [6,9,21]  ==  [3,3,3]\n<\/pre>\n<ul>\n<li>(sumaReducida xs) es la suma de la reducida de la lista xs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     sumaReducida1 [7,2,6]   ==  3\n     sumaReducida1 [6,9,21]  ==  9\n<\/pre>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\n\n-- Definici\u00f3n de transformada\n-- ==========================\n\ntransformada :: Integral a => [a] -> [a]\ntransformada []  = []\ntransformada [x] = [x]\ntransformada (x:y:zs)\n  | x > y = x-y : y : zs\n  | x < y = x : y-x : zs\n  | otherwise = x : transformada (y:zs)\n\n-- 1\u00aa definici\u00f3n de reducida\n-- =========================\n\nreducida1 :: Integral a => [a] -> [a]\nreducida1 xs\n  | xs == ys  = xs\n  | otherwise = reducida ys\n  where ys = transformada xs\n\n-- 2\u00aa definici\u00f3n de reducida\n-- =========================\n\nreducida2 :: Integral a => [a] -> [a]\nreducida2 xs =\n  replicate (length xs) (foldl1 gcd xs)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sum (reducida1 [2,4..4*10^6])\n--    4000000\n--    (1.97 secs, 1,277,797,888 bytes)\n--    \u03bb> sum (reducida2 [2,4..4*10^6])\n--    4000000\n--    (1.92 secs, 1,277,798,344 bytes)\n\n-- Definici\u00f3n de reducida\n-- =======================\n\nreducida :: Integral a => [a] -> [a]\nreducida = reducida2\n\n-- 1\u00aa definici\u00f3n de sumaReducida\n-- =============================\n\nsumaReducida1 :: Integral a => [a] -> a\nsumaReducida1 = sum . reducida\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nsumaReducida2 :: Integral a => [a] -> a\nsumaReducida2 xs = genericLength xs * foldl1 gcd xs\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> sumaReducida1 [2,4..4*10^6]\n--    4000000\n--    (2.53 secs, 1,277,796,760 bytes)\n--    \u03bb> sumaReducida2 [2,4..4*10^6]\n--    4000000\n--    (1.89 secs, 1,214,376,960 bytes)\n<\/pre>\n<h4>Nuevas soluciones<\/h4>\n<ul>\n<li>En los comentarios se pueden escribir nuevas soluciones.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=&quot;haskell&quot;&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Definir las siguientes funciones transformada :: Integral a => [a] -> [a] reducida :: Integral a => [a] -> [a] sumaReducida :: Integral a => [a] -> a tales que (transformada xs) es la lista obtenida sustituyendo en el primer de elementos consecutivos de xs el mayor por su diferencia, donde se supone que xs&#8230;<\/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":[2,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\/6134"}],"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=6134"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6134\/revisions"}],"predecessor-version":[{"id":6171,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6134\/revisions\/6171"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6134"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6134"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6134"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}