Permutation Algorithm in Haskell
I read this permutation function example in a Haskell textbook and I was wondering if someone could help me understand what is happening. Also, assume that the function delete simply deletes the first occurrence of a value from a list and returns the list
perms [] = [[]]
perms p = [x:xs | x <-p, xs <- perms (delete x p)]
I understand that an empty list equals a list with an empty list. For all other cases the head of the list is prepended to x and the numbers except the head recurses through the algorithm.
My question is how does this work, for example, my pseudocode understanding is
perms[1,2,3]
x <- 1
xs <- [2,3]
perms [2,3]
x <- 2
xs <- 3
perms [3]
x <- 3
xs <- []
this would produce the list [1,2,3] how does the algorithm produce the other list results.
An output of this code working is as follows:
>perms [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
The expression:
[x:xs | x <- p, xs <- perms (delete x p)]
is a list comprehension, which means that each of the a <- b expressions on the right hand side form a sort of implicit loop that your pseudocode doesn't account for.
Written in pseudocode with explicit loops, it's equivalent to:
for each x in p:
for each xs in perms (delete x p):
yield (x:xs)
-- and return the list of all results yielded
It can then be helpful to think through the definition recursively from the bottom up. If you run perm [n] for any n, then the outer loop is only evaluated for x = n, and since:
perms (delete n [n]) = perms [] = [[]]
the inner loop is equivalent to:
for each xs in [[]]
...
and is only evaluated for xs = []. Therefore, only one value is yielded:
x:xs = n:[] = [n]
So, perm [n] gives a list of the single element [n], in other words [[n]].
If you move on to perm [1,2] and imagine unfolding the loops:
-- for each x in [1,2]
first, for x = 1
-- for each xs in perms (delete 1 [1,2]) = perms [2] = [[2]]
so only for xs = [2]
yield (x:xs) = yield (1:[2]) = yield [1,2]
second, for x = 2
-- for each xs in perms (delete 2 [1,2]) = perms [1] = [[1]]
so only for xs = [1]
yield (x:xs) = yield (2:[1]) = yield [2,1]
so two values are yielded, namely [1,2] and [2,1], giving:
perm [1,2] = [[1,2],[2,1]]
This obviously generalizes to any perm [a,b] = [[a,b],[b,a]], so we can finally calculate perm [1,2,3]:
-- for each x in [1,2,3]
first, for x = 1
-- for each xs in perms (delete 1 [1,2,3]) = perms [2,3] = [[2,3],[3,2]]
first for xs = [2,3]
yield (x:xs) = yield (1:[2,3]) = yield [1,2,3]
second for xs = [3,2]
yield (x:xs) = yield [1,3,2]
second, for x = 2
-- for each xs in perms (delete 2 [1,2,3]) = [[1,3],[3,1]]
first for xs = [1,3]
yield (x:xs) = yield [2,1,3]
second for xs = [3,1]
yield (x:xs) = yield [2,3,1]
third, for x = 3
first for xs = [1,2]
yield [3,1,2]
second for xs = [2,1]
yield [3,2,1]
In all, six values are yielded, giving the list:
perms [1,2,3] = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]