haskell如何從另一個列表創建一個新列表？

Question

假設我們有一個列表

x = [1..10] 

，我們打算以這種方式使用它來創建另一個列表Y：

y= [a|a<-x] 

因此，儘管從x創建列表y，它訪問的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

你在考慮名單補償方式rehensions並不完全正確。當你看到理解

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

你不應該考慮將連續結果添加到（最初是空的）結果列表的前面。

取而代之的是，將每個f a添加到對x的其餘部分運行列表理解的結果的前面。也就是說，

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

這是一個遞歸的方法 - 通過假設存在列表的尾部結果列表，你可以下一個結果添加到它的前面。

Answer 3

查看列表解析是如何解釋一元計算的，而不是直覺地使用它們的工作方式。

[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