Definir la funci\u00f3n<\/p>\n
\n producto :: [[a]] -> [[a]]\n<\/pre>\ntal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,<\/p>\n
\n \u03bb> producto [[1,3],[2,5]]\n [[1,2],[1,5],[3,2],[3,5]]\n \u03bb> producto [[1,3],[2,5],[6,4]]\n [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]]\n \u03bb> producto [[1,3,5],[2,4]]\n [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]]\n \u03bb> producto []\n [[]]\n<\/pre>\nComprobar con QuickCheck que para toda lista de listas de n\u00fameros enteros, xss, se verifica que el n\u00famero de elementos de (producto xss) es igual al producto de los n\u00fameros de elementos de cada una de las listas de xss.<\/p>\n
Soluciones<\/h4>\n\nmodule Producto_cartesiano where\n\nimport Test.QuickCheck (quickCheck)\nimport Control.Monad (liftM2)\nimport Control.Applicative (liftA2)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nproducto1 :: [[a]] -> [[a]]\nproducto1 [] = [[]]\nproducto1 (xs:xss) = [x:ys | x <- xs, ys <- producto1 xss]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nproducto2 :: [[a]] -> [[a]]\nproducto2 [] = [[]]\nproducto2 (xs:xss) = [x:ys | x <- xs, ys <- ps]\n where ps = producto2 xss\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nproducto3 :: [[a]] -> [[a]]\nproducto3 [] = [[]]\nproducto3 (xs:xss) = inserta3 xs (producto3 xss)\n\n-- (inserta xs xss) inserta cada elemento de xs en los elementos de\n-- xss. Por ejemplo,\n-- \u03bb> inserta [1,2] [[3,4],[5,6]]\n-- [[1,3,4],[1,5,6],[2,3,4],[2,5,6]]\ninserta3 :: [a] -> [[a]] -> [[a]]\ninserta3 [] _ = []\ninserta3 (x:xs) yss = [x:ys | ys <- yss] ++ inserta3 xs yss\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nproducto4 :: [[a]] -> [[a]]\nproducto4 = foldr inserta4 [[]]\n\ninserta4 :: [a] -> [[a]] -> [[a]]\ninserta4 [] _ = []\ninserta4 (x:xs) yss = map (x:) yss ++ inserta4 xs yss\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nproducto5 :: [[a]] -> [[a]]\nproducto5 = foldr inserta5 [[]]\n\ninserta5 :: [a] -> [[a]] -> [[a]]\ninserta5 xs yss = [x:ys | x <- xs, ys <- yss]\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\nproducto6 :: [[a]] -> [[a]]\nproducto6 = foldr inserta6 [[]]\n\ninserta6 :: [a] -> [[a]] -> [[a]]\ninserta6 xs yss = concatMap (\\x -> map (x:) yss) xs\n\n-- 7\u00aa soluci\u00f3n\n-- ===========\n\nproducto7 :: [[a]] -> [[a]]\nproducto7 = foldr inserta7 [[]]\n\ninserta7 :: [a] -> [[a]] -> [[a]]\ninserta7 xs yss = xs >>= (\\x -> map (x:) yss)\n\n-- 8\u00aa soluci\u00f3n\n-- ===========\n\nproducto8 :: [[a]] -> [[a]]\nproducto8 = foldr inserta8 [[]]\n\ninserta8 :: [a] -> [[a]] -> [[a]]\ninserta8 xs yss = (:) <$> xs <*> yss\n\n-- 9\u00aa soluci\u00f3n\n-- ===========\n\nproducto9 :: [[a]] -> [[a]]\nproducto9 = foldr inserta9 [[]]\n\ninserta9 :: [a] -> [[a]] -> [[a]]\ninserta9 = liftA2 (:)\n\n-- 10\u00aa soluci\u00f3n\n-- ============\n\nproducto10 :: [[a]] -> [[a]]\nproducto10 = foldr (liftM2 (:)) [[]]\n\n-- 11\u00aa soluci\u00f3n\n-- ============\n\nproducto11 :: [[a]] -> [[a]]\nproducto11 = sequence\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_producto :: [[Int]] -> Bool\nprop_producto xss =\n all (== producto1 xss)\n [ producto2 xss\n , producto3 xss\n , producto4 xss\n , producto5 xss\n , producto6 xss\n , producto7 xss\n , producto8 xss\n , producto9 xss\n , producto10 xss\n , producto11 xss\n ]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize = 9}) prop_producto\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (producto1 (replicate 7 [0..9]))\n-- 10000000\n-- (10.51 secs, 10,169,418,496 bytes)\n-- \u03bb> length (producto2 (replicate 7 [0..9]))\n-- 10000000\n-- (2.14 secs, 1,333,870,712 bytes)\n-- \u03bb> length (producto3 (replicate 7 [0..9]))\n-- 10000000\n-- (3.33 secs, 1,956,102,056 bytes)\n-- \u03bb> length (producto4 (replicate 7 [0..9]))\n-- 10000000\n-- (0.98 secs, 1,600,542,752 bytes)\n-- \u03bb> length (producto5 (replicate 7 [0..9]))\n-- 10000000\n-- (2.10 secs, 1,333,870,288 bytes)\n-- \u03bb> length (producto6 (replicate 7 [0..9]))\n-- 10000000\n-- (1.17 secs, 1,600,534,632 bytes)\n-- \u03bb> length (producto7 (replicate 7 [0..9]))\n-- 10000000\n-- (0.35 secs, 1,600,534,352 bytes)\n-- \u03bb> length (producto8 (replicate 7 [0..9]))\n-- 10000000\n-- (0.87 secs, 978,317,848 bytes)\n-- \u03bb> length (producto9 (replicate 7 [0..9]))\n-- 10000000\n-- (1.38 secs, 1,067,201,016 bytes)\n-- \u03bb> length (producto10 (replicate 7 [0..9]))\n-- 10000000\n-- (0.54 secs, 2,311,645,392 bytes)\n-- \u03bb> length (producto11 (replicate 7 [0..9]))\n-- 10000000\n-- (1.32 secs, 1,067,200,992 bytes)\n--\n-- \u03bb> length (producto7 (replicate 7 [1..14]))\n-- 105413504\n-- (3.77 secs, 16,347,739,040 bytes)\n-- \u03bb> length (producto10 (replicate 7 [1..14]))\n-- 105413504\n-- (5.11 secs, 23,613,162,016 bytes)\n\n-- Comprobaci\u00f3n de la propiedad\n-- ============================\n\n-- La propiedad es\nprop_longitud :: [[Int]] -> Bool\nprop_longitud xss =\n length (producto7 xss) == product (map length xss)\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheckWith (stdArgs {maxSize = 7}) prop_longitud\n-- +++ OK, passed 100 tests.\n<\/pre>\nEl c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\nLa elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n