程式語言入門/函式式資料結構

大多數用於實現抽象資料型別（如佇列、棧和序列）的資料結構是在命令式思維模式下設計的。它們通常假設資料是可變的，並且對記憶體的隨機訪問速度很快。

在像 ML 和 Haskell 這樣的函式式語言中，隨機訪問並非規則，而是例外。這些語言不鼓勵可變性和隨機訪問，有些語言甚至完全禁止它們。但是，我們仍然可以在這些語言中實現大多數流行的資料結構，保持與我們在命令式實現中可能找到的相同的複雜度界限。在本章的剩餘部分，我們將看到一些此類實現的示例。

棧

棧是一種抽象資料型別，它儲存一組專案。它能夠執行兩個操作：push 和 pop。push 負責將新專案新增到棧中，而 pop 則檢索最後一個插入的專案（如果有）。棧是一種 LIFO 資料結構，它是“後進先出”的縮寫。

棧可以用許多不同的方式實現。例如，在 python 中，我們可以使用內建的列表來實現它，如下所示

  class Stack:
    def create_stack(self):
      self.data = []
    def push(self, item):
      self.data.append(item)
    def pop(self)
      return self.data.pop()

由於 append 和 pop 在 python 中都是 $O(1)$，因此我們的棧實現能夠在恆定時間內執行這兩個操作 [1]。

ML 實現如下

  datatype 'a stack = Stack of ('a list)
                    | Empty
  fun push item (Stack s)         = Stack (item::s)
  fun pop (Stack (first_item::s)) = (first_item, Stack s)

這個實現與它的 python 對應實現之間存在一些值得注意的差異。首先，觀察在 push 和 pop 中如何使用模式匹配來獲取棧的內容。

兩種實現都選擇將棧的內容儲存在一個列表中。列表是 python 和 ML 中的內建型別。但是，它們在這兩種語言中的使用方式有所不同。在 ML 中，列表是代數資料型別，由一些語法糖支撐。它們可以進行模式匹配，並且有一個特殊的運算子用 :: 表示，我們稱之為 cons。cons 運算子允許我們提取列表的第一個元素（也稱為其頭部）並將新元素追加到現有列表中。空列表用 nil 表示。

另一個重要的區別出現在 pop 的實現上。SML 不鼓勵使用可變資料。為了解決這個問題，我們必須返回彈出項和操作執行後獲得的棧。這是一種在大多數函式式資料結構實現中常見的模式。使用我們的棧時，我們需要跟蹤最新的版本。例如，在 ML 提示符中，我們可以寫

  $ sml stack.sml
  - val v = Stack nil;
  val v = Stack [] : 'a stack
  - val v2 = push 2 v;
  val v2 = Stack [2] : int stack
  - pop v2;
  val it = (2,Stack []) : int * int stack
  - v2;
  val it = Stack [2] : int stack
  - val (item, v3) = pop v2;
  val item = 2 : int
  val v3 = Stack [] : int stack

由於 cons (::) 和模式匹配都是在恆定時間內完成的，因此我們 ML 實現中的 push 和 pop 也是 $O(1)$。正如我們將在本章後面看到的那樣，情況並非總是如此。函式式抽象資料型別實現比它們對應的命令式實現慢 $O(\log n)$ 或更多倍的情況並不少見。

佇列

另一個常見的資料結構是 佇列。與棧一樣，佇列是支援兩個操作的容器：push 和 pop。但是，棧提供“後進先出”（ LIFO ）訪問，而佇列是“先進先出”（ FIFO ）結構。這意味著第一個使用 push 插入佇列的專案也是第一個被 pop 返回的專案。我們再次從一個簡單的 python 實現開始我們的討論。

  class Queue:
    def __init__(self):
      self.data = []
    def push(self, item):
      self.data.append(item)
    def pop(self):
      return self.data.pop(0)

就像我們的棧示例一樣，這個第一個 python 實現使用列表來儲存入隊的專案。但是，時間複雜度比第一個示例要差得多。雖然 push 仍然是 $O(1)$，但 pop 現在是 $O(n)$，因為 .pop(0) 也是 $O(n)$。 [2]

