Prodotto cartesiano annidato di elenchi Haskell

Question

Vorrei creare un metodo in cui potrei fornire un elenco di lunghezze e restituire tutte le combinazioni di coordinate cartesiane fino a tali lunghezze. Più facile da spiegare con un esempio:

cart [2,5] 
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ] 

cart [2,2,2] 
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ] 

un elenco semplice di comprensione non funziona perché non so per quanto tempo le liste stanno per essere. Mentre adoro la semplicità di Haskell per molti problemi, questo è uno che potrei scrivere proceduralmente (in C o qualcosa) in 5 minuti mentre Haskell mi dà un aneurisma!

Una soluzione a questo problema specifico potrebbe aiutarmi molto; Mi piacerebbe anche conoscere i tuoi processi mentali quando affronti cose del genere.

Answer 1

Questo può essere risolto in modo ricorsivo. In primo luogo, il Cartesian product of nothing è {∅}:

cart [] = [[]] 

(O definire solo la forma 1-elemento se il prodotto vuota è valida:

cart [x] = [[i] | i <- [0 .. x-1]] 

)

Poi, il prodotto cartesiano x:xs può essere scritto come

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs] 

---

In generale, se si cosa scrivere una funzione f che richiede la lunghezza della lista N, provate a pensare a un modo per rendere f (N) dipende liste più piccole per esempio f (N - 1) solo, quindi risolvere il caso base f (0) o f (1) ecc. Questo trasforma il problema in una ricorsione che può essere facilmente risolta.

Answer 2

Scommetto che la soluzione procedurale implicherebbe la ricorsione. Anche la nostra soluzione Haskell coinvolgerà la ricorsione.

Quindi, ricorsione. Prima il caso ricorsivo.

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart] 
    where rcart = cart cs 

Qui stiamo solo dicendo che per ogni possibile iniziale di coordinate, e ogni possibile combinazione di coordinate cartesiane dalle restanti lunghezze, facciamo la cosa più ovvia di combinare il coordinamento con il restante coordinate.

Quindi il caso base.

cart [] = [[]] 

Si potrebbe pensare cart [] = []. L'ho fatto all'inizio. Ma pensa a ciò che il caso ricorsivo richiede dal caso base.

Answer 3

Umm ..

cart = sequence . map (enumFromTo 0 . subtract 1) 

E 'ragionevole aspettarsi che una funzione [[a]] -> [[a]] facendo quello che ci aspettiamo già esiste nella libreria. Quindi, se uno non ha familiarità con sequence, trovarlo è una questione semplice di hoogling esso.

Edit: come newacct sottolineato:

cart = mapM (enumFromTo 0 . subtract 1) 

Questo trovano anche alimentando la soluzione precedente HLint.