编程语言简介/列表成本模型
< 编程语言简介
列表可能是函数式编程语言中最著名的数据结构。函数式列表为用户提供了两个众所周知的操作：头和尾。前者返回列表的第一个元素。后者返回对列表尾部的引用，即包含原始序列中所有元素的子列表，但第一个元素除外。仅使用这两个操作，我们无法进行随机访问，即无法以相同的时间成本读取列表中的任何元素。为了说明这一点，让我们考虑一下下面这个谓词的实现，它允许我们连接列表
@([], L, L).
@([H|T], L, [H|Tt]) :- @(T, L, Tt).
这个谓词由两个子句组成。第一个显然是 O(1)，因为它总是为真。另一方面，第二个涉及递归。对于第一个列表上的每个元素，谓词将被递归调用一次。每个递归调用执行 O(1) 量的计算。因此，这个谓词对于第一个列表的元素数量是线性的。请注意，我们谈论的是元素的数量，而不是元素的大小。换句话说，无论第一个列表包含什么，谓词都应该在相同的时间内运行。再举一个例子，这次让我们分析一个对反转列表的谓词的简单实现
reverse([],[]).
reverse([Head|Tail],Rev) :- reverse(Tail,TailRev), @(TailRev,[Head],Rev).
有人可能会认为这个谓词对我们要反转的列表的大小是线性的：第一个子句在 O(1) 内运行，第二个子句递归调用一次 reverse。但是，每次调用 reverse 的成本并非 O(1)。除了最后一次调用之外，每次调用都使用了我们的 append，我们已经知道它是 O(N)，N 是第一个列表的元素数量。因此，我们目前实现的 reverse 对列表元素的数量是二次的。鉴于在 C、Python 或 Java 中，以线性时间反转数组是如此容易，我们可能会想知道是否可以在函数式列表的成本模型上实现相同的复杂度。的确，这是可能的，我们很快就会证明这一点。现在，我们将把这个问题放到我们的堆栈中。