我們可以用至少兩種方式改進我們對佇列的第一次嘗試。第一種方法是推出我們自己的列表實現，而不是使用 python 的內建列表。在這樣做時，我們可以包含指向前一個元素和下一個元素的連結，有效地實現了一種稱為 雙向連結串列 的資料結構。我們在下面展示了此新實現的程式碼

  class Node:
    def __init__(self):
      self.prev = None
      self.next = None
      self.item = None

  class Queue:
    def __init__(self):
      self.begin = Node()
      self.end = Node()
      self.begin.next = self.end
      self.end.prev = self.begin

    def push(self, item):
      new_node = Node()
      new_node.item = item
      new_node.next = self.end
      new_node.prev = self.end.prev
      new_node.next.prev = new_node
      new_node.prev.next = new_node

    def pop(self):
      popped_node = self.begin.next
      new_first = popped_node.next
      self.begin.next = new_first
      new_first.prev = self.begin
      return popped_node.item

此程式碼的漸進行為比以前的實現好得多。由於雙向連結串列，push 和 pop 現在都是 $O(1)$。但是，由於現在需要許多指標操作，該程式變得更加複雜。例如，要 push 一個新專案，我們必須操作連線節點的 4 個引用。這可能很難做到。

一個更好的方法是使用兩個 python 內建列表而不是一個。我們稱這些列表為 push_list 和 pop_list。第一個 push_list 在專案到達時儲存專案。列表 pop_list 是從其中彈出專案的列表。當 pop_list 為空時，我們只需將元素從 push_list 移動到其中即可。

  class SimplerQueue:
    def __init__(self):
      self.push_list = []
      self.pop_list = []
    def push(self, item):
      self.push_list.append(item)
    def pop(self):
      if not self.pop_list:
        while self.push_list:
          self.pop_list.append(self.push_list.pop())
      return self.pop_list.pop()

這段程式碼具有所需的漸近特性：push 和 pop 都是 $O(1)$。要了解原因，請考慮一個包含 $n$ 個 push 操作和 $n$ 個 pop 操作的序列。每個 push 都是 $O(1)$，因為它只是將元素追加到 Python 列表中。正如我們之前所見，append 操作在 Python 列表中是 $O(1)$。另一方面，pop 操作可能更昂貴，因為有時需要移動專案。但是，每個被 push 的專案最多被移動一次。因此，當 $n$ 個專案被 pop 時，pop 內部的 while 迴圈總共不會迭代超過 $n$ 次。這意味著，雖然有些 pop 操作可能稍微昂貴一些，但每個 pop 都會在所謂的攤銷常數時間內執行 攤銷分析。

使用兩個 Python 列表來獲得 $O(1)$ 複雜度的技巧在 Python 以外也有用。要了解原因，請注意 push_list 和 pop_list 都被用作堆疊。我們所做的只是將專案追加到它們的前面，並從它們的後面刪除專案。正如我們之前所見，堆疊在 ML 中很容易實現。

但在深入 ML 實現之前，我們需要稍微偏離一下。碰巧的是，為了在 ML 中實現一個高效的佇列，我們需要能夠在 $O(n)$ 時間內反轉一個列表。在第一次嘗試中，人們可能會嘗試使用以下程式碼來做到這一點

  fun reverse nil = nil
    | reverse (first_element::others) = (reverse others) @ [first_element]

但是，這段程式碼需要平方時間。問題在於用於合併兩個列表的反轉時的 @ 運算子。它需要的時間與第一個列表的大小成線性關係。由於 @ 被使用一次 per 元素，並且有 n 個元素，因此複雜度變為 $O(n^{2})$

我們可以透過引入一個第二個引數來解決這個缺陷，該引數在構建這個列表時儲存反轉後的列表。

  fun do_reverse nil    accumulator = accumulator
    | do_reverse (h::t) accumulator = do_reverse t (h::accumulator)

我們可以將上面的函式包裝在一個初始化額外引數的呼叫中，以使其擁有更好的介面

  fun reverse x = do_reverse x nil

現在我們可以在 $O(n)$ 內反轉列表，push 和 pop 可以在與我們在 Python 中看到的相同的複雜度範圍內實現。程式碼如下

  datatype 'a queue = Queue of 'a list * 'a list
  fun push item (Queue (push_list, pop_list)) =       Queue (item::push_list, pop_list)
  fun pop (Queue (push_list, first_item::pop_list)) = (first_item, Queue (push_list, pop_list))
    | pop (Queue (push_list, nil))                  = pop (Queue (nil, reverse push_list))

二叉樹

二叉搜尋樹是計算機科學中最重要的資料結構之一。它們可以以有序的方式儲存元素集合，如果我們幸運的話，可以在 O(log n) 內對這些集合進行以下操作

