Producto cartesiano de una familia de conjuntos
Definir la función
|
1 |
producto :: [[a]] -> [[a]] |
tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> producto [[1,3],[2,5]] [[1,2],[1,5],[3,2],[3,5]] λ> producto [[1,3],[2,5],[6,4]] [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] λ> producto [[1,3,5],[2,4]] [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]] λ> producto [] [[]] |
Comprobar con QuickCheck que para toda lista de listas de números enteros, xss, se verifica que el número de elementos de (producto xss) es igual al producto de los números de elementos de cada una de las listas de xss.
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 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 |
module Producto_cartesiano where import Test.QuickCheck (quickCheck) import Control.Monad (liftM2) import Control.Applicative (liftA2) -- 1ª solución -- =========== producto1 :: [[a]] -> [[a]] producto1 [] = [[]] producto1 (xs:xss) = [x:ys | x <- xs, ys <- producto1 xss] -- 2ª solución -- =========== producto2 :: [[a]] -> [[a]] producto2 [] = [[]] producto2 (xs:xss) = [x:ys | x <- xs, ys <- ps] where ps = producto2 xss -- 3ª solución -- =========== producto3 :: [[a]] -> [[a]] producto3 [] = [[]] producto3 (xs:xss) = inserta3 xs (producto3 xss) -- (inserta xs xss) inserta cada elemento de xs en los elementos de -- xss. Por ejemplo, -- λ> inserta [1,2] [[3,4],[5,6]] -- [[1,3,4],[1,5,6],[2,3,4],[2,5,6]] inserta3 :: [a] -> [[a]] -> [[a]] inserta3 [] _ = [] inserta3 (x:xs) yss = [x:ys | ys <- yss] ++ inserta3 xs yss -- 4ª solución -- =========== producto4 :: [[a]] -> [[a]] producto4 = foldr inserta4 [[]] inserta4 :: [a] -> [[a]] -> [[a]] inserta4 [] _ = [] inserta4 (x:xs) yss = map (x:) yss ++ inserta4 xs yss -- 5ª solución -- =========== producto5 :: [[a]] -> [[a]] producto5 = foldr inserta5 [[]] inserta5 :: [a] -> [[a]] -> [[a]] inserta5 xs yss = [x:ys | x <- xs, ys <- yss] -- 6ª solución -- =========== producto6 :: [[a]] -> [[a]] producto6 = foldr inserta6 [[]] inserta6 :: [a] -> [[a]] -> [[a]] inserta6 xs yss = concatMap (\x -> map (x:) yss) xs -- 7ª solución -- =========== producto7 :: [[a]] -> [[a]] producto7 = foldr inserta7 [[]] inserta7 :: [a] -> [[a]] -> [[a]] inserta7 xs yss = xs >>= (\x -> map (x:) yss) -- 8ª solución -- =========== producto8 :: [[a]] -> [[a]] producto8 = foldr inserta8 [[]] inserta8 :: [a] -> [[a]] -> [[a]] inserta8 xs yss = (:) <$> xs <*> yss -- 9ª solución -- =========== producto9 :: [[a]] -> [[a]] producto9 = foldr inserta9 [[]] inserta9 :: [a] -> [[a]] -> [[a]] inserta9 = liftA2 (:) -- 10ª solución -- ============ producto10 :: [[a]] -> [[a]] producto10 = foldr (liftM2 (:)) [[]] -- 11ª solución -- ============ producto11 :: [[a]] -> [[a]] producto11 = sequence -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_producto :: [[Int]] -> Bool prop_producto xss = all (== producto1 xss) [ producto2 xss , producto3 xss , producto4 xss , producto5 xss , producto6 xss , producto7 xss , producto8 xss , producto9 xss , producto10 xss , producto11 xss ] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize = 9}) prop_producto -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (producto1 (replicate 7 [0..9])) -- 10000000 -- (10.51 secs, 10,169,418,496 bytes) -- λ> length (producto2 (replicate 7 [0..9])) -- 10000000 -- (2.14 secs, 1,333,870,712 bytes) -- λ> length (producto3 (replicate 7 [0..9])) -- 10000000 -- (3.33 secs, 1,956,102,056 bytes) -- λ> length (producto4 (replicate 7 [0..9])) -- 10000000 -- (0.98 secs, 1,600,542,752 bytes) -- λ> length (producto5 (replicate 7 [0..9])) -- 10000000 -- (2.10 secs, 1,333,870,288 bytes) -- λ> length (producto6 (replicate 7 [0..9])) -- 10000000 -- (1.17 secs, 1,600,534,632 bytes) -- λ> length (producto7 (replicate 7 [0..9])) -- 10000000 -- (0.35 secs, 1,600,534,352 bytes) -- λ> length (producto8 (replicate 7 [0..9])) -- 10000000 -- (0.87 secs, 978,317,848 bytes) -- λ> length (producto9 (replicate 7 [0..9])) -- 10000000 -- (1.38 secs, 1,067,201,016 bytes) -- λ> length (producto10 (replicate 7 [0..9])) -- 10000000 -- (0.54 secs, 2,311,645,392 bytes) -- λ> length (producto11 (replicate 7 [0..9])) -- 10000000 -- (1.32 secs, 1,067,200,992 bytes) -- -- λ> length (producto7 (replicate 7 [1..14])) -- 105413504 -- (3.77 secs, 16,347,739,040 bytes) -- λ> length (producto10 (replicate 7 [1..14])) -- 105413504 -- (5.11 secs, 23,613,162,016 bytes) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_longitud :: [[Int]] -> Bool prop_longitud xss = length (producto7 xss) == product (map length xss) -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize = 7}) prop_longitud -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.
La elaboración de las soluciones se describe en el siguiente vídeo