{"id":6869,"date":"2022-04-04T06:00:03","date_gmt":"2022-04-04T04:00:03","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6869"},"modified":"2022-04-11T13:42:13","modified_gmt":"2022-04-11T11:42:13","slug":"trenzado-de-listas","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/trenzado-de-listas\/","title":{"rendered":"Trenzado de listas"},"content":{"rendered":"

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

\n   trenza :: [a] -> [a] -> [a]\n<\/pre>\n
tal que (trenza xs ys) es la lista obtenida intercalando los elementos de xs e ys. Por ejemplo,<\/p>\n
\n   trenza [5,1] [2,7,4]             ==  [5,2,1,7]\n   trenza [5,1,7] [2..]             ==  [5,2,1,3,7,4]\n   trenza [2..] [5,1,7]             ==  [2,5,3,1,4,7]\n   take 8 (trenza [2,4..] [1,5..])  ==  [2,1,4,5,6,9,8,13]\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Test.QuickCheck (quickCheck)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ntrenza1 :: [a] -> [a] -> [a]\ntrenza1 []     _      = []\ntrenza1 _      []     = []\ntrenza1 (x:xs) (y:ys) = x : y : trenza1 xs ys\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ntrenza2 :: [a] -> [a] -> [a]\ntrenza2 (x:xs) (y:ys) = x : y : trenza2 xs ys\ntrenza2 _      _      = []\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ntrenza3 :: [a] -> [a] -> [a]\ntrenza3 xs ys = concat [[x,y] | (x,y) <- zip xs ys]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ntrenza4 :: [a] -> [a] -> [a]\ntrenza4 xs ys = concat (zipWith par xs ys)\n\npar :: a -> a -> [a]\npar x y = [x,y]\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\n-- Explicaci\u00f3n de eliminaci\u00f3n de argumentos en composiciones con varios\n-- argumentos:\n\nf :: Int -> Int\nf x = x + 1\n\ng :: Int -> Int -> Int\ng x y = x + y\n\nh1, h2, h3, h4, h5, h6, h7 :: Int -> Int -> Int\nh1 x y  = f (g x y)\nh2 x y  = f ((g x) y)\nh3 x y  = (f . (g x)) y\nh4 x    = f . (g x)\nh5 x    = (f .) (g x)\nh6 x    = ((f .) . g) x\nh7      = (f .) . g\n\nprop_composicion :: Int -> Int -> Bool\nprop_composicion x y =\n  all (== h1 x y)\n      [p x y | p <- [h2, h3, h4, h5, h6, h7]]\n\n-- \u03bb> quickCheck prop_composicion\n-- +++ OK, passed 100 tests.\n\n-- En general,\n--    f . g             --> \\x -> f (g x)\n--    (f .) . g         --> \\x y -> f (g x y)\n--    ((f .) .) . g     --> \\x y z -> f (g x y z)\n--    (((f .) .) .) . g --> \\w x y z -> f (g w x y z)\n\ntrenza5 :: [a] -> [a] -> [a]\ntrenza5 = (concat .) . zipWith par\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_trenza :: [Int] -> [Int] -> Bool\nprop_trenza xs ys =\n  all (== trenza1 xs ys)\n      [trenza2 xs ys,\n       trenza3 xs ys,\n       trenza4 xs ys,\n       trenza5 xs ys]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_trenza\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> last (trenza1 [1,1..] [1..4*10^6])\n--    4000000\n--    (2.33 secs, 1,472,494,952 bytes)\n--    \u03bb> last (trenza2 [1,1..] [1..4*10^6])\n--    4000000\n--    (2.24 secs, 1,376,494,928 bytes)\n--    \u03bb> last (trenza3 [1,1..] [1..4*10^6])\n--    4000000\n--    (1.33 secs, 1,888,495,048 bytes)\n--    \u03bb> last (trenza4 [1,1..] [1..4*10^6])\n--    4000000\n--    (0.76 secs, 1,696,494,968 bytes)\n--    \u03bb> last (trenza5 [1,1..] [1..4*10^6])\n--    4000000\n--    (0.76 secs, 1,696,495,064 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