{"id":1909,"date":"2015-12-25T06:00:50","date_gmt":"2015-12-25T04:00:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=1909"},"modified":"2016-01-01T08:20:34","modified_gmt":"2016-01-01T06:20:34","slug":"inserciones-por-posicion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/inserciones-por-posicion\/","title":{"rendered":"Inserciones por posici\u00f3n"},"content":{"rendered":"<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"text\">\n   inserta :: [a] -> [[a]] -> [[a]]\n<\/pre>\n<p>tal que (inserta xs yss) es la lista obtenida insertando<\/p>\n<ul>\n<li>el primer elemento de xs como primero en la primera lista de yss,<\/li>\n<li>el segundo elemento de xs como segundo en la segunda lista de yss (si la segunda lista de yss tiene al menos un elemento), <\/li>\n<li>el tercer elemento de xs como tercero en la tercera lista de yss (si la tercera lista de yss tiene al menos dos elementos), <\/li>\n<\/ul>\n<p>y as\u00ed sucesivamente. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   inserta [1,2,3] [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,3,8]]\n   inserta [1,2,3] [[4,7],[] ,[9,5,8]]  ==  [[1,4,7],[],   [9,5,3,8]]\n   inserta [1,2]   [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,8]]\n   inserta [1,2,3] [[4,7],[6]]          ==  [[1,4,7],[6,2]]\n   inserta \"tad\"   [\"odo\",\"pra\",\"naa\"]  ==  [\"todo\",\"para\",\"nada\"]\n<\/pre>\n<p><strong>Nota<\/strong>: Este ejercicio es parte del examen del grupo 2 del 4 de diciembre.<\/p>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ninserta :: [a] -> [[a]] -> [[a]]\ninserta xs yss = aux xs yss 0 where\n    aux [] yss _ = yss\n    aux xs []  _ = []\n    aux (x:xs) (ys:yss) n \n        | length us == n = (us ++ x : vs) : aux xs yss (n+1)\n        | otherwise      = ys : aux xs yss (n+1)\n        where (us,vs) = splitAt n ys\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ninserta2 :: [a] -> [[a]] -> [[a]]\ninserta2 xs yss =  \n    [ins n x ys | (n,x,ys) <- zip3 [0..] xs yss] ++ drop (length xs) yss\n \nins :: Int -> a -> [a] -> [a]\nins n x ys | length ys < n  = ys\n           | otherwise      = take n ys ++ x : drop n ys\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> let n = 10000 in length (inserta [1..n] (replicate n (replicate n 0)))\n--    10000\n--    (3.28 secs, 6,400,568,776 bytes)\n--    \u03bb> let n = 10000 in length (inserta2 [1..n] (replicate n (replicate n 0)))\n--    10000\n--    (0.02 secs, 0 bytes)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Definir la funci\u00f3n inserta :: [a] -> [[a]] -> [[a]] tal que (inserta xs yss) es la lista obtenida insertando el primer elemento de xs como primero en la primera lista de yss, el segundo elemento de xs como segundo en la segunda lista de yss (si la segunda lista de yss tiene al menos&#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":[4],"tags":[46,28,6,73,47,44],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1909"}],"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=1909"}],"version-history":[{"count":6,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1909\/revisions"}],"predecessor-version":[{"id":1942,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/1909\/revisions\/1942"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=1909"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=1909"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=1909"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}