Trenzado de listas
Definir la función
|
1 |
trenza :: [a] -> [a] -> [a] |
tal que (trenza xs ys) es la lista obtenida intercalando los elementos de xs e ys. Por ejemplo,
|
1 2 3 4 |
trenza [5,1] [2,7,4] == [5,2,1,7] trenza [5,1,7] [2..] == [5,2,1,3,7,4] trenza [2..] [5,1,7] == [2,5,3,1,4,7] take 8 (trenza [2,4..] [1,5..]) == [2,1,4,5,6,9,8,13] |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== trenza1 :: [a] -> [a] -> [a] trenza1 [] _ = [] trenza1 _ [] = [] trenza1 (x:xs) (y:ys) = x : y : trenza1 xs ys -- 2ª solución -- =========== trenza2 :: [a] -> [a] -> [a] trenza2 (x:xs) (y:ys) = x : y : trenza2 xs ys trenza2 _ _ = [] -- 3ª solución -- =========== trenza3 :: [a] -> [a] -> [a] trenza3 xs ys = concat [[x,y] | (x,y) <- zip xs ys] -- 4ª solución -- =========== trenza4 :: [a] -> [a] -> [a] trenza4 xs ys = concat (zipWith par xs ys) par :: a -> a -> [a] par x y = [x,y] -- 5ª solución -- =========== -- Explicación de eliminación de argumentos en composiciones con varios -- argumentos: f :: Int -> Int f x = x + 1 g :: Int -> Int -> Int g x y = x + y h1, h2, h3, h4, h5, h6, h7 :: Int -> Int -> Int h1 x y = f (g x y) h2 x y = f ((g x) y) h3 x y = (f . (g x)) y h4 x = f . (g x) h5 x = (f .) (g x) h6 x = ((f .) . g) x h7 = (f .) . g prop_composicion :: Int -> Int -> Bool prop_composicion x y = all (== h1 x y) [p x y | p <- [h2, h3, h4, h5, h6, h7]] -- λ> quickCheck prop_composicion -- +++ OK, passed 100 tests. -- En general, -- f . g --> \x -> f (g x) -- (f .) . g --> \x y -> f (g x y) -- ((f .) .) . g --> \x y z -> f (g x y z) -- (((f .) .) .) . g --> \w x y z -> f (g w x y z) trenza5 :: [a] -> [a] -> [a] trenza5 = (concat .) . zipWith par -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_trenza :: [Int] -> [Int] -> Bool prop_trenza xs ys = all (== trenza1 xs ys) [trenza2 xs ys, trenza3 xs ys, trenza4 xs ys, trenza5 xs ys] -- La comprobación es -- λ> quickCheck prop_trenza -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (trenza1 [1,1..] [1..4*10^6]) -- 4000000 -- (2.33 secs, 1,472,494,952 bytes) -- λ> last (trenza2 [1,1..] [1..4*10^6]) -- 4000000 -- (2.24 secs, 1,376,494,928 bytes) -- λ> last (trenza3 [1,1..] [1..4*10^6]) -- 4000000 -- (1.33 secs, 1,888,495,048 bytes) -- λ> last (trenza4 [1,1..] [1..4*10^6]) -- 4000000 -- (0.76 secs, 1,696,494,968 bytes) -- λ> last (trenza5 [1,1..] [1..4*10^6]) -- 4000000 -- (0.76 secs, 1,696,495,064 bytes) |
El código se encuentra en GitHub.
La elaboración de las soluciones se describe en el siguiente vídeo
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>