[Haskell-beginners] Missing termination rule for recursive function

[Oscar Benjamin]

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.

Thanks for your help.


Oscar