Haskell/分层库/列表

List 数据类型（参见 Data.List）是 Haskell 中的基本数据结构——这是数据存储和操作的基本构建块。在计算机科学术语中，它是一个单链表。在分层库系统中，List 模块存储在 Data.List 中；但是，这个模块只包含实用程序函数。列表本身的定义是 Haskell 语言不可分割的一部分。

理论

单链表是一组按定义顺序排列的值。列表只能单向遍历（即，您不能像磁带盒中的磁带一样在列表中来回移动）。

前 5 个正整数的列表写成

[ 1, 2, 3, 4, 5 ]

我们可以从左到右遍历这个列表，检查和更改值，但不能反过来。这意味着列表

[ 5, 4, 3, 2, 1 ]

不仅仅是之前列表的视角上的微不足道的改变，而是大量计算的结果（在列表长度上为O(n)）。

定义

多态列表数据类型可以用以下递归定义来定义

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

这个定义的“基本情况”是[]，空列表。为了将某些东西放入这个列表中，我们使用(:) 构造函数

emptyList = []
oneElem = 1:[]

(:)（发音为cons）是右结合的，因此创建多元素列表可以像这样完成

manyElems = 1:2:3:4:5:[]

或者甚至只是

manyElems' = [1,2,3,4,5]

基本列表用法

前置

使用 cons 以外的方法很容易硬编码列表，但运行时列表创建将使用 cons。例如，要将一个参数压入模拟栈，我们会使用

push :: Arg -> [Arg] -> [Arg]
push arg stack = arg:stack

模式匹配

如果我们想要检查栈顶，我们通常会使用一个 peek 函数。我们可以尝试模式匹配来实现这一点。

peek :: [Arg] -> Maybe Arg
peek [] = Nothing
peek (a:as) = Just a

模式中cons之前的a匹配列表的头部。as匹配列表的尾部。由于我们实际上并不想要尾部（并且它在代码中的其他任何地方都没有被引用），我们可以明确地告诉编译器这一点，使用通配符匹配，形式为下划线

peek (a:_) = Just a

列表实用程序

FIXME: 这在关于列表操作的章节中没有涵盖吗？