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

Question

假设我们有一个清单

x = [1..10]

我们打算用这种方式创建另一个列表y:

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

因为它在列表的尾部"插入"它们(在构建列表时),而不是head(参见"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]

这是一种递归方法 - 通过假设列表尾部存在结果列表,您可以将下一个结果添加到其前面.