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

因为它 "inserts" 它们在列表的尾部 （在构建列表时）， 而不是头部（参见 "tail recursion modulo cons"）：

[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

了解列表推导式如何对单子计算进行脱糖是很有启发性的，而不是凭直觉了解它们的工作原理。

[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

haskell 如何从另一个列表创建新列表？

How does haskell create a new list from another list?

haskell

list-comprehension

list

lazy-evaluation