berechnen n-ary Kartesisches Produkt

Question

Gegeben seien zwei Listen, kann ich eine Liste aller Permutationen die Kartesisches Produkt dieser beiden Listen erzeugen:

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

Wie kann ich permute erweitern, so dass statt zwei Listen der Einnahme , dauert es eine Liste (Länge n) von Listen und gibt eine Liste von Listen (Länge 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 

ich nichts Relevantes auf Hoogle nicht .. die einzige Funktion passend die Signatur transpose war finden konnte, die doesn t produzieren die gewünschte Ausgabe.

Edit: Ich denke, die 2-Liste-Version von diesem ist im Wesentlichen die Cartesian Product, aber ich kann nicht meinen Kopf rund um die Implementierung der n-ary Cartesian Product. Irgendwelche Zeiger?

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

Als Ergänzung zu jleedev Antwort (könnte dieses Format nicht in den Kommentaren):

Eine schnelle unkontrollierte Substitution von Listenfunktionen für monadische die:

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

Ich fand Eric Lippert Artikel auf computing Cartesian product with LINQ ziemlich hilfreich bei der Verbesserung meines Verständnisses, was vor sich ging. Hier ist eine mehr oder weniger direkte Übersetzung:

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

Oder mit mehr „Haskell-y“ kurz und bündig, bedeutungsParameterNamen;)

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

Dieser windet sich ziemlich ähnlich zu sein bis SCLV schließlich gebucht .

Answer 4

Wenn Sie mehr Kontrolle über die Ausgabe haben wollen, können Sie eine Liste als applicative Funktors verwenden können, zum Beispiel:

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

Lasst uns sagen, dass Sie eine Liste von Tupeln wollen statt:

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

Und es sieht auch irgendwie cool aus ...

Answer 5

Hier ist meine Art, es einfach zu implementieren, indem ich nur List-Comprehensions verwende.

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

Answer 6

Sie können das tun in 2 Möglichkeiten:

1. Mit Liste Verständnis

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

cp [] = [[]]

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

2. eine Falte Mit

cp1 :: [[a]] -> [[a ]]

cp1 xs = foldr f [[]] xs

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