# [Haskell-beginners] Missing termination rule for recursive function

Oscar Benjamin oscar.j.benjamin at gmail.com
Tue Nov 6 00:57:14 CET 2012

```On 5 November 2012 21:27, Jay Sulzberger <jays at panix.com> wrote:
> On Mon, 5 Nov 2012, Oscar Benjamin <oscar.j.benjamin at gmail.com> wrote:
>
>> -- Select each item and remainder from a sequence
>> selections :: [a] -> [(a, [a])]
>> selections []     = []
>> selections (x:xs) = (x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]
>>
>> -- Permutations of a sequence
>> permutations :: [a] -> [[a]]
>> permutations xs = [ y:zs | (y,ys) <- selections xs, zs <- permutations ys
>> ]
>>
>
> Assuming selections is correct, we have
>
>   permutations ["a"] ~> the list of all lists of form "a":(something that
> lies in permutations [])
>
> So what is the value of permutations []?  It is the list of all things of
> form
>
>   y:zs
>
>   such that
>
>   (y,ys) lies in selections xs and zs lies in permutations ys

When you rephrase in set terminology like this it becomes easier to
understand. I was thinking of it all in terms of loops before.

> where xs = [].  But there are no such things.  And so the list of
> sll such things is the empty list [].
>
> What is perhaps confusing is that, at this juncture, one tends to
> think that
>
>   y:zs
>
> must really be
>
>   y:[]
>
> but it is not.

That's exactly what confused me. It doesn't confuse me when it's laid
out like this but in the list comprehension it did.