Definir la funci\u00f3n<\/p>\n
\n borra :: Int -> [a] -> [[a]]\n<\/pre>\ntal que (borra n xs) es la lista de las listas obtenidas borrando n elementos de xs. Por ejemplo,<\/p>\n
\n borra 0 \"abcd\" == [\"abcd\"]\n borra 1 \"abcd\" == [\"abc\",\"abd\",\"acd\",\"bcd\"]\n borra 2 \"abcd\" == [\"ab\",\"ac\",\"ad\",\"bc\",\"bd\",\"cd\"]\n borra 3 \"abcd\" == [\"a\",\"b\",\"c\",\"d\"]\n borra 4 \"abcd\" == [\"\"]\n borra 5 \"abcd\" == []\n borra 6 \"abcd\" == []\n length (borra 2 [1..300]) == 44850\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.List (nub, subsequences)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nborra1 :: Eq a => Int -> [a] -> [[a]]\nborra1 n xs = [ys | ys <- subsequences xs, length ys == k]\n where k = length xs - n\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nborra2 :: Eq a => Int -> [a] -> [[a]]\nborra2 0 xs = [xs]\nborra2 n [] = []\nborra2 n (x:xs) = [x:ys | ys <- borra2 n xs] ++ borra2 (n-1) xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nborra3 :: Eq a => Int -> [a] -> [[a]]\nborra3 n xs =\n nub (itera n borraUnoListas [xs])\n\n-- (borraUno xs) es la lista de listas obtenidas borrando un elemento de la\n-- lista no vac\u00eda xs de todas las formas posibles. Por ejemplo,\n-- borraUno \"abcde\" == [\"bcde\",\"acde\",\"abde\",\"abce\",\"abcd\"]\nborraUno :: [a] -> [[a]]\nborraUno [x] = [[]]\nborraUno (x:xs) = xs : map (x:) (borraUno xs)\n\n-- borraUnoListas [\"abc\", \"def\"] == [\"bc\",\"ac\",\"ab\",\"ef\",\"df\",\"de\"]\nborraUnoListas :: [[a]] -> [[a]]\nborraUnoListas = concatMap borraUno\n\n-- (itera k f x) es el resultado de aplicar k veces la funci\u00f3n f al\n-- elemento x. Por ejmplo,\n-- itera 3 (*2) 1 == 8\n-- itera 4 (+2) 10 == 18\nitera :: Eq a => Int -> (a -> a) -> a -> a\nitera 0 _ x = x\nitera n f x = itera (n-1) f (f x)\n\n-- 2\u00aa definici\u00f3n de itera\nitera2 :: Eq a => Int -> (a -> a) -> a -> a\nitera2 0 _ = id\nitera2 n f = itera2 (n-1) f . f\n\n-- 3\u00aa definici\u00f3n de itera\nitera3 :: Eq a => Int -> (a -> a) -> a -> a\nitera3 n f x = (iterate f x) !! n\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (borra1 10 [1..11])\n-- 11\n-- (0.03 secs, 527,712 bytes)\n-- \u03bb> length (borra2 10 [1..11])\n-- 11\n-- (0.01 secs, 917,720 bytes)\n-- \u03bb> length (borra3 10 [1..11])\n-- 11\n-- (22.32 secs, 20,104,455,496 bytes)\n--\n-- \u03bb> length (borra1 25 [1..26])\n-- 26\n-- (16.30 secs, 13,958,748,280 bytes)\n-- \u03bb> length (borra2 25 [1..26])\n-- 26\n-- (36.36 secs, 25,769,904,744 bytes)\n--\n-- \u03bb> length (borra1 2 [1..26])\n-- 325\n-- (16.51 secs, 13,958,767,696 bytes)\n-- \u03bb> length (borra2 2 [1..26])\n-- 325\n-- (0.01 secs, 168,272 bytes)\n-- \u03bb> length (borra3 2 [1..26])\n-- 325\n-- (0.03 secs, 1,209,992 bytes)\n--\n-- \u03bb> length (borra2 2 [1..100])\n-- 4950\n-- (0.06 secs, 59,128,272 bytes)\n-- \u03bb> length (borra3 2 [1..100])\n-- 4950\n-- (6.37 secs, 57,943,128 bytes)\n<\/pre>\nNuevas soluciones<\/h4>\n\n- En los comentarios se pueden escribir nuevas soluciones.\n
- El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n borra :: Int -> [a] -> [[a]] tal que (borra n xs) es la lista de las listas obtenidas borrando n elementos de xs. Por ejemplo, borra 0 \u00ababcd\u00bb == [\u00ababcd\u00bb] borra 1 \u00ababcd\u00bb == [\u00ababc\u00bb,\u00bbabd\u00bb,\u00bbacd\u00bb,\u00bbbcd\u00bb] borra 2 \u00ababcd\u00bb == [\u00abab\u00bb,\u00bbac\u00bb,\u00bbad\u00bb,\u00bbbc\u00bb,\u00bbbd\u00bb,\u00bbcd\u00bb] borra 3 \u00ababcd\u00bb == [\u00aba\u00bb,\u00bbb\u00bb,\u00bbc\u00bb,\u00bbd\u00bb] borra 4 \u00ababcd\u00bb == [\u00ab\u00bb] borra…<\/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\/6036"}],"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=6036"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6036\/revisions"}],"predecessor-version":[{"id":6080,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/6036\/revisions\/6080"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=6036"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=6036"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=6036"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}