Come funziona questa funzione Haskell per calcolare le permutazioni usando il lavoro di comprensione delle liste?

Question

Sto leggendo di Simon Thompson Haskell: The Craft della programmazione funzionale, e mi chiedo come fa questo lavoro:

perms [] = [[]] 
perms xs = [ x:ps | x <- xs , ps <- perms (xs\\[x]) ] 

io non riesco a capire come che perms(xs\\[x]) si suppone a funzionare. La traccia di una lista a due elementi mostra:

perms [2,3] 
    [ x:ps | x <- [2,3] , ps <- perms ([2,3] \\ [x]) ]  exe.1 
    [ 2:ps | ps <- perms [3] ] ++ [ 3:ps | ps <- perms [2] ] exe.2 
    ... 

Come si fa a passare exe.1-exe.2?

Answer 1

Si dice in sostanza:

1. prendere qualsiasi x dalla lista xs (x <- xs)
2. Prendere ps che è permutazione di lista xs\\[x] (cioè xs con cancellato x) - perms (xs\\[x])
3. di ritorno il risultato.

il perms(xs\\[x]) è chiamata ricorsiva che cancella x da xs.

Answer 2

Bene, inserisce solo 2 e 3 rispettivamente in [2,3] \\ [x]. In modo da avere

[ 2:ps | ps <- perms ([2,3] \\ [2]) ] ++ [ 3:ps | ps <- perms ([2,3] \\ [3]) ] 

E poiché \\ è l'operatore differenza, cioè restituisce gli elementi della prima lista che non sono nel secondo elenco, il risultato è rispettivamente [3] e [2].