Kartesisches Produkt von 2 Listen in Haskell

74

Ich möchte das kartesische Produkt aus 2 Listen in Haskell produzieren, kann aber nicht herausfinden, wie es geht. Das kartesische Produkt enthält alle Kombinationen der Listenelemente:

xs = [1,2,3]
ys = [4,5,6]

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Dies ist keine eigentliche Hausaufgabenfrage und hängt nicht mit einer solchen Frage zusammen, aber die Art und Weise, wie dieses Problem gelöst wird, kann bei einer Frage helfen, an der ich festhalte.

Callum Rogers
quelle

Antworten:

115

Dies ist mit Listenverständnis sehr einfach. Um das kartesische Produkt der Listen xsund zu erhalten ys, müssen wir nur das Tupel (x,y)für jedes Element xin xsund jedes Element yin nehmen ys.

Dies gibt uns das folgende Listenverständnis:

cartProd xs ys = [(x,y) | x <- xs, y <- ys]
sepp2k
quelle
2
Danke, so einfach und doch elegant, hat wirklich bei dem anderen Problem geholfen :)
Callum Rogers
3
Gut auch für Erlang, danke. Kleine Änderung in der Syntax: cartProd (Xs, Ys) -> [{X, Y} || X <- Xs, Y <- Ys].
Dacav
72

Wie andere Antworten festgestellt haben, ist die Verwendung eines Listenverständnisses in Haskell der natürlichste Weg, dies zu tun.

Wenn Sie Haskell lernen und daran arbeiten möchten, Intuitionen über Typklassen wie zu entwickeln Monad, ist es eine unterhaltsame Übung, herauszufinden, warum diese etwas kürzere Definition gleichwertig ist:

import Control.Monad (liftM2)

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)

Sie würden dies wahrscheinlich nie in echtem Code schreiben wollen, aber die Grundidee ist etwas, das Sie in Haskell ständig sehen werden: Wir verwenden liftM2, um die nicht-monadische Funktion (,)in eine Monade zu heben - in diesem Fall speziell die Liste Monade.

Wenn dies keinen Sinn ergibt oder nicht nützlich ist, vergessen Sie es - es ist nur eine andere Art, das Problem zu betrachten.

Travis Brown
quelle
4
Wahrscheinlich eine gute Idee, um zu erfahren, was Monaden tatsächlich zuerst tun: P
Callum Rogers
18
Als Fußnote (drei Jahre später): Ich würde jetzt vermuten, dass ich das Monadic liftM2hier ursprünglich aus Gründen der Klarheit verwendet habe (mehr Leute haben von Monaden gehört als von anwendbaren Funktoren?), Aber alles, was Sie brauchen, ist die anwendbare Funktorinstanz für Listen , so liftA2wird gleichwertig funktionieren.
Travis Brown
58

Wenn Ihre Eingabelisten vom gleichen Typ sind, können Sie das kartesische Produkt einer beliebigen Anzahl von Listen mit sequence(unter Verwendung der ListMonade) erhalten. Dadurch erhalten Sie eine Liste mit Listen anstelle einer Liste mit Tupeln:

