Генераторы пустых списков

Question

Как генераторы списков обрабатываются Haskell? В частности, почему это

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

дает пустой список? Что такое xs в x:xs на каждой итерации?

Answer 1

Увеличиваемый из ответа является то, что ...

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

... состоит из всех возможных списков, полученных путем выбора элемента (x) от [1..n] плюс элемент (xs) от [] и предваряя один к другому. Поскольку в [] нет элементов, количество списков, которые могут быть сгенерированы таким образом, равно нулю.

Увеличиваемую в ответ, что list comprehensions are sugar for the list monad, и поэтому это ...

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

... эквивалентно ...

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

... что (после desugaring делать-обозначения) ...

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

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

... что (после подстановки определений (>>=) и return для списка монады):

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

concatMap (который, как следует из названия, это просто map с последующим concat) на пустой список дает пустой список, и поэтому он становится ...

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

... который заменяет каждый элемент [1..n] пустым списком, а затем concat -получает результат, который создает пустой список.