Prodotto cartesiano di 2 elenchi in Haskell

Desidero produrre il prodotto cartesiano di 2 elenchi in Haskell, ma non riesco a capire come farlo. Il prodotto cartesiano fornisce tutte le combinazioni degli elementi dell’elenco:

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

Questa non è una domanda reale sui compiti a casa e non è correlata a nessuna di queste domande, ma il modo in cui questo problema viene risolto può essere d’aiuto con uno su cui sono bloccato.

Questo è molto facile con la comprensione delle liste. Per ottenere il prodotto cartesiano degli elenchi xs e ys , abbiamo solo bisogno di prendere la tupla (x,y) per ogni elemento x in xs e ogni elemento y in ys .

Questo ci dà la seguente lista di comprensione:

 cartProd xs ys = [(x,y) | x <- xs, y <- ys] 

Come hanno notato altre risposte, usare la comprensione delle liste è il modo più naturale per farlo in Haskell.

Se stai imparando Haskell e vuoi lavorare sullo sviluppo di intuizioni su classi di tipi come Monad , tuttavia, è un esercizio divertente per capire perché questa definizione leggermente più breve è equivalente:

 import Control.Monad (liftM2) cartProd :: [a] -> [b] -> [(a, b)] cartProd = liftM2 (,) 

Probabilmente non vorresti mai scriverlo in codice reale, ma l’idea di base è qualcosa che vedrai in Haskell tutto il tempo: stiamo usando liftM2 per sollevare la funzione non monadica (,) in un monade-in questo caso specificamente la lista monad.

Se questo non ha senso o non è utile, dimenticalo: è solo un altro modo di considerare il problema.

Se gli elenchi di input sono dello stesso tipo, è ansible ottenere il prodotto cartesiano di un numero arbitrario di elenchi utilizzando la sequence (utilizzando la monade List ). Questo ti porterà una lista di liste invece di una lista di tuple:

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

C’è un modo molto elegante per farlo con i Functional Applicativi:

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

L’idea di base è di applicare una funzione su argomenti “avvolti”, ad es

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

In caso di liste, la funzione verrà applicata a tutte le combinazioni, quindi tutto ciò che devi fare è “tuple” con (,) .

Vedi http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors o (più teorico) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf per dettagli.

Il modo giusto è usare le list comprehensions, come altri hanno già indicato, ma se volessi farlo senza usare le list comprehensions per qualsiasi motivo, allora potresti fare questo:

 cartProd :: [a] -> [b] -> [(a,b)] cartProd xs [] = [] cartProd [] ys = [] cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys 

Un altro modo per ottenere questo risultato è l’utilizzo di applicativi:

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

Ancora un altro modo, usando la notazione:

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

Altre risposte presuppongono che i due elenchi di input siano finiti. Spesso, il codice haskell idiomatico include liste infinite e quindi vale la pena commentare brevemente come produrre un prodotto cartesiano infinito nel caso sia necessario.

L’approccio standard consiste nell’utilizzare la diagonalizzazione; scrivendo l’input in alto e l’altro in input a sinistra, potremmo scrivere una tabella bidimensionale che contenesse il prodotto cartesiano completo come questo:

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

Ovviamente, lavorare su una singola riga ci darà infiniti elementi prima che raggiunga la riga successiva; allo stesso modo andare in colonna sarebbe disastroso. Ma possiamo percorrere diagonali che vanno giù e a sinistra, ricominciando un po ‘più a destra ogni volta che raggiungiamo il bordo della griglia.

 a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 

…e così via. In ordine, questo ci darebbe:

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

Per codificarlo in Haskell, possiamo prima scrivere la versione che produce la tabella bidimensionale:

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

Un metodo inefficiente di diagonalizzazione è quindi iterare prima lungo le diagonali e poi lungo la profondità di ogni diagonale, tirando fuori ogni volta l'elemento appropriato. Per semplicità di spiegazione, supporrò che entrambe le liste di input siano infinite, quindi non dobbiamo gironzolare con il controllo dei limiti.

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

Questa implementazione è un po 'sfortunata: l'operazione di indicizzazione delle liste ripetuta !! diventa sempre più costoso man mano che procediamo, dando prestazioni asintotiche piuttosto brutte. Un'implementazione più efficiente prenderà l'idea di cui sopra ma la implementerà usando le cerniere. Quindi, dividiamo la nostra griglia infinita in tre forms come questa:

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

Il triangolo in alto a sinistra saranno i bit che abbiamo già emesso; il quadrilatero in alto a destra sarà costituito da righe parzialmente emesse, ma contribuirà comunque al risultato; e il rettangolo in basso saranno le righe che non abbiamo ancora iniziato a emettere. Per cominciare, il triangolo superiore e il quadrilatero superiore saranno vuoti e il rettangolo in basso sarà l'intera griglia. Su ogni passaggio, possiamo emettere il primo elemento di ogni riga nel quadrilatero superiore (essenzialmente spostando la linea inclinata di uno), quindi aggiungere una nuova riga dal rettangolo inferiore al quadrilatero superiore (essenzialmente spostando la linea orizzontale verso il basso di uno ).

 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] 

Anche se questo sembra un po 'più complicato, è significativamente più efficiente. Gestisce anche i limiti di controllo che abbiamo puntato nella versione più semplice.

Ma non dovresti scrivere tutto questo codice, naturalmente! Invece, dovresti usare il pacchetto universo . In Data.Universe.Helpers , c'è (+*+) , che raggruppa le funzioni di cartesian2d e diagonal sopra per dare solo l'operazione di prodotto cartesiana:

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

Puoi anche vedere le diagonali stesse se questa struttura diventa utile:

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

Se si hanno molti elenchi di prodotti insieme, l'iterazione (+*+) può distorcere ingiustamente determinate liste; puoi usare le choices :: [[a]] -> [[a]] per le tue esigenze di prodotto cartesiano n-dimensionale.

Bene, un modo molto semplice per farlo sarebbe quello di comprendere le liste:

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

Quale suppongo sia come lo farei, anche se non sono un esperto di Haskell (con qualsiasi mezzo).

qualcosa di simile a:

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

È un lavoro per la sequence . Una sua implementazione monadica potrebbe essere:

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

Come si può notare, quanto sopra è simile all’implementazione della map con funzioni pure ma in tipo monadico. Di conseguenza puoi semplificarlo fino a

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

Ecco la mia implementazione del prodotto cartesiano n-ary:

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