How does this Haskell function to calculate permutations using list comprehension work?

Question

I'm reading Simon Thompson's Haskell: The Craft of Functional Programming, and I'm wondering how does this work:

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

I can't seem to grasp how that perms( xs\\[x] ) is supposed to function. The trace of a two element list shows:

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

How do you go from exe.1 to exe.2?

Answer 1

Well, it just inserts 2 and 3 respectively into [2,3] \\ [x]. So you have

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

And since \\ is the difference operator, i.e. it returns the elements of the first list which are not in the second list, the result is [3] and [2] respectively.

Answer 2

It basicly says:

1. Take any x from list xs (x <- xs)
2. Take ps that is permutation of list xs\\[x] (i.e. xs with deleted x) - perms ( xs\\[x] )
3. Return the result.

the perms(xs\\[x]) is recursive call that deletes x from xs.