Kartesisches Produkt von 2 Listen in Haskell

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.

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]

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.

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

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.

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.

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

import Control.Applicative

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

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

Noch ein anderer Weg, mit der doNotation:

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

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.

etwas wie:

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

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

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 ]

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] 

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