Calcular n-arias producto cartesiano

Question

Dadas dos listas, puedo producir una lista de todas las permutaciones el producto cartesiano de estas dos listas:

permute :: [a] -> [a] -> [[a]] 
permute xs ys = [ [x, y] | x <- xs, y <- ys ] 

Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ] 

¿Cómo se amplía permute por lo que en lugar de tomar dos listas , se necesita una lista (longitud n) de las listas y devuelve una lista de listas (longitud n)

permute :: [[a]] -> [[a]] 

Example> permute [ [1,2], [3,4], [5,6] ] 
      == [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc 

no pude encontrar nada relevante sobre Hoogle .. la única función que concuerden con la firma era transpose, que doesn no produce la salida deseada

Editar: Creo que la versión de 2 listas de esto es esencialmente el Cartesian Product, pero no puedo entender la implementación del n-ary Cartesian Product. ¿Alguna sugerencia?

Answer 1

Prelude> sequence [[1,2],[3,4],[5,6]] 
[[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]] 

Answer 2

Como complemento a la respuesta de jleedev (no podía dar formato a esto en los comentarios):

Una sustitución sin control rápido de las funciones de lista de los monádicos:

sequence ms = foldr k (return []) ms 
    where 
    k m m' = do { x <- m; xs <- m'; return (x:xs) } 

....

k m m' = m >>= \x -> m' >>= \xs -> [x:xs] 
    k m m' = flip concatMap m $ \x -> flip concatMap m' $ \xs -> [x:xs] 
    k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m 

....

sequence ms = foldr k ([[]]) ms 
    where 
    k m m' = concatMap (\x -> concatMap (\xs -> [x:xs]) m') m 

Answer 3

Encontré el artículo de Eric Lippert en computing Cartesian product with LINQ bastante útil para mejorar mi comprensión de lo que estaba pasando. He aquí una traducción directa, más o menos:

cartesianProduct :: [[a]] -> [[a]] 
cartesianProduct sequences = foldr aggregator [[]] sequences 
        where aggregator sequence accumulator = 
         [ item:accseq |item <- sequence, accseq <- accumulator ] 

O con más, los nombres de parámetros sin sentido concisas "Haskell-Y";)

cartesianProduct = foldr f [[]] 
        where f l a = [ x:xs | x <- l, xs <- a ] 

Esto termina siendo bastante similar al SCLV publicado después de todo .

Answer 4

Si desea tener más control sobre la salida, se puede utilizar una lista como funtor aplicativo, por ejemplo:

(\x y z -> [x,y,­z]) <$> [1,2]­ <*> [4,5]­ <*> [6,7] 

Digamos que usted desea una lista de tuplas en su lugar:

(\x y z -> (x,y,­z)) <$> [1,2]­ <*> [4,5]­ <*> [6,7] 

Y se ve algo genial, también ...

Answer 5

Aquí está mi manera de implementarlo simplemente, usando solo listas de comprensión.

crossProduct :: [[a]] -> [[a]] 
crossProduct (axis:[]) = [ [v] | v <- axis ] 
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ] 

Answer 6

Puede hacerlo de 2 maneras:

1. Utilizando lista por comprensión

cp :: [[a]] -> [[a]]

cp [] = [[]]

cp (xs: xss) = [x: ys | x < - xs, ys < - XSS cp]

2. Uso de un pliegue

CP1 :: [[a]] -> [[a ]]

f [[]] xs

CP1 xs = foldr

where f xs xss = [x:ys | x <- xs, ys <- xss]