List comprehensions -require base case?

I don't understand why the base case is needed in this:

-- perms :: Ord a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ (x:ps) | x <- xs, ps <- perms (xs \\ [x])]

It seems to me that it should be automatic from the list-comprehension, but then I noticed that:

[ x:y | x<-[], y<-[] ]

evaluates to [], and not [[]], which seems surprising.

开发者_JAVA百科Even so, I was also surprised that without the base case it runs, but always gives [], which violates the type signature. Is there an easy way to trace the execution of a list comprehension? It seems atomic to Debug.Trace.trace.

---

You can think of <- as use every element from the list in right in the expression in left. Since [] has no elements the whole list comprehension returns an empty list. It will be strange if [ x:y | x<-[], y<-[] ] returns [[]] because : takes element and a list. So to generate [[]] y must be [] but then what will be x?

As KennyTM said [] is of type [[a]]. Actually [] is from every type of this kind: [a] [[a]] [[[a]]] and so on. If it wasn't then there is no way a function to return an empty list.

Anyway it is a very common mistake to forget some brackets and this is why type annotations are necessary.

---

Let's de-sugar!

[ x:y | x <- [], y <- [] ]

Turns into

do x <- []
   y <- []
   return (x:y)

Now, more de-sugaring! Yay!

[] >>= \x -> ([] >>= \y -> return (x:y))

iirc, >>= for lists is flip concatMap, and return is simply \x -> [x]

Let's only do a little bit of that replacement.

concatMap (\x -> ([] >>= \y -> return (x:y))) []

There, now do you see? concatMap f [] will obviously evaluate to []. Because concatMap f is just concat . map f. So map f onto the empty list, and then concatenate the results. Except there are no results, so the final evaluation is [].

---

So it comes down to the meaning of

[ x:y | x<-[], y<-[] ]

The way to read this is, "What are the possible values of x:y, when x has no possible values, and y has no possible values?" Hopefully, it should be clear that in that case, there are no values at all for x:y, since you'd need a value for x and a value for y to get a possibility for x:y, and you have neither.

This general pattern of selecting combinations of possible values for x and y is called a cartesian product, and the word "product" is used in part because the number of possibile combinations is equal to the number of possibilities for x, times the number of possibilities for y. So if there are zero choices for x, and zero choices for y, you can expect 0 * 0 = 0 choices for combinations of the two.

---

Here's another hint why there is a base case with an empty list. How many permutations are there of n elements? There are n! permutations. And what is 0!? It's 1. So the length of the result list for perm [] has to be 1. The types and the lack of elements of type a forces the result to be [[]]. No other defined value has the right type and length.

---

If you have a list comprehension of the form:

[ x:y | stuff ]

then you are producing a list whose elements are of the form x:y for some choices of x and y as determined by stuff. [[]] is a list whose elements are not of the form x:y for any x or y, so the former cannot produce the latter.

In expecting [[]] from [ x:y | x <- [], y <- [] ], you seem to be setting x = [] and y = [] and then considering x:y = [[]]. This is wrong for a couple of reasons:

• x is coming from xs of type [a], so x has type a, and is not (in general) a list
• the result of the list comprehension is a list of x:y elements, not a single one.