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 的成本。

解答