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: 這在關於列表操作的章節中沒有涵蓋嗎？