Permutations in Haskell involving List Comprehensions, Recursion and the delete function

user_11350356 0
Viewed 449

I'm a Haskell beginner following exercises from a book. The first question asked me to define a function that deletes the first occurrence of an integer from a list of integers.

E.g. 

delete 5 [1,5,3,5,1]

outputs:

[1,3,5,1]

The second question asks me to create a function that uses the delete function I just defined, that takes as an argument a list of integers, and outputs a list of all the permutations as lists.

E.g.

perms [1,2,3]

outputs:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

I tried hard, gave up and googled the solution.

Here's what I found:

perms [] = [[]]
perms xs = [ i:j | i <- xs, j <- perms $ delete i xs ]

I looked around and found many other similar solutions, almost identical, just using different variable names and parentheses instead of the $ symbol, so I'm guessing this is a common problem with an idiomatic solution.

I'm just a little lost trying to understand exactly what this code is doing. I am seeking a step by step explanation through the recursion, to understand how this code is creating a list of permutations?

permutation recursion list-comprehension haskell
2 Answers

Like any recursive function that operates on lists, this one can be broken down into two cases:

1) What should the function do on an empty list?

2) If I know what the function does on a list of length n, can I use that to figure out what the function should do on a list of length n + 1.

Once you know those two things, you have a definition that will work on any list (at least one of finite length - such a procedure will of course never end for one of infinite length; that doesn't matter here as it doesn't make much sense to talk about permutations from an infinite list). [If you have any sort of mathematical background, you will recognise this as a simple statement of the law of mathematical induction.]

For the perms function, it is clear that there is only one way to permute the 0 elements of the empty list: another empty list. This gives [[]] for the base case, as in the first line of the example solution.

For the recursive/inductive step, let's say we have a list xs of length n (where n > 0), and suppose (as we are allowed to) that we already know how to compute all permutations of any list of length n - 1.

Each permutation must start with a particular element of the xs - let's call this element i, and think about how to get all the permutations of xs whose first element is i. It should be clear that these correspond precisely with all permutations of the list delete i xs (that is, xs with one i removed) - given a permutation j of the latter, the list i : j is a permutation of xs which begins with i, and conversely all such permutations of xs can be obtained in that way.

Note that this is exactly the list [ i:j | j <- perms $ delete i xs ]

(And note in passing that, since we've assumed i is in xs, delete i xs indeed has length n - 1, so by the inductive hypothesis we know how to compute this.)

i of course was chosen completely arbitrarily there - and all elements of xs will need to be accounted for as the first element of some permutations. So we simply put together all of the above, for all elements i in xs - which is exactly what the expression in the recursive step is:

[ i:j | i <- xs, j <- perms $ delete i xs ]

You might need to read some of the above slowly, a few times, before it makes sense - but it is fundamentally very elementary logic (and like most elementary logic, has a nasty habit of often looking more complicated than it actually is).

user_84750540
  • One by one take a single element i from xs
  • Delete i from xs and prepend i to j (every list element of the perms of xs less i) up until all is are depleted.
user_45432070
Related