How does this Haskell function compute permutations using list compilation?

Question

I am reading Simon Thompson Haskell: The Craft of Functional Programming, and I wonder how this works:

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

I cannot understand how perms( xs\\[x] ) . Tracing a list of two items 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

It basically says:

• Take any x from the list xs ( x <- xs )
• Take ps , which is a permutation of the list xs\\[x] (ie xs with x removed) - perms ( xs\\[x] )
• Return the result.

perms(xs\\[x]) is a recursive call that removes x from xs .

Answer 2

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

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

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