Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 657
NO WAR WITH RUSSIA Avatar asked Aug 07 '10 22:08

NO WAR WITH RUSSIA


2 Answers

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

like image 128
Maciej Piechotka Avatar answered Nov 15 '22 09:11

Maciej Piechotka


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.

like image 25
sepp2k Avatar answered Nov 15 '22 08:11

sepp2k