list - Haskell:从后面访问列表

Question

今天我开始学习Haskell。我对函数式语言有点陌生，而且我很喜欢 Haskell。

但是，我有一个关于它的设计的问题，这让我很烦恼:从我目前的理解来看，访问列表后面的元素似乎比访问前面的元素要复杂得多(例如 xs:x，其中xs::[a] 和 x::a 似乎不可能)。

(据我所知)可以将一个列表 append 到另一个列表( xs++[a] )，但在运行时会花费更多(它需要遍历整个列表)并且它不能用于模式匹配。

为什么 Haskell 缺少这样的操作？

Answer 1

列表数据类型

data [a] = [] | a : [a]

定义如上。您只能匹配两种模式: []和 x : xs , 其中 x是头和 xs是尾部。

准备一个列表

a = 1 : 2 : []
b = 0 : a

 (:) <-- b / \  0  (:)  <-- a   / \  1  (:)     / \    2   []

simply adds a new cons cell and reuses the original list as the tail.

However, keep in mind that Haskell data structures are immutable. Appending to the tail of a list

a = 1 : 2 : []
b = a ++ [3]

 (:) <-- a      (:) <-- b / \            / \1  (:)         1  (:)   / \            / \  2   []         2  (:)                    / \                   3   []

requires building an entirely new list, because no part of the original structure can be reused.

In fact, consider

a = 0 : a
b = 0 : [ x+1 | x <- b ]

(:) <-- a (:) <-- b
/\/\
0 (:) <-- a 0 (:) <-- [ x+1 | x <- b ]
/\/\
0 (:) <-- a 1 (:) <-- [ x+1 | x <- [ x+1 | x <- b ] ]
……

你将如何获得列表的最后一个元素，或者追加到最后？

还有其他数据结构如 dequeue s 更适合基于前端和后端的访问。