Re: [Haskell-beginners] Missing termination rule for recursive function

On 5 November 2012 21:27, Jay Sulzberger wrote:

On Mon, 5 Nov 2012, Oscar Benjamin 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