编程语言入门/函数式数据结构

大多数用于实现抽象数据类型（如队列、栈和序列）的数据结构是在命令式思维模式下设计的。它们通常假设数据是可变的，并且对内存的随机访问速度很快。

在像 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