Permutation Algorithm in Haskell

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