Wie funktioniert diese Haskell-Funktion zur Berechnung von Permutationen unter Verwendung des Listenverständnisses?

Question

Ich lese gerade Simon Thompsons Haskell: Das Handwerk der funktionalen Programmierung und ich frage mich, wie das funktioniert:

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

Ich kann nicht begreifen, wie das perms( xs\\[x] ) funktionieren soll. Die Spur einer zwei Elemente umfassenden Liste 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 kommt man von exe.1 a exe.2 ?

Answer 1

Nun, es fügt einfach 2 y 3 jeweils in [2,3] \\ [x] . Sie haben also

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

Und da \\ ist der Differenzoperator, d. h. er liefert die Elemente der ersten Liste, die nicht in der zweiten Liste enthalten sind, das Ergebnis ist [3] y [2] beziehungsweise.

Answer 2

Sie besagt im Wesentlichen:

1. Nehmen Sie eine x aus Liste xs ( x <- xs )
2. Nehmen Sie ps das ist eine Permutation der Liste xs\\[x] (d.h. xs mit gelöscht x ) - perms ( xs\\[x] )
3. Geben Sie das Ergebnis zurück.

die perms(xs\\[x]) ist ein rekursiver Aufruf, der Folgendes löscht x から xs .