Haskell:从后面访问列表

Question

今天我开始学习Haskell.我是函数式语言的新手,我很喜欢Haskell.

然而,我有一个关于它的设计的问题,这让我烦恼:从我到目前为止所理解的看起来像访问列表后面的元素看起来要复杂得多,因为访问元素到前面(类似于xs:x哪里xs::[a]和x::a似乎不可能).

(根据我的理解)可以将列表附加到另一个(xs++[a]),但它在运行时会花费更多(它需要遍历整个列表)并且它不能用于模式匹配.

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

Answer 1

列表数据类型

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

定义如上.这里只有两种模式,你可以搭配:[]和x : xs,其中x是头xs是尾.

在列表前面

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

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

只需添加一个新的cons单元格并重新使用原始列表作为尾部.

但是,请记住,Haskell数据结构是不可变的.附加到列表的尾部

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

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

需要构建一个全新的列表,因为原始结构的任何部分都不能重用.

实际上,考虑一下

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

Answer 2

Haskell中的列表数据类型是链表,因此查找使用O(n)时间.如果您需要频繁访问列表的后面,您可能需要查看Data.Sequence ,其中O(1)添加到开头和结尾.

要回答为什么Haskell将此数据结构用作"标准容器"(如C和数组),这是因为Haskell是一种纯函数式语言,因此优先选择纯函数式数据结构(不可变和持久性).在这个维基页面.要在Haskell中使用非功能性数据结构,需要将其放在orad IO或STmonad中.