Как haskell создает новый список из другого списка?

Question

Предположим, у нас есть список

x = [1..10] 

и мы намерены создать еще один список у, используя это таким образом:

y= [a|a<-x] 

Так, при создании списка y из x, он обращается к каждому элементу x (от 1 до 10) и вставляет его в y в том же порядке. Поскольку список в haskell является односвязным списком, мы можем вставить новый элемент только в его голове. Итак, сначала он вставляет 1 в [] & у нас есть [1]. Затем он вставляет 2 в голову &, поэтому у нас есть [2,1]. Затем он вставляет 3 & у нас есть [3,2,1] & и так далее. Поэтому в конечном итоге мы должны получить y как [10,9..1]. Но вместо этого мы получаем y как [1..10]. Почему это так?

Answer 1

Потому что он «вставляет» их в хвост списка в (пока список строится), не головой (ср «хвост рекурсии по модулю против»):

[a | a <- [1..10]]  == 
[a | a <- (1:[2..10])] ==  -- [a | a <- ([1] ++ [2..10])] 
1 : [a | a <- [2..10]]   -- [1] ++ [a | a <- [2..10]] 

Это потому, что

[a | a <- (xs ++ ys)] == [a | a <- xs] ++ [a | a <- ys] 

и

[a | a <- ys] == ys 

Answer 2

, как вы думаете о списке компе привязки не совсем корректны. Когда вы видите, осознание

y <- [f a | a <- x] 

вы не должны думать о последовательном результате добавляются к передней части (первоначально пустой) списка результатов.

Вместо этого подумайте о том, что каждый из f a добавлен в начало результата выполнения списка на остальной части x. То есть,

[f a | a <- x:xs] == f x : [f a | a <- xs] 

Это рекурсивный подход - если предположить, что список результатов существует для хвоста списка, вы можете добавить следующий результат перед ним.

Answer 3

Поучительно взглянуть на то, как именно восприятие списков desugar на монадические вычисления, а не использовать интуицию в отношении того, как они работают.

[a | a <- [1..3]] == do {a <- [1..3]; return a} -- desugared comprehension 
        == [1..3] >>= return a   -- desugared do 
        == concat (map return [1..3]) -- definition of >>= 
        == concat [[1], [2], [3]]  -- defintiion of return 
        == [1,2,3]      -- definition of concat