08 演算法

第八章：實作進階演算法

在 Lambda Calculus 的基礎上，進一步探索如何實作進階演算法能幫助我們深刻理解遞迴與函數應用的威力。本章將涵蓋幾個經典演算法的 Lambda Calculus 定義，以及 Python 中的模擬實作。

---

8.1 費波那契數列

費波那契數列是遞迴演算法的典型例子。其定義如下： [ F(n) = \begin{cases} 0 & \text{if } n = 0 \ 1 & \text{if } n = 1 \ F(n-1) + F(n-2) & \text{if } n > 1 \end{cases} ]

Lambda Calculus 定義：

FIB = Y(lambda f: lambda n:
    IF(IS_ZERO(n))
    (lambda _: _zero)
    (lambda _: IF(IS_EQUAL(n)(_one))
        (lambda _: _one)
        (lambda _: ADDITION(f(PREDECESSOR(n)))(f(PREDECESSOR(PREDECESSOR(n)))))
    )
)

測試：

assert FIB(_zero) == _zero
assert FIB(_one) == _one
assert FIB(_five) == _five  # F(5) = 5

---

8.2 階乘

階乘演算法可以用遞迴定義： [ n! = \begin{cases} 1 & \text{if } n = 0 \ n \times (n-1)! & \text{if } n > 0 \end{cases} ]

Lambda Calculus 定義：

FACTORIAL = Y(lambda f: lambda n:
    IF(IS_ZERO(n))
    (lambda _: _one)
    (lambda _: MULTIPLICATION(n)(f(PREDECESSOR(n))))
)

測試：

assert FACTORIAL(_three) == MULTIPLICATION(_three)(MULTIPLICATION(_two)(_one))  # 3! = 6

---

8.3 最大公因數（GCD）

最大公因數可用歐幾里得算法計算，其遞迴定義為： [ \text{GCD}(a, b) = \begin{cases} a & \text{if } b = 0 \ \text{GCD}(b, a \mod b) & \text{if } b > 0 \end{cases} ]

Lambda Calculus 定義：

GCD = Y(lambda f: lambda a: lambda b:
    IF(IS_ZERO(b))
    (lambda _: a)
    (lambda _: f(b)(MOD(a)(b)))
)

測試：

assert GCD(_eight)(_twelve) == _four  # GCD(8, 12) = 4

---

8.4 合計範圍內的數字（Sum Range）

合計範圍內數字是一個經典的遞迴範例，目標是計算從 (m) 到 (n) 的所有數字總和： [ \text{SUM_RANGE}(m, n) = \begin{cases} 0 & \text{if } m > n \ m + \text{SUM_RANGE}(m+1, n) & \text{if } m \leq n \end{cases} ]

Lambda Calculus 定義：

SUM_RANGE = Y(lambda f: lambda m: lambda n:
    IF(IS_GREATER(m)(n))
    (lambda _: _zero)
    (lambda _: ADDITION(m)(f(SUCCESSOR(m))(n)))
)

測試：

assert SUM_RANGE(_two)(_four) == ADDITION(_two)(ADDITION(_three)(_four))  # 2 + 3 + 4 = 9

---

8.5 合併排序（Merge Sort）

合併排序是一種經典的分治演算法，適用於排序列表。其步驟如下：

1. 將列表分割為兩部分。
2. 遞迴排序兩部分。
3. 合併排序後的子列表。

Lambda Calculus 定義：

MERGE_SORT = Y(lambda f: lambda lst:
    IF(IS_NULL(lst) OR IS_NULL(CDR(lst)))
    (lambda _: lst)  # 單個元素或空列表視為已排序
    (lambda _: 
        LET(split_result = SPLIT(lst))(
            lambda _: MERGE(
                f(CAR(split_result))  # 遞迴排序左半部分
            )(f(CDR(split_result)))  # 遞迴排序右半部分
        )
    )
)

Python 提示：分割與合併邏輯需要額外實作，類似於列表操作章節中的方法。

---

8.6 本章小結

本章展示了 Lambda Calculus 如何以純函數方式實現經典的進階演算法，並透過 Python 模擬其邏輯。我們學習了從簡單的費波那契數列到合併排序的多種演算法，並深入了解遞迴與條件分支的應用。

下一章將探討 Lambda Calculus 與現代計算理論的聯繫，並展示如何將這些知識應用於更實際的計算模型中。