> sequence [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
newacct
quelle
49

Es gibt eine sehr elegante Möglichkeit, dies mit Applicative Functors zu tun:

import Control.Applicative

(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Die Grundidee besteht darin, eine Funktion auf "umschlossene" Argumente anzuwenden, z

(+) <$> (Just 4) <*> (Just 10)
-- Just 14

Bei Listen wird die Funktion auf alle Kombinationen angewendet. Sie müssen sie also nur "tupeln" (,).

Siehe http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors oder (theoretischer) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf für Einzelheiten.

Landei
quelle
4
Ziemlich cool, dass Sie das Tupel nach Bedarf erweitern können: (,,) <$> [1..3] <*> [4..6] <*> [7..9]
Landon Poch
16

Andere Antworten setzen voraus, dass die beiden Eingabelisten endlich sind. Häufig enthält der idiomatische Haskell-Code unendliche Listen. Daher lohnt es sich, kurz zu erläutern, wie bei Bedarf ein unendliches kartesisches Produkt hergestellt werden kann.

Der Standardansatz ist die Verwendung der Diagonalisierung. Wenn wir die eine Eingabe oben und die andere Eingabe links schreiben, können wir eine zweidimensionale Tabelle schreiben, die das vollständige kartesische Produkt wie folgt enthält:

   1  2  3  4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...

.  .  .  .  . .
.  .  .  .  .  .
.  .  .  .  .   .

Wenn wir über eine einzelne Zeile arbeiten, erhalten wir natürlich unendlich viele Elemente, bevor die nächste Zeile erreicht wird. In ähnlicher Weise wäre es katastrophal, säulenweise vorzugehen. Aber wir können entlang von Diagonalen gehen, die nach unten und links gehen, und jedes Mal, wenn wir den Rand des Gitters erreichen, etwas weiter rechts beginnen.

a1

   a2
b1

      a3
   b2
c1

         a4
      b3
   c2
d1

...und so weiter. In der Reihenfolge würde dies uns geben:

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...

Um dies in Haskell zu codieren, können wir zuerst die Version schreiben, die die zweidimensionale Tabelle erzeugt:

cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]

Eine ineffiziente Methode zur Diagonalisierung besteht darin, zuerst entlang der Diagonalen und dann entlang der Tiefe jeder Diagonale zu iterieren und jedes Mal das entsprechende Element herauszuziehen. Zur Vereinfachung der Erklärung gehe ich davon aus, dass beide Eingabelisten unendlich sind, damit wir nicht mit der Überprüfung der Grenzen herumspielen müssen.

diagonalBad :: [[a]] -> [a]
diagonalBad xs =
    [ xs !! row !! col
    | diagonal <- [0..]
    , depth <- [0..diagonal]
    , let row = depth
          col = diagonal - depth
    ]

Diese Implementierung ist etwas unglücklich: Die wiederholte Listenindizierung wird im !!Laufe der Zeit immer teurer und führt zu einer ziemlich schlechten asymptotischen Leistung. Eine effizientere Implementierung übernimmt die oben genannte Idee, implementiert sie jedoch mithilfe von Reißverschlüssen. Also werden wir unser unendliches Gitter in drei Formen wie diese unterteilen:

a1 a2 / a3 a4 ...
     /
    /
b1 / b2 b3 b4 ...
  /
 /
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...

 .  .  .  . .
 .  .  .  .  .
 .  .  .  .   .

Das obere linke Dreieck sind die Bits, die wir bereits ausgegeben haben. Das obere rechte Viereck besteht aus Reihen, die teilweise emittiert wurden, aber dennoch zum Ergebnis beitragen. und das untere Rechteck besteht aus Zeilen, die wir noch nicht ausgegeben haben. Zunächst sind das obere Dreieck und das obere Viereck leer, und das untere Rechteck ist das gesamte Raster. Bei jedem Schritt können wir das erste Element jeder Zeile im oberen Viereck ausgeben (im Wesentlichen die schräge Linie um eins verschieben) und dann eine neue Zeile vom unteren Rechteck zum oberen Viereck hinzufügen (im Wesentlichen die horizontale Linie um eins nach unten verschieben) ).

diagonal :: [[a]] -> [a]
diagonal = go [] where
    go upper lower = [h | h:_ <- upper] ++ case lower of
        []         -> concat (transpose upper')
        row:lower' -> go (row:upper') lower'
        where upper' = [t | _:t <- upper]

Dies sieht zwar etwas komplizierter aus, ist aber deutlich effizienter. Es behandelt auch die Grenzen, die überprüft werden, auf die wir in der einfacheren Version gestoßen sind.

Aber Sie sollten diesen ganzen Code natürlich nicht selbst schreiben! Stattdessen sollten Sie das Universumspaket verwenden . In Data.Universe.Helpersgibt es (+*+), was das Obige zusammenfasst cartesian2dund diagonalFunktionen, um nur die kartesische Produktoperation zu ergeben:

Data.Universe.Helpers> "abcd" +*+ [1..4]
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)]

Sie können auch die Diagonalen selbst sehen, wenn diese Struktur nützlich wird:

Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4]
[('a',1)]
[('a',2),('b',1)]
[('a',3),('b',2),('c',1)]
[('a',4),('b',3),('c',2),('d',1)]
[('b',4),('c',3),('d',2)]
[('c',4),('d',3)]
[('d',4)]

Wenn Sie viele Listen zusammen produzieren müssen, (+*+)kann das Iterieren bestimmte Listen unfair beeinflussen. Sie können choices :: [[a]] -> [[a]]für Ihre n-dimensionalen kartesischen Produktanforderungen verwenden.

