Empty list generators

Question

How list generators are handled by Haskell? Specifically, why does this

f n = [x:xs | x <- [1..n], xs <- []]

yields empty list? What is xs in x:xs in every 'iteration'?

There is no answer to "What is `xs` in `x:xs` in every 'iteration'?" because there are no "iterations" of `x:xs`. Meditate on this expression: `[undefined | _ <- []] == []`. — Chris Martin, Dec 12 '16 at 02:42
@duplode gave a great answer regarding why it doesn't work. But I assume, you wanted to create lists of lists each containing a single element; which you can do with `f n = [x:xs | x <- [1..n], xs <- [[]] ]` — zeronone, Dec 12 '16 at 07:10
That creates single-element lists, but why would you do it that way? Just `f n = [[x] | x <- [1..n]]`, or `f n = map pure [1..n]`. — amalloy, Dec 12 '16 at 17:19

duplode · Accepted Answer · 2018-03-05T18:04:52.360

The zoomed-out answer is that...

[x:xs | x <- [1..n], xs <- []]

... consists of all possible lists generated by picking an element (x) from [1..n] plus an element (xs) from [] and prepending one to the other. Since there are no elements in [], the number of lists that can be generated in this way is zero.

The zoomed-in answer is that list comprehensions are sugar for the list monad, and so this...

[x:xs | x <- [1..n], xs <- []]

... is equivalent to...

do
    x <- [1..n]
    xs <- []
    return (x:xs)

... that is (after desugaring do-notation)...

[1..n] >>= \x ->
[] >>= \xs ->
return (x:xs)

-- Or, without the line breaks:
[1..n] >>= \x -> [] >>= \xs -> return (x:xs)

... that is (after substituting the definitions of (>>=) and return for the list monad):

concatMap (\x -> concatMap (\xs -> [x:xs]) []) [1..n]

concatMap (which, as the name suggests, is merely map followed by concat) on an empty list gives an empty list, and so it becomes...

concatMap (\x -> []) [1..n]

... which amounts to replacing each element of [1..n] with an empty list and then concat-ing the result, which produces an empty list.

Empty list generators

1 Answers1