Producto cartesiano de una familia de conjuntos
Definir la función
producto :: [[a]] -> [[a]]
tal que (producto xss) es el producto cartesiano de los conjuntos xss. Por ejemplo,
λ> 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.
Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación
quickCheckWith (stdArgs {maxSize=9}) prop_producto
Soluciones
-- 1ª solución -- =========== producto :: [[a]] -> [[a]] producto [] = [[]] producto (xs:xss) = inserta xs (producto 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]] -- La función inserta se puede definir de distintas maneras, como se -- muestra a continuación. Elegimos la primera. inserta :: [a] -> [[a]] -> [[a]] inserta = inserta1 inserta1 :: [a] -> [[a]] -> [[a]] inserta1 [] _ = [] inserta1 (x:xs) yss = [x:ys | ys <- yss] ++ inserta1 xs yss inserta2 :: [a] -> [[a]] -> [[a]] inserta2 [] _ = [] inserta2 (x:xs) yss = map (x:) yss ++ inserta2 xs yss inserta3 :: [a] -> [[a]] -> [[a]] inserta3 xs yss = concatMap (\k -> map (k:) yss) xs inserta4 :: [a] -> [[a]] -> [[a]] inserta4 xs xss = [x:ys | x <- xs, ys <- xss] -- 2ª solución -- =========== producto2 :: [[a]] -> [[a]] producto2 = foldr inserta [[]] -- 3ª solución -- =========== producto3 :: [[a]] -> [[a]] producto3 [] = [[]] producto3 (xs:xss) = [x:ys | x <- xs, ys <- producto3 xss] -- 4ª solución -- =========== producto4 :: [[a]] -> [[a]] producto4 = sequence -- La propiedad es prop_producto :: [[Int]] -> Bool prop_producto xss = length (producto xss) == product (map length xss) -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=9}) prop_producto -- +++ OK, passed 100 tests.