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 更适合基于前端和后端的访问。