{"id":6859,"date":"2022-04-01T06:00:04","date_gmt":"2022-04-01T04:00:04","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6859"},"modified":"2022-04-08T14:17:41","modified_gmt":"2022-04-08T12:17:41","slug":"biparticiones-de-una-lista","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/biparticiones-de-una-lista\/","title":{"rendered":"Biparticiones de una lista"},"content":{"rendered":"

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

\n   biparticiones :: [a] -> [([a],[a])]\n<\/pre>\n
tal que (biparticiones xs)<\/code> es la lista de pares formados por un prefijo de xs<\/code> y el resto de xs<\/code>. Por ejemplo,<\/p>\n
\n   \u03bb> biparticiones [3,2,5]\n   [([],[3,2,5]),([3],[2,5]),([3,2],[5]),([3,2,5],[])]\n   \u03bb> biparticiones \"Roma\"\n   [(\"\",\"Roma\"),(\"R\",\"oma\"),(\"Ro\",\"ma\"),(\"Rom\",\"a\"),(\"Roma\",\"\")]\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Data.List (inits, tails)\nimport Control.Applicative (liftA2)\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones1 :: [a] -> [([a],[a])]\nbiparticiones1 [] = [([],[])]\nbiparticiones1 (x:xs) =\n  ([],(x:xs)) : [(x:ys,zs) | (ys,zs) <- biparticiones1 xs]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones2 :: [a] -> [([a],[a])]\nbiparticiones2 xs =\n  [(take i xs, drop i xs) | i <- [0..length xs]]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones3 :: [a] -> [([a],[a])]\nbiparticiones3 xs =\n  [splitAt i xs | i <- [0..length xs]]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones4 :: [a] -> [([a],[a])]\nbiparticiones4 xs =\n  zip (inits xs) (tails xs)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones5 :: [a] -> [([a],[a])]\nbiparticiones5 = liftA2 zip inits tails\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nbiparticiones6 :: [a] -> [([a],[a])]\nbiparticiones6 = zip <$> inits <*> tails\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_biparticiones :: [Int] -> Bool\nprop_biparticiones xs =\n  all (== biparticiones1 xs)\n      [biparticiones2 xs,\n       biparticiones3 xs,\n       biparticiones4 xs,\n       biparticiones5 xs,\n       biparticiones6 xs]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_biparticiones\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> length (biparticiones1 [1..6*10^3])\n--    6001\n--    (2.21 secs, 3,556,073,552 bytes)\n--    \u03bb> length (biparticiones2 [1..6*10^3])\n--    6001\n--    (0.01 secs, 2,508,448 bytes)\n--\n--    \u03bb> length (biparticiones2 [1..6*10^6])\n--    6000001\n--    (2.26 secs, 2,016,494,864 bytes)\n--    \u03bb> length (biparticiones3 [1..6*10^6])\n--    6000001\n--    (2.12 secs, 1,584,494,792 bytes)\n--    \u03bb> length (biparticiones4 [1..6*10^6])\n--    6000001\n--    (0.78 secs, 1,968,494,704 bytes)\n--    \u03bb> length (biparticiones5 [1..6*10^6])\n--    6000001\n--    (0.79 secs, 1,968,494,688 bytes)\n--    \u03bb> length (biparticiones6 [1..6*10^6])\n--    6000001\n--    (0.77 secs, 1,968,494,720 bytes)\n--\n--    \u03bb> length (biparticiones4 [1..10^7])\n--    10000001\n--    (1.30 secs, 3,280,495,432 bytes)\n--    \u03bb> length (biparticiones5 [1..10^7])\n--    10000001\n--    (1.42 secs, 3,280,495,416 bytes)\n--    \u03bb> length (biparticiones6 [1..10^7])\n--    10000001\n--    (1.30 secs, 3,280,495,448 bytes)\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n