Daniel Wagner
quelle
Ich habe gerade Universe-1.1 installiert und es ist fabelhaft. Vielen Dank. Ja, dein Name steht überall, also wissen wir, dass wir ihm vertrauen können. Der Wert ist nicht kalkulierbar. Ich habe Diagonalen gemacht und diese ersten Ergebnisse sehen genau richtig aus. Kartesische Produkte sind ein Schmerz, aber Sie sind ein Schmerzmittel. Danke nochmal.
fp_mora
@fp_mora Freut mich zu hören, dass du es genießt!
Daniel Wagner
@ Daniel Wagner Es ist ein Glücksfall. Ich war nicht klar. Es sind die unendlichen Listen, die Schmerzen bereiten. Sie gehen geschickt damit um.
fp_mora
15

Ein weiterer Weg, dies zu erreichen, ist die Verwendung von Applikativen:

import Control.Applicative

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys
Paul
quelle
12

Der richtige Weg ist die Verwendung von Listenverständnissen, wie andere bereits betont haben. Wenn Sie dies jedoch aus irgendeinem Grund ohne Verwendung von Listenverständnissen tun möchten, können Sie dies tun:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys
Stuart Golodetz
quelle
2
Ein einfacher Weg ohne Listenverständnis istcartProd xs ys = xs >>= \x -> ys >>= \y -> [(x,y)]
Chuck
5
Stattdessen map (\y -> (x,y))kannst du schreiben map ((,) x).
Yitz
1
@Chuck: Schön :) Es ist eine Weile für mich Haskell-weise gewesen, weshalb ich auf der Seite von simplen Lösungen
irre
@ Yitz: Ja, guter Anruf. Ich hatte das vergessen (siehe oben auf "Es ist eine Weile her") ...
Stuart Golodetz
@ Stuart List Verständnis mag der "richtige Weg" sein, aber gibt es wirklich einen Nachteil, wenn man es so macht? Scheint mir in Ordnung zu sein, und es hilft einem Anfänger, sich mit einer einfachen Implementierung kartesischer Produkte zu beschäftigen. +1
Landon Poch
12

Noch ein anderer Weg, mit der doNotation:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
                    y <- ys
                    return (x,y)
gawi
quelle
6

Ein sehr einfacher Weg, dies zu tun, wäre das Listenverständnis:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = [(x, y) | x <- xs, y <- ys]

Ich nehme an, ich würde das tun, obwohl ich (auf keinen Fall) ein Haskell-Experte bin.

James Cunningham
quelle
5

etwas wie:

cartProd x y = [(a,b) | a <- x, b <- y]
vichle
quelle
3

Es ist ein Job für sequenceing. Eine monadische Umsetzung könnte sein:

cartesian :: [[a]] -> [[a]]
cartesian [] = return []
cartesian (x:xs) = x >>= \x' -> cartesian xs >>= \xs' -> return (x':xs')

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

Wie Sie vielleicht bemerken, ähnelt das Obige der Implementierung mapdurch reine Funktionen, jedoch in monadischer Form. Dementsprechend können Sie es bis auf vereinfachen

cartesian :: [[a]] -> [[a]]
cartesian = mapM id

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
Reduzieren
quelle
0

Hier ist meine Implementierung eines n-ary kartesischen Produkts:

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]
Christian Oudard
quelle
1
Wie wäre es crossProduct = sequence?
Daniel Wagner
Was ist, wenn die Liste leer ist? Ich vermute, Sie haben hier den falschen Basisfall identifiziert.
Feuer
0

Fügen Sie dem Enthusiasten nur einen weiteren Weg hinzu, indem Sie nur den rekursiven Mustervergleich verwenden.

cartProd :: [a]->[b]->[(a,b)]
cartProd _ []=[]
cartProd [] _ = []
cartProd (x:xs) (y:ys) = [(x,y)] ++ cartProd [x] ys  ++ cartProd xs ys ++  cartProd xs [y] 
Manoj R.
quelle
0

Rekursiver Mustervergleich ohne Listenverständnis

crossProduct [] b=[]
crossProduct (x : xs) b= [(x,b)] ++ crossProduct xs b

cartProd _ []=[]
cartProd x (u:uv) = crossProduct x u ++ cartProd x uv
Darshan D.
quelle
Nur-Code-Antworten werden nicht empfohlen. Bitte fügen Sie eine Erklärung hinzu, wie dies das Problem löst oder wie sich dies von den vorhandenen Antworten unterscheidet. Aus dem Rückblick
Nick