• 插入一個新元素
• 搜尋一個元素
• 找到最小元素

幸運是指有一些操作序列可以將這些複雜度降至 O(n)。我們將在下一節中介紹如何處理它們。值得注意的是，這僅僅是樹所能做的事情的一個子集。但是，一些操作（如刪除）可能變得相當複雜，我們在這裡不會介紹它們。

樹是由節點組成的。每個節點至少包含三個東西：它的資料和兩個子樹，我們將它們稱為左樹和右樹。左樹包含嚴格小於節點中儲存的資料的元素，而右樹包含大於它的元素。左樹和右樹本身都是樹，這導致了 ML 中以下遞迴定義

   datatype 'a tree = Leaf
                    | Node of 'a tree * 'a * 'a tree

像往常一樣，我們從三個操作的 Python 實現開始：插入、搜尋和查詢最小值。就像上面的資料型別一樣，Python 實現從樹的描述開始。

  class Tree:
    def __init__(self, left=None, data=None, right=None):
      self.left = left
      self.right = right
      self.data = data

  def insert(node, data):
    if node is None:
      return Tree(None, data, None)
    elif data < node.data:
      return TreeNode(insert(node.left, data), node.data, node.right)
    elif data > node.data:
      return TreeNode(node.left, node.data, insert(node.right, data))

  def find(node, data):
    if node is None:
      return False
    elif data < node.data:
      return find(node.left, data)
    elif data > node.data:
      return find(node.right, data)
    else:
      return True

  def find_min(node):
    if node.left:
      return find_min(node.left)
    else:
      return node.data

這段程式碼實際上比我們之前見過的例子更具函式式。請注意，樹操作是如何遞迴實現的。事實上，它們可以很容易地被翻譯成 ML。等效的 ML 程式碼如下所示。

datatype 'a tree = Node of 'a tree * 'a * 'a tree
                 | Empty

fun insert item Empty                      = Node (Empty, item, Empty)
  | insert item (Node (left, data, right)) = 
  if item < data then 
  	(Node (insert item left, data, right))
  else if item > data then
  	(Node (left, data, insert item right))
  else 
  	(Node (left, data, right))

fun find item Empty = false
  | find item (Node (left, data, right)) = 
  if item < data then 
  	find item left 
  else if item > data then
  	find item right
  else 
  	true

fun find_min (Node (Empty, data, _)) = data
  | find_min (Node (left, _, _))     = find_min left

請注意，這兩個實現非常相似。這是因為操作樹的演算法具有簡單的遞迴定義，而遞迴演算法非常適合函數語言程式設計語言。

但是，有一個重要的區別。就像堆疊實現中發生的那樣，插入後必須返回一個新的樹。呼叫者有責任跟蹤它。下面，我們展示了一個從 ML 提示符中使用上面樹的例子。

- val t = Empty;
val t = Empty : 'a tree
- val t0 = Empty;
val t0 = Empty : 'a tree
- val t1 = insert 1 t0; 
val t1 = Node (Empty,1,Empty) : int tree
- val t2 = insert 2 t1;
val t2 = Node (Empty,1,Node (Empty,2,Empty)) : int tree
- val t3 = insert 0 t2;
val t3 = Node (Node (Empty,0,Empty),1,Node (Empty,2,Empty)) : int tree
- find 0 t3;
val it = true : bool
- find 0 t1;
val it = false : bool

字典樹

上一節討論的樹實現有一個嚴重的缺點。對於某些插入序列，它會變得過深，這反過來又會將查詢和插入時間增加到 $O(n)$。要了解這一點，請考慮以下插入序列

- val t = Empty;
val t = Empty : 'a tree
- val t = insert 10 t;
val t = Node (Empty,10,Empty) : int tree
- val t = insert 9 t;
val t = Node (Node (Empty,9,Empty),10,Empty) : int tree
- val t = insert 8 t;
val t = Node (Node (Node #,9,Empty),10,Empty) : int tree
- val t = insert 7 t;
val t = Node (Node (Node #,9,Empty),10,Empty) : int tree
- val t = insert 6 t;
val t = Node (Node (Node #,9,Empty),10,Empty) : int tree
...

雖然 ML 直譯器在進行幾次插入後停止列印完整的樹，但模式很明顯。透過按順序插入節點，樹實際上變成了一個列表。每個節點只有一個子樹，即它左邊的子樹。

有很多方法可以解決這個問題。一種流行的方法是使用平衡二叉樹，例如 紅黑樹。平衡樹對插入演算法進行了一些更改，以確保插入不會使樹變得過深。但是，這些更改可能很複雜。

另一種方法是在每個節點中加入一個額外的鍵。可以證明，如果這些額外的鍵是隨機選擇的，並且我們能夠以這樣的方式編寫插入過程，使節點的額外部索引鍵始終大於其子節點的額外部索引鍵，那麼生成的樹很可能很淺。這就是所謂的 Treap。Treap 比平衡樹更容易實現。但是，仍然存在更簡單的替代方案。

第三種方法是探索鍵的特定屬性。這是我們將在本節中遵循的方法。具體來說，我們將假設儲存在節點中的項是固定大小的整數。假設這一點，我們將使用鍵的二進位制表示中的每一位來定位它在樹上的位置。這產生了稱為 字典樹 的資料結構。字典樹更容易維護，因為它們不需要平衡。

這次，我們將從 ML 實現開始。Trie 只是一個具有兩種節點型別的樹：內部節點和葉子節點。我們可以像下面這樣宣告它。

datatype trie = Node of trie * trie
              | Empty
              | Leaf

每個節點對應於鍵二進位制表示中的一個位。位的位位置由節點的深度給出。例如，根節點對應於最左邊的位，它的子節點對應於從左到右的第二個位。以 0 開頭的鍵遞迴地儲存在左子樹中。我們稱此左子樹為 low。在最左邊有 1 的鍵儲存在右邊，我們稱該子樹為 high。特殊值 Empty 用於指示特定子樹上沒有任何內容。Leaf 表示我們已到達鍵的最後一位，並且它確實存在。

由於 ML 沒有內建的按位運算，我們首先定義兩個函式來恢復數字二進位制表示中的位，並將該位設定為 1。請注意，這些操作線上性於鍵可能具有的位數上。在支援按位運算的語言中，如 C 或 Java，所有這些操作都可以實現為在 O(1) 中執行。

fun getbit n 1 = n mod 2
  | getbit n i = getbit (n div 2) (i - 1)

fun setbit n 1 = 
    if n mod 2 = 0 then n + 1 
    else n
  | setbit n i = 
    if n mod 2 = 0 then 2 * setbit (n div 2) (i-1)  
    else 2 * setbit (n div 2) (i-1) + 1

Trie 的程式碼如下。它實現了與二叉樹相同的操作，但具有一個基本優勢：由於位根據它們在樹中的深度分配給節點，並且鍵通常很小，因此樹永遠不會變得太深。事實上，它的深度從未超過 $O(\log n)$，其中 $n$ 是任何鍵可以具有的最大值。由於該屬性，所描述的操作也是 $O(\log n)$。在典型的硬體中，$\log n$ 從未超過 64。

fun do_insert item _     0 = Leaf
  | do_insert item Empty b = 
    if getbit item b = 0 then Node (do_insert item Empty (b - 1), Empty)
    else                      Node (Empty, do_insert item Empty (b - 1))
  | do_insert item (Node (low, high)) b = 
    if getbit item b = 0 then Node (do_insert item low (b - 1), high)
    else                      Node (low, do_insert item high (b - 1))
  | do_insert item Leaf b = Leaf

fun do_find item Leaf               0 = true
  | do_find item Empty              b = false
  | do_find item (Node (low, high)) b = 
    if getbit item b = 0 then do_find item low  (b - 1)
    else                      do_find item high (b - 1)

fun do_find_min Leaf                  b = 0
  | do_find_min (Node (Empty, high )) b = setbit (do_find_min high (b - 1)) b
  | do_find_min (Node (low,   _   ))  b = do_find_min low (b - 1)

這三個函式透過遍歷 Trie 並跟蹤它們當前處理的位來工作。為了使事情更輕鬆，我們可以使用以下別名，假設鍵不超過 10 位。

fun insert item t = do_insert item t 10;
fun find item t = do_find item t 10;
fun find_min t = do_find_min t 10;

使用命令提示符中的 Trie 實現與使用二叉樹一樣容易。

- val t = Empty;
val t = Empty : trie
- val t = insert 1 t;
val t = Node (Node (Node #,Empty),Empty) : trie
- val t = insert 2 t;
val t = Node (Node (Node #,Empty),Empty) : trie
- find 1 t;
val it = true : bool
- find 2 t;
val it = true : bool
- find 3 t;
val it = false : bool
- find_min t;
val it = 1 : int