05.3 柯里化與指數律在型別中的體現#

curry   :: ((a, b) -> c) -> a -> b -> c
curry f x y = f (x, y)

uncurry :: (a -> b -> c) -> ((a, b) -> c)
uncurry f (x, y) = f x y

-- 互逆性的驗證（自由定理保證這對任意 f 成立）：
-- unurry . curry = id  且  curry . uncurry = id

from typing import Callable, Tuple

def curry[A, B, C](f: Callable[[Tuple[A, B]], C]) -> Callable[[A], Callable[[B], C]]:
    return lambda x: lambda y: f((x, y))

def uncurry[A, B, C](f: Callable[[A], Callable[[B], C]]) -> Callable[[Tuple[A, B]], C]:
    def g(p: Tuple[A, B]) -> C:
        return f(p[0])(p[1])
    return g

def f_pair(p: Tuple[int, int]) -> int:
    return p[0] * 10 + p[1]

def f_cur(x: int) -> Callable[[int], int]:
    return lambda y: x * 10 + y

# 互逆驗證
for x, y in [(1, 2), (3, 4), (0, 9)]:
    assert uncurry(curry(f_pair))((x, y)) == f_pair((x, y))
    assert curry(uncurry(f_cur))(x)(y) == f_cur(x)(y)
print("柯里化同構驗證通過")

add :: Int -> Int -> Int
add x y = x + y

inc :: Int -> Int
inc = add 1            -- 固定第一參數：C^1 特化自 C^2

-- 運算子區段（section）同樣是柯里化的直接受益者
double = (* 2)
halve  = (/ 2)

map (add 10) [1, 2, 3]   -- [11, 12, 13]

from functools import partial

def scale(factor: float, value: float) -> float:
    return factor * value

double = partial(scale, 2.0)   # Python 需要庫函數輔助，因為函數預設不柯里化
assert double(21) == 42.0

// Rust 函數天然是多參數的（非柯里化），但閉包語法輕鬆手動柯里化
let add = |x: i32, y: i32| x + y;
let add10 = move |y| add(10, y);   // 部分應用 = 閉包捕獲
assert_eq!(add10(5), 15);

volume :: Double -> Double -> Double -> Double
volume w h d = w * h * d
-- 其型別等價於：(Double, Double, Double) -> Double
--   因為  ((a,b),c) ≅ (a,(b,c)) ≅ (a,b,c)   （積的結合律）
-- 於是  a -> b -> c -> r ≅ (a×b×c) -> r   （指數律 + 結合律）

# 當定義域夠小，真值表表示法是可行的（也更快！）
from functools import lru_cache

# Bool->Bool 的四個函數中，not 是唯一「非平凡」的：
truth_table = {False: True, True: False}          # 真值表即映射，O(1) 求值
assert truth_table[False] is True

# u8->u8 有 256^256 個函數：只能存「描述」（演算法）
@lru_cache(maxsize=None)
def f(x: int) -> int:
    return (x * 7 + 3) % 256
# 教訓：基數決定表示法。小定義域→查表；大定義域→演算法+記憶化

-- 律 1 的程式證明：處理 A+B 的函數 = 兩個函數的配對
fanOut :: (Either a b -> c) -> (a -> c, b -> c)
fanOut f = (f . Left, f . Right)

fanIn  :: (a -> c, b -> c) -> Either a b -> c
fanIn (g, _) (Left x)  = g x
fanIn (_, h) (Right y) = h y

-- fanOut . fanIn = id 且 fanIn . fanOut = id
-- 「case 分析」與「函數配對」是同一件事——又是邏輯規則的代數化

# 驗證指數半環三律（在小型有限型別上窮舉）
from itertools import product

def fn_type(dom, cod):
    """列出 dom -> cod 的全部函數（以 tuple 編碼：真值表）"""
    return tuple(tuple(dict(zip(dom, vals))[x] for x in dom)
                 for vals in product(cod, repeat=len(dom)))

Nat2 = (0, 1)          # |A| = 2
Nat3 = (0, 1, 2)       # |C| = 3

# 律 3: C^(A×1) ≅ C^A
# 律 2（柯里化）: |(C^A)^B| = (|C|^|A|)^|B| = |C|^(|A|·|B|)
lhs = len(fn_type(Nat2, fn_type(Nat2, Nat3)))    # (3^2)^2 = 81
rhs = len(fn_type((0,1,0,1), Nat3))              # 3^4     = 81  (A×B 有 4 個值)
assert lhs == rhs == 81
print("柯里化 = 指數律，在有限型別上窮舉驗證成立")