The recursive permutation function always returns an empty list

Question

I am studying Haskell, and one of my practical functions was a simple recursive permute . I adapted the solution described here and initially got the following:

 selections [] = [] selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ] permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

(Yes, it may be shorter, but I was going to explain clarity as well.)

However, this permute version always returned an empty list! Having twisted a little, I made it work by changing permute to:

 permute [] = [[]] permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

However, I am still puzzled by why the original version always returns an empty list .

Answer 1

Well, they are obviously very similar, so why not look in detail where they disagree? The recursive part is the same in both cases, so at first we can say that both versions do the same in non-empty lists. This doesn’t sound right, because they give different results, but actually it’s true, because they perform the same operation as a result of a recursive call.

The base register is from the correct version permute [] = [[]] , which goes without saying. However, the base case from the first version is implicit in the list comprehension. Given the definition:

 permute xs = [y:ps | (y,ys) <- selections xs, ps <- permute ys] 

... we can replace in [] with xs to see what happens:

 permute [] = [y:ps | (y,ys) <- selections [], ps <- permute ys] 

Given the definition of selections [] = [] , we can simplify:

 permute [] = [y:ps | (y,ys) <- [], ps <- permute ys] 

... from which it is clear that no results are generated, so a complete understanding of the list is empty, simplification down to simple:

 permute [] = [] 

Now consider the last recursive step in front of the base, replacing [x] as an argument:

 permute [x] = [y:ps | (y,ys) <- selections [x], ps <- permute ys] 

The definition of selections is selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ] selections (x:xs) = (x, xs) : [ (y, x:ys) | (y,ys) <- selections xs ] , substituting in the [x] expression selections [x] = (x, []) : [ (y, x:ys) | (y,ys) <- selections [] ] selections [x] = (x, []) : [ (y, x:ys) | (y,ys) <- selections [] ] . selections [] evaluates to [] , so a complete understanding of the list comes down to [] , giving selections [x] = (x, []) : [] or just selections [x] = [(x, [])] .

Replace this with permute as above:

 permute [x] = [y:ps | (y,ys) <- [(x, [])], ps <- permute ys] 

There is only one element in the list, so we can ignore the binding and substitution <- directly:

 permute [x] = [y:ps | (y,ys) = (x, []), ps <- permute ys] permute [x] = [ x:ps | ps <- permute []] 

Having established that permute [] evaluates to [] , we can also replace this and find that understanding the list again comes down to [] :

 permute [x] = [] 

... which easily generalizes to return [] for any input. However, the working version uses the following definition:

 permute [] = [[]] 

In the final reduction of the final recursive step, this replaces the replacements with the following:

 permute [x] = [ x:ps | ps <- permute []] permute [x] = [ x:ps | ps <- [[]] ] 

Since ps tied to just one element, we can again directly replace:

 permute [x] = (x:[]) 

It just says permute [x] = [x] .