Wie funktioniert diese Haskell-Funktion zum Berechnen von Permutationen mit List-Verständnis Arbeit?

Question

Ich lese Simon Thompson Haskell: The Craft of Functional Programming, und ich frage mich, wie funktionierts:

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

ich nicht zu begreifen scheinen kann, wie das perms(xs\\[x]) funktionieren soll. Die Spur eines Zweielementliste zeigt:

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

Wie Sie exe.1-exe.2 gehen?

Answer 1

Es sagt im Grunde:

1. Nehmen Sie eine beliebige x aus der Liste xs (x <- xs)
2. ps Nehmen Sie das Permutation der Liste ist xs\\[x] (das heißt xs mit gelöscht x) - perms (xs\\[x])
3. Return das Ergebnis.

der perms(xs\\[x]) ist rekursiven Aufruf, die x von xs löscht.

Answer 2

Nun, es fügt nur 2 und 3 jeweils in [2,3] \\ [x]. So haben Sie

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

Und da \\ der Differenzoperator ist, das heißt, es gibt die Elemente der ersten Liste, die nicht in der zweiten Liste, ist das Ergebnis [3] und [2] sind.