Biparticiones de una lista
Definir la función
|
1 |
biparticiones :: [a] -> [([a],[a])] |
tal que (biparticiones xs) es la lista de pares formados por un prefijo de xs y el resto de xs. Por ejemplo,
|
1 2 3 4 |
λ> biparticiones [3,2,5] [([],[3,2,5]),([3],[2,5]),([3,2],[5]),([3,2,5],[])] λ> biparticiones "Roma" [("","Roma"),("R","oma"),("Ro","ma"),("Rom","a"),("Roma","")] |
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 |
import Data.List (inits, tails) import Control.Applicative (liftA2) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== biparticiones1 :: [a] -> [([a],[a])] biparticiones1 [] = [([],[])] biparticiones1 (x:xs) = ([],(x:xs)) : [(x:ys,zs) | (ys,zs) <- biparticiones1 xs] -- 2ª solución -- =========== biparticiones2 :: [a] -> [([a],[a])] biparticiones2 xs = [(take i xs, drop i xs) | i <- [0..length xs]] -- 3ª solución -- =========== biparticiones3 :: [a] -> [([a],[a])] biparticiones3 xs = [splitAt i xs | i <- [0..length xs]] -- 4ª solución -- =========== biparticiones4 :: [a] -> [([a],[a])] biparticiones4 xs = zip (inits xs) (tails xs) -- 5ª solución -- =========== biparticiones5 :: [a] -> [([a],[a])] biparticiones5 = liftA2 zip inits tails -- 6ª solución -- =========== biparticiones6 :: [a] -> [([a],[a])] biparticiones6 = zip <$> inits <*> tails -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_biparticiones :: [Int] -> Bool prop_biparticiones xs = all (== biparticiones1 xs) [biparticiones2 xs, biparticiones3 xs, biparticiones4 xs, biparticiones5 xs, biparticiones6 xs] -- La comprobación es -- λ> quickCheck prop_biparticiones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (biparticiones1 [1..6*10^3]) -- 6001 -- (2.21 secs, 3,556,073,552 bytes) -- λ> length (biparticiones2 [1..6*10^3]) -- 6001 -- (0.01 secs, 2,508,448 bytes) -- -- λ> length (biparticiones2 [1..6*10^6]) -- 6000001 -- (2.26 secs, 2,016,494,864 bytes) -- λ> length (biparticiones3 [1..6*10^6]) -- 6000001 -- (2.12 secs, 1,584,494,792 bytes) -- λ> length (biparticiones4 [1..6*10^6]) -- 6000001 -- (0.78 secs, 1,968,494,704 bytes) -- λ> length (biparticiones5 [1..6*10^6]) -- 6000001 -- (0.79 secs, 1,968,494,688 bytes) -- λ> length (biparticiones6 [1..6*10^6]) -- 6000001 -- (0.77 secs, 1,968,494,720 bytes) -- -- λ> length (biparticiones4 [1..10^7]) -- 10000001 -- (1.30 secs, 3,280,495,432 bytes) -- λ> length (biparticiones5 [1..10^7]) -- 10000001 -- (1.42 secs, 3,280,495,416 bytes) -- λ> length (biparticiones6 [1..10^7]) -- 10000001 -- (1.30 secs, 3,280,495,448 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>