Desemparejamiento de listas
Definir la función
|
1 |
desemparejada :: [(a,b)] -> ([a],[b]) |
tal que (desemparejada ps) es el par de lista (xs,ys) tal que al emparejar (con zip) xs e ys devuelve ps. Por ejemplo,
|
1 2 |
ghci> desemparejada [(3,'l'),(2,'u'),(5,'i'),(9,'s')] ([3,2,5,9],"luis") |
Comprobar con QuickCheck que
- desemparejada es equivalente a la función predefinida unzip.
- si el valor de (desemparejada ps) es (xs,ys), entonces (zip xs ys) es igual a ps.
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 |
import Test.QuickCheck -- 1ª definición (por comprensión): desemparejada1 :: [(a,b)] -> ([a],[b]) desemparejada1 ps = ([x | (x,_) <- ps], [y | (_,y) <- ps]) -- 2ª definición (con map): desemparejada2 :: [(a,b)] -> ([a],[b]) desemparejada2 ps = (map fst ps, map snd ps) -- 3ª definición (por recursión): desemparejada3 :: [(a,b)] -> ([a],[b]) desemparejada3 [] = ([],[]) desemparejada3 ((x,y):ps) = (x:xs,y:ys) where (xs,ys) = desemparejada3 ps -- 4ª definición (por plegado): desemparejada4 :: [(a,b)] -> ([a],[b]) desemparejada4 = foldr f ([],[]) where f (x,y) (xs,ys) = (x:xs, y:ys) -- 5ª definición (por plegado por la izquierda): desemparejada5 :: [(a,b)] -> ([a],[b]) desemparejada5 ps = (reverse us, reverse vs) where (us,vs) = foldl f ([],[]) ps f (xs,ys) (x,y) = (x:xs,y:ys) -- Comparación de eficiencia- -- ghci> let ps = zip [1..10^7] [1..10^7] -- -- ghci> length (fst (desemparejada1 ps)) -- 10000000 -- (3.67 secs, 360441524 bytes) -- -- ghci> length (fst (desemparejada2 ps)) -- 10000000 -- (0.38 secs, 440476764 bytes) -- -- ghci> length (fst (desemparejada3 ps)) -- 10000000 -- (14.11 secs, 2160188668 bytes) -- -- ghci> length (fst (desemparejada4 ps)) -- 10000000 -- (19.08 secs, 1658689692 bytes) -- -- ghci> length (fst (desemparejada5 ps)) -- 10000000 -- (20.98 secs, 1610061796 bytes) -- En lo que sigue, usaremos la 2º definición desemparejada :: [(a,b)] -> ([a],[b]) desemparejada = desemparejada2 -- La primera propiedad es prop_desemparejada_1 :: (Eq a, Eq b) => [(a,b)] -> Bool prop_desemparejada_1 ps = desemparejada ps == unzip ps -- Su comprobación es -- ghci> quickCheck prop_desemparejada_1 -- +++ OK, passed 100 tests. -- La segunda propiedad es prop_desemparejada_2 :: (Eq a, Eq b) => [(a,b)] -> Bool prop_desemparejada_2 ps = zip xs ys == ps where (xs,ys) = desemparejada ps -- Su comprobación es -- ghci> quickCheck prop_desemparejada_2 -- +++ OK, passed 100 tests. |
2 Comentarios