Calculer produit

Question

cartésienne n-aire Étant donné deux listes, je peux produire une liste de toutes les permutations le produit cartésien de ces deux listes:

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] ] 

Comment puis-je prolonger permute de sorte qu'au lieu de prendre deux listes , il faut une liste (longueur n) des listes et retourne une liste de listes (longueur 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 

Je ne pouvais pas trouver quoi que ce soit pertinent sur Hoogle .. la seule fonction ne correspond à la signature était transpose, qui doesn ne produira pas la sortie désirée.

Éditer: Je pense que la version à 2 listes de ceci est essentiellement le Cartesian Product, mais je ne peux pas enrouler ma tête autour de la mise en œuvre du n-ary Cartesian Product. Des pointeurs?

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

En complément à la réponse de jleedev (n'a pas pu formater ce sujet dans les commentaires):

Une substitution sans contrôle rapide des fonctions de liste pour les monades:

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

J'ai trouvé l'article d'Eric Lippert sur computing Cartesian product with LINQ très utile pour améliorer ma compréhension de ce qui se passait. Voici une plus ou moins traduction directe:

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

Ou avec plus « Haskell-y » noms de paramètres laconiques, vides de sens;)

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

Cela serpente jusqu'à être tout à fait semblable à SCLV affiché après tout .

Answer 4

Si vous voulez avoir plus de contrôle sur la sortie, vous pouvez utiliser une liste comme foncteur applicative, par exemple:

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

Supposons que vous voulez une liste de tuples à la place:

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

Et il semble plutôt cool, aussi ...

Answer 5

Voici ma façon de le mettre en œuvre simplement, en utilisant uniquement des listes de compréhension.

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

Answer 6

Vous pouvez le faire de 2 façons:

1. En utilisant la compréhension de la liste

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

cp [] = [[]]

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

2. l'aide d'un pli

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

CP1 xs = fOLDR f [[]] xs

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