2.1 作为递归 ADT 的 list

动机

List 是课程中第一种把 recursion 写进数据本身的结构。[3, 6, 4] 只列出 元素，却隐藏了算法真正使用的分解：list 要么是 empty list，要么由一个 head element 和一个本身仍是 list 的 tail 组成。处理 head 后，剩余问题就是 同一个问题在更短的 tail 上。

这个观点把两件事分开。ADT 规定建立和观察 list 的含义； representation 才决定操作会复制 array、跟随 pointer，还是共享已有存储。 Length、indexing、display 与 concatenation 等 client function 应依赖公开契约， 而不是查看 implementation 的 field。

配套 recursion tutorial 也使用相同纪律：先找 stopping test，为 end case 给出 直接答案，再保证 recursive call 的 input 真正变小。List 的 tail 正好提供这个 较小 input。

定义

Lecture 的公开接口可以写成 opaque C handle；client 看得到 declaration，却 不能检查 struct listCDT：

typedef struct listCDT *listADT;
typedef int listElementT;

listADT EmptyList(void);
int ListIsEmpty(listADT list);
listADT CreateList(listElementT head, listADT tail);
listElementT ListHead(listADT list);
listADT ListTail(listADT list);

各操作有明确 domain。EmptyList() 返回长度为零的有效 list； ListIsEmpty(list) 对每个有效 list 都有定义。CreateList(head, tail) 要求 tail 是有效有限 list，并返回非空 list。ListHead 与 ListTail 的 precondition 都是 list 非空，因为 empty list 没有 head，也没有 tail。对任何 constructed list，observer laws 是

另外两个 observation 区分 recursive cases：ListIsEmpty(EmptyList()) 为 true， 而 ListIsEmpty(CreateList(h, t)) 为 false。这些是 value-level ADT facts； interface 没有承诺 pointer-identity test，client 也不必知道 empty value 在内部 如何 encode。

因此 head 是一个元素，tail 则是一个 list。只有当 element type 本身就是 list type 时，head 才可以是一个 nested list。

Empty list 是 base case；非空 case 把 ListTail(list) 传入 recursive call， 使长度恰好减一。程序必须先测试 emptiness，才可调用两个 observer。

Recursive 与 iterative length 使用同一 invariant：

int ListLength(listADT list) {
   if (ListIsEmpty(list)) {
      return 0;
   }
   return 1 + ListLength(ListTail(list));
}

int ListLengthIterative(listADT list) {
   int count = 0;
   for (listADT cursor = list;
        !ListIsEmpty(cursor);
        cursor = ListTail(cursor)) {
      count++;
   }
   return count;
}

Recursive 版本把尚未完成的加法保存在 call frames；iterative 版本用 count 表示已处理 prefix 的长度，用 cursor 表示尚未处理的 suffix。

两个 implementation 的 correctness 都不需要查看 representation fields。 Recursive length 的 empty branch 返回 length definition 要求的零；非空 call 中，如果 recursive result 是 tail 的正确长度，加一就把 current head 计入。 Loop 则在每次 iteration 开始保持 invariant

开始时尚未 count 任何 cell；一次 iteration 使 count 加一，同时从 cursor 移去恰好一个 head，所以等式不变。当 cursor empty 时，其长度为零，invariant 就证明 count 等于原 list 长度。这也说明 cursor 必须沿 current tail 前进。

定理 / 命题

这个命题只适用于 finite、well-formed、acyclic list。任意 pointer cycle 不符合 这个 ADT contract。

Constant-time 前提非常重要：它适用于 linked representation，或任何不会在 ListTail 复制 suffix 的表示。如果每次取 tail 都复制 array suffix，同一个 recursion 仍会终止，但不再有 linear-time bound。

证明思路

先证明终止。用 list length 作为非负整数 variant。Empty branch 直接 return； 每个非空 recursive call 收到的 tail 长度少一。非负整数不可能无限严格下降， 所以从长度 $n$ 开始，恰好做 $n$ 次 tail step 后到达零。

再对 $n$ 使用 induction 证明 traversal 次数。长度为零时没有 cell，base call 不处理 node。假设长度 $n-1$ 的 tail 中每个 cell 都恰好处理一次。长度 $n$ 的 list 先处理 head 一次，再 traversal 它的 tail；由 induction hypothesis， 其余所有 cell 各处理一次，总数为 $1+(n-1)=n$，没有遗漏或重复。

在指定 RAM model 中，每个非空 frame 除 recursive call 外的成本介于两个 正常数之间，因此 $T(n)=T(n-1)+\Theta(1)$、$T(0)=\Theta(1)$，累加得 $T(n)=\Theta(n)$。Base call return 前，suffix length $n,n-1,\ldots,0$ 各有一个 live frame，所以最大 depth 是 $n+1=\Theta(n)$。这个结论描述 straightforward implementation，没有假设 compiler 会做 tail-call elimination。

例题详解

CreateList(3, CreateList(4, CreateList(5, EmptyList())))

ListLength([3, 4, 5])
= 1 + ListLength([4, 5])
= 1 + (1 + ListLength([5]))
= 1 + (1 + (1 + ListLength([])))
= 1 + (1 + (1 + 0))
= 3

NthElement 使用 zero-based index，precondition 是 0 ≤ n ≤ ListLength(list) - 1。在这个条件下，每次 observer call 都作用于非空 list，无须虚构 recoverable error policy：

listElementT NthElement(listADT list, int n) {
   if (n == 0) {
      return ListHead(list);
   }
   return NthElement(ListTail(list), n - 1);
}

NthElement([6, 9, 5, 2, 3], 3)
-> NthElement([9, 5, 2, 3], 2)
-> NthElement([5, 2, 3], 1)
-> NthElement([2, 3], 0)
-> ListHead([2, 3]) = 2

Display 用 wrapper 打印 brackets，再用 recursive helper 打印元素；只有 tail 非空时才打印 separator：

void RecDisplayList(listADT list) {
   if (!ListIsEmpty(list)) {
      printf("%d", ListHead(list));
      listADT tail = ListTail(list);
      if (!ListIsEmpty(tail)) {
         printf(", ");
      }
      RecDisplayList(tail);
   }
}

void DisplayList(listADT list) {
   printf("[");
   RecDisplayList(list);
   printf("]\n");
}

Helper 的 output contract 是：依次写出 input 的 elements，用 comma-space 分隔， 但不写 outer brackets。Empty input 不写任何内容；非空 input 先写 head，只在 后面仍有 element 时写 separator，再把剩余 sequence 交给 tail call。对 length 使用 induction，可以同时证明次序正确且没有 trailing separator；wrapper 因此 可以一致地处理 empty 与 non-empty list。

Concatenation 在 return path 重建第一个 list 的 cells，保持原顺序：

listADT ListConcat(listADT list1, listADT list2) {
   if (ListIsEmpty(list1)) {
      return list2;
   }
   return CreateList(ListHead(list1),
                     ListConcat(ListTail(list1), list2));
}

它的 abstract postcondition 是：list1 的全部 elements 按原顺序出现在前， 随后是 list2 的全部 elements，因此 result length 是两个 input lengths 之和。 Empty branch 直接满足契约；非空 branch 保留第一个 head，再对更短的 first tail 使用同一契约，unwinding 时重建较早的 heads。这个 reasoning 只依赖 ADT laws； sharing 是下面才讨论的 implementation consequence，不属于 abstract result。

CreateList(4, ListConcat([2, 6], [5, 7]))
CreateList(4, CreateList(2, ListConcat([6], [5, 7])))
CreateList(4, CreateList(2, CreateList(6, ListConcat([], [5, 7]))))
CreateList(4, CreateList(2, CreateList(6, [5, 7])))
[4, 2, 6, 5, 7]

Representation、sharing 与 ownership

Array representation 可以存储 contiguous elements 的 pointer 和 count。 Lecture 的 array-style CreateList 会 allocate 更大的 array 并复制完整 tail， 因此在 $n$-element tail 前添加 head 需要 $\Theta(n)$ time and space。Array tail 也可以作为 view，但 backing allocation 和 lifetime 必须另外跟踪。

Recursive linked representation 直接对应 ADT：

struct listCDT {
   listElementT head;
   listADT tail;
};

如果用 NULL 表示 EmptyList()，非空 CreateList 只 allocate 一个 cell， 存储 head 与已有 tail handle，因此为 constant time；三个 observers 也都是 constant time。

Sharing 改变 ownership obligation，却不改变 abstract value。在这个 interface 下应把 list 视为 immutable，否则修改 shared cell 会同时改变多个 logical lists。只要任何 handle 仍可到达一个 cell，它就必须保持 alive。Lecture interface 没有 destructor、reference counting 或 mutation policy，本节不自行 虚构。

Interface boundary。 C 按 value 传递 listADT handle。未来如果有 operation 要替换 caller 的 head handle，就必须 return 新 handle，或接收 caller-visible indirection，例如 listADT *。Source decks 没有定义 mutation 或 deletion； 本节也不假设存在这些操作。

常见错误

• 把 ListTail(list) 当成 element，而不是 list。
• 未排除 empty list 就调用 ListHead 或 ListTail。
• 用 invalid 或 negative index 调用 NthElement，再用 successful process exit 隐藏 contract violation。
• Recursive call 仍用原 list，使 length measure 没有下降。
• 未检查 representation 中 ListTail 的成本，就声称任何 traversal 都是 linear。
• 以为 concatenation 复制两个 inputs；linked 版本只重建第一条 spine，并共享 第二个 list。
• 另一个 handle 仍可到达 shared tail 时就将它释放。
• 把 return 的 list handle 误认为已经 in-place 更新 caller handle。

总结

List 的 recursive contract 是 empty，或一个 head 加上一个 list-valued tail。 这个 contract 同时给出 end case 与更小 input。对 finite、well-formed、acyclic list，沿 successive tails 的结构递归一定终止；在 constant-time observers 下，straightforward 完整 traversal 的时间和 call-stack depth 都是 linear。NthElement、display 与 concatenation 都遵循同一结构；ADT 决定含义，representation 则决定 copying、sharing、成本与 lifetime obligation。

练习

1. 说明 DisplayList 的 recursive idea：print head，再 display tail。
2. 解释为什么 ListConcat(list1, list2) 在 list1 empty 时应该 return list2。
3. 比较 array representation 和 linked representation 下 CreateList 的成本。

解答