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