Menu Close

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,

   ghci> producto [[1,3],[2,5]]
   [[1,2],[1,5],[3,2],[3,5]]
   ghci> 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]]
   ghci> producto [[1,3,5],[2,4]]
   [[1,2],[1,4],[3,2],[3,4],[5,2],[5,4]]
   ghci> 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

import Test.QuickCheck
 
-- 1ª solución
producto :: [[a]] -> [[a]]
producto []       = [[]]
producto (xs:xss) = [x:ys | x <- xs, ys <- producto xss]
 
-- 2ª solución
producto2 :: [[a]] -> [[a]]
producto2 = foldr f [[]]
  where f xs xss = [x:ys | x <- xs, ys <- xss]
 
-- 3ª solución
producto3 :: [[a]] -> [[a]]
producto3 = foldr aux [[]] 
  where aux [] _      = []
        aux (x:xs) ys = map (x:) ys ++ aux xs ys
 
-- 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.
Medio

5 soluciones de “Producto cartesiano de una familia de conjuntos

  1. jorcatote
    producto :: [[a]] -> [[a]]
    producto = foldr aux [[]] 
      where aux [] _ = []
            aux (x:xs) ys = map (x:) ys ++ aux xs ys
  2. mirmednav
    import Test.QuickCheck
    producto :: [[a]] -> [[a]]
    producto = foldr f [[]]
       where f xs xss = [x:ys | x <- xs, ys <- xss]
  3. jaibengue
    import Data.List
    import Test.QuickCheck
     
    producto :: [[a]] -> [[a]]
    producto []       = [[]]
    producto (xs:xss) = [e:u | e <- xs, u <- producto xss]
     
    prop_producto :: [[a]] -> Bool
    prop_producto xss =
      product [length xs | xs <- xss] == length (producto xss)
    • alerodrod5

      No es necesario importar la librería Data.List para el funcionamiento de esta definición.

  4. Chema Cortés
    import Test.QuickCheck
     
    producto :: [[a]] -> [[a]]
    producto = foldr ((<*>) . ((:)<$>) ) [[]]
     
    prop_producto :: [[a]] -> Bool
    prop_producto =
        (==) <$> length . producto <*> product . fmap length

Los comentarios están cerrados.