第3章 元组与不可变序列理论
本章导读
元组是Python中实现不可变序列的核心数据结构。本章从类型理论和函数式编程角度深入分析元组的理论基础，包括乘积类型的数学定义、不可变性的语义保证、可哈希性的形式化条件，以及命名元组的代数规范。
学习目标
完成本章学习后，读者将能够：
- 理解元组作为乘积类型的数学本质
- 掌握不可变性的语义保证与形式化定义
- 理解可哈希性的数学条件与哈希函数设计
- 应用势能方法分析不可变数据结构的性能
- 掌握命名元组的代数规范与类型推导
3.1 元组的类型理论基础
3.1.1 乘积类型的数学定义
定义 3.1（乘积类型） 给定类型 $T_1, T_2, \ldots, T_n$，它们的乘积类型 $T_1 \times T_2 \times \cdots \times T_n$ 是所有形如 $(v_1, v_2, \ldots, v_n)$ 的 $n$-元组的集合，其中 $v_i \in T_i$。
定义 3.2（元组的基数） 设类型 $T_1, T_2, \ldots, T_n$ 的基数分别为 $|T_1|, |T_2|, \ldots, |T_n|$，则乘积类型的基数为：
$$|T_1 \times T_2 \times \cdots \times T_n| = \prod_{i=1}^{n} |T_i|$$
定理 3.1（元组的同构性） 对于任意类型 $A, B, C$，有：
- $(A \times B) \times C \cong A \times (B \times C) \cong A \times B \times C$（结合律）
- $A \times B \cong B \times A$（交换律，但语义不同）
- $A \times 1 \cong A$，其中 $1$ 是单元类型
证明：通过构造双射证明。
定义 $f: (A \times B) \times C \to A \times B \times C$ 为 $f((a, b), c) = (a, b, c)$，其逆为 $f^{-1}(a, b, c) = ((a, b), c)$。显然 $f$ 是双射。
定义 $g: A \times B \to B \times A$ 为 $g(a, b) = (b, a)$，其逆为 $g^{-1}(b, a) = (a, b)$。
定义 $h: A \times 1 \to A$ 为 $h(a, ()) = a$，其逆为 $h^{-1}(a) = (a, ())$。
∎
3.1.2 元组ADT规范
ADT 3.1（Tuple）
ADT Tuple[T₁, T₂, ..., Tₙ]
Types: Tuple[T₁, T₂, ..., Tₙ]
Operations:
tuple: T₁ × T₂ × ... × Tₙ → Tuple[T₁, T₂, ..., Tₙ]
fst: Tuple[T₁, T₂, ..., Tₙ] → T₁
snd: Tuple[T₁, T₂, ..., Tₙ] → T₂
get: Tuple[T₁, T₂, ..., Tₙ] × ℕ → Tᵢ
size: Tuple[T₁, T₂, ..., Tₙ] → ℕ
concat: Tuple[T₁, ..., Tₘ] × Tuple[Tₘ₊₁, ..., Tₙ] → Tuple[T₁, ..., Tₙ]
Axioms:
∀t: Tuple[T₁, T₂, ..., Tₙ], ∀i: ℕ, 1 ≤ i ≤ n
(A1) get(tuple(v₁, v₂, ..., vₙ), i) = vᵢ
(A2) size(tuple(v₁, v₂, ..., vₙ)) = n
(A3) fst(tuple(v₁, v₂, ..., vₙ)) = v₁
(A4) snd(tuple(v₁, v₂, ..., vₙ)) = v₂
(A5) concat(tuple(a₁, ..., aₘ), tuple(b₁, ..., bₖ)) = tuple(a₁, ..., aₘ, b₁, ..., bₖ)定理 3.2（元组ADT的一致性） 元组ADT的公理系统是一致的。
证明：构造具体模型。设元组为索引函数 $t: {1, 2, \ldots, n} \to \bigcup_{i=1}^{n} T_i$，满足 $t(i) \in T_i$。
- $tuple(v_1, \ldots, v_n) = \lambda i. v_i$
- $get(t, i) = t(i)$
- $size(t) = n$
可直接验证所有公理成立。∎
3.1.3 不可变性的形式化定义
定义 3.3（不可变性） 类型 $T$ 是不可变的，当且仅当对于该类型的任意对象 $o$，不存在操作能够改变 $o$ 的观测行为。
形式化地，设 $obs(o)$ 为对象 $o$ 的所有可观测行为的集合。类型 $T$ 不可变当且仅当：
$$\forall o: T, \forall op: Operation, obs(o) = obs(op(o))$$
定义 3.4（浅不可变性） 对象 $o$ 是浅不可变的，如果 $o$ 的直接字段不能被修改，但字段引用的对象可能可变。
定义 3.5（深不可变性） 对象 $o$ 是深不可变的，如果 $o$ 及其所有可达对象都是不可变的。
定理 3.3（Python元组的不可变性） Python元组是浅不可变的。
证明：元组 $t = (v_1, v_2, \ldots, v_n)$ 存储的是引用 $r_1, r_2, \ldots, r_n$。元组保证这些引用不变，即：
$$\forall t, \forall i, \forall op \in {assignment, deletion}, op(t[i]) \text{ raises TypeError}$$
但如果 $r_i$ 指向可变对象 $m$，则 $m$ 可以被修改。因此元组是浅不可变的。∎
3.2 可哈希性的数学理论
3.2.1 哈希函数的形式化定义
定义 3.6（哈希函数） 哈希函数是从任意大小数据到固定大小值的映射：
$$h: U \to {0, 1, \ldots, m-1}$$
其中 $U$ 是全集，$m$ 是哈希表大小。
定义 3.7（理想哈希函数性质） 理想的哈希函数应满足：
- 确定性：$\forall x, h(x)$ 总是返回相同值
- 均匀分布：$\forall i \in {0, \ldots, m-1}, P(h(x) = i) \approx \frac{1}{m}$
- 高效计算：$h(x)$ 可在 $O(|x|)$ 时间内计算
定义 3.8（可哈希对象） 对象 $o$ 是可哈希的，当且仅当：
- $o$ 在其生命周期内哈希值不变
- $o$ 实现了
__hash__和__eq__方法 - 相等对象的哈希值相同：$a = b \Rightarrow hash(a) = hash(b)$
定理 3.4（哈希一致性约束） 若 $a = b$，则必须 $hash(a) = hash(b)$。
证明：反证法。设 $a = b$ 但 $hash(a) \neq hash(b)$。将 $a$ 插入哈希表 $T$，则 $a$ 存储在桶 $hash(a)$。查询 $b$ 时，在桶 $hash(b)$ 查找，无法找到 $a$，但 $a = b$，矛盾。∎
推论 3.1 可变对象不能是可哈希的。
证明：设 $o$ 是可变对象，存在操作使 $o$ 从状态 $s_1$ 变为 $s_2$。若 $o$ 可哈希，则 $hash(o)$ 应不变。但若 $s_1 \neq s_2$，可能 $o_{s_1} = o' \neq o_{s_2}$，此时 $hash(o_{s_1}) = hash(o') \neq hash(o_{s_2})$，与哈希值不变矛盾。∎
3.2.2 元组的可哈希条件
定理 3.5（元组可哈希条件） 元组 $t = (v_1, v_2, \ldots, v_n)$ 是可哈希的，当且仅当所有 $v_i$ 都是可哈希的。
证明：
必要性：若存在 $v_i$ 不可哈希，则 $v_i$ 可变。修改 $v_i$ 会改变 $t$ 的观测行为，从而 $t$ 不可哈希。
充分性：若所有 $v_i$ 可哈希，定义：
$$hash(t) = \bigoplus_{i=1}^{n} (hash(v_i) \times p_i) \mod m$$
其中 $p_i$ 是第 $i$ 个质数，$\oplus$ 是异或操作。
由于所有 $v_i$ 的哈希值不变，$hash(t)$ 也不变。若 $t_1 = t_2$，则所有对应元素相等，故 $hash(t_1) = hash(t_2)$。∎
3.2.3 Python哈希实现分析
import sys
from typing import Any, Tuple
def analyze_tuple_hash(t: Tuple) -> int:
"""分析元组哈希计算"""
h = 0x345678
mult = 1000003
for i, item in enumerate(t):
h = (h ^ hash(item)) * mult
mult += 82520 + i + i
h += 97531
return h
def demonstrate_hash_properties():
"""演示哈希性质"""
t1 = (1, 2, 3)
t2 = (1, 2, 3)
t3 = (1, 2, 4)
print(f"hash((1, 2, 3)) = {hash(t1)}")
print(f"hash((1, 2, 3)) = {hash(t2)}")
print(f"hash((1, 2, 4)) = {hash(t3)}")
print(f"相等元组哈希相等: {hash(t1) == hash(t2)}")
print(f"不等元组哈希可能不等: {hash(t1) != hash(t3)}")
print(f"\n元组大小与哈希值:")
for n in [1, 2, 3, 5, 10]:
t = tuple(range(n))
print(f" {n}元素: hash={hash(t)}, sizeof={sys.getsizeof(t)}")
if __name__ == '__main__':
demonstrate_hash_properties()3.3 元组的内存模型与性能分析
3.3.1 CPython内存布局
CPython PyTupleObject 结构
┌─────────────────────────────────────────────────────────────┐
│ PyObject_VAR_HEAD │
│ ├─ ob_refcnt: Py_ssize_t │ 引用计数 │
│ └─ ob_type: PyTypeObject* │ 类型指针 → &PyTuple_Type │
├─────────────────────────────────────────────────────────────┤
│ ob_size: Py_ssize_t │ 元素数量 (len()) │
│ ob_item[0]: PyObject* │ 第一个元素指针 │
│ ob_item[1]: PyObject* │ 第二个元素指针 │
│ ... │ │
│ ob_item[n-1]: PyObject* │ 最后一个元素指针 │
└─────────────────────────────────────────────────────────────┘3.3.2 内存效率定理
定理 3.6（元组内存效率） 对于相同元素数量 $n$，元组的内存占用严格小于列表。
证明：
列表存储：
PyObject_VAR_HEAD：16字节（64位系统）ob_size：8字节ob_item：8字节（指针）allocated：8字节（容量）- 元素指针数组：$8n$ 字节
总计：$40 + 8n$ 字节
元组存储：
PyObject_VAR_HEAD：16字节ob_size：8字节- 元素指针数组：$8n$ 字节（内联）
总计：$24 + 8n$ 字节（约节省16字节）∎
定理 3.7（元组创建效率） 常量元组的创建时间为 $O(1)$。
证明：CPython对常量元组进行常量折叠（Constant Folding）。编译时，常量元组被存储在代码对象的常量表中。运行时直接返回预构造的元组对象，无需分配内存和初始化元素。∎
3.3.3 性能基准测试
import sys
import timeit
from typing import List, Tuple
def benchmark_tuple_vs_list():
"""元组与列表性能对比"""
n = 1000000
print("=== 内存占用 ===")
for size in [1, 5, 10, 100]:
lst = list(range(size))
tpl = tuple(range(size))
print(f" {size}元素: 列表={sys.getsizeof(lst)}字节, 元组={sys.getsizeof(tpl)}字节")
print("\n=== 创建速度 ===")
list_time = timeit.timeit('[1, 2, 3, 4, 5]', number=n)
tuple_time = timeit.timeit('(1, 2, 3, 4, 5)', number=n)
print(f" 列表: {list_time:.4f}秒")
print(f" 元组: {tuple_time:.4f}秒")
print(f" 元组快 {list_time/tuple_time:.1f}倍")
print("\n=== 索引访问速度 ===")
lst = list(range(10000))
tpl = tuple(range(10000))
list_access = timeit.timeit('lst[5000]', globals=globals(), number=n)
tuple_access = timeit.timeit('tpl[5000]', globals=globals(), number=n)
print(f" 列表: {list_access:.4f}秒")
print(f" 元组: {tuple_access:.4f}秒")
print("\n=== 哈希计算速度 ===")
hash_time = timeit.timeit('hash((1, 2, 3, 4, 5))', number=n)
print(f" hash((1,2,3,4,5)): {hash_time:.4f}秒")
if __name__ == '__main__':
benchmark_tuple_vs_list()3.4 序列解包的理论基础
3.4.1 模式匹配语义
定义 3.9（模式匹配） 模式匹配是将数据结构分解为其组成部分的过程。对于元组，模式匹配定义为：
$$match(t, p) = \begin{cases} \theta & \text{if } t \sim p \ \text{fail} & \text{otherwise} \end{cases}$$
其中 $t$ 是目标元组，$p$ 是模式，$\theta$ 是替换（绑定变量的映射）。
定义 3.10（元组模式） 元组模式的形式化定义为：
$$p ::= (p_1, p_2, \ldots, p_n) \mid x \mid _ \mid p_1 \mid p_2$$
其中：
- $(p_1, \ldots, p_n)$ 是元组模式
- $x$ 是变量模式（绑定值）
- $_$ 是通配符模式（忽略值）
- $p_1 \mid p_2$ 是或模式
定理 3.8（解包完备性） 若模式 $p$ 与元组 $t$ 匹配，则解包操作产生唯一的变量绑定。
证明：归纳证明。
基础情况：变量模式 $x$ 匹配任意值 $v$，产生绑定 ${x \mapsto v}$，唯一。
归纳步骤：设元组模式 $p = (p_1, \ldots, p_n)$ 匹配 $t = (v_1, \ldots, v_n)$。由归纳假设，每个 $p_i$ 匹配 $v_i$ 产生唯一绑定 $\theta_i$。由于变量名不相交，$\theta = \bigcup_i \theta_i$ 是唯一的。∎
3.4.2 扩展解包的形式化
定义 3.11（星号模式） 星号模式 $*x$ 匹配零个或多个元素，绑定为列表：
$$match((v_1, \ldots, v_n), (p_1, *x, p_2)) = {p_1 \mapsto v_1, x \mapsto [v_2, \ldots, v_{n-1}], p_2 \mapsto v_n}$$
定理 3.9（星号模式的唯一性） 在一个模式中，星号模式最多出现一次。
证明：反证法。设模式中有两个星号模式 $*x$ 和 $*y$。匹配元组 $(v_1, \ldots, v_n)$ 时，无法确定 $x$ 和 $y$ 各自匹配多少元素，产生歧义。∎
3.4.3 解包实现
from typing import Tuple, List, Any, TypeVar, Generic
T = TypeVar('T')
class PatternMatcher(Generic[T]):
"""模式匹配器实现"""
@staticmethod
def match_tuple(tpl: Tuple[T, ...], pattern: Tuple) -> dict:
"""
元组模式匹配
pattern 可以包含：
- 具体值：精确匹配
- 变量名（字符串）：绑定值
- '_'：通配符
- '*name'：星号模式
"""
bindings = {}
tpl_idx = 0
pat_idx = 0
star_var = None
star_start = None
while pat_idx < len(pattern):
p = pattern[pat_idx]
if isinstance(p, str) and p.startswith('*'):
star_var = p[1:]
star_start = tpl_idx
pat_idx += 1
continue
if star_var is not None and pat_idx == len(pattern) - 1:
bindings[star_var] = list(tpl[star_start:tpl_idx])
star_var = None
if tpl_idx >= len(tpl):
return None
val = tpl[tpl_idx]
if isinstance(p, str):
if p == '_':
pass
elif p.startswith('*'):
pass
else:
bindings[p] = val
elif p == val:
pass
else:
return None
tpl_idx += 1
pat_idx += 1
if star_var is not None:
bindings[star_var] = list(tpl[star_start:])
return bindings if tpl_idx == len(tpl) else None
def demo_pattern_matching():
"""演示模式匹配"""
matcher = PatternMatcher()
tpl = (1, 2, 3, 4, 5)
print(f"元组: {tpl}")
result = matcher.match_tuple(tpl, ('a', 'b', 'c', 'd', 'e'))
print(f"模式 ('a', 'b', 'c', 'd', 'e'): {result}")
result = matcher.match_tuple(tpl, ('first', '*rest'))
print(f"模式 ('first', '*rest'): {result}")
result = matcher.match_tuple(tpl, ('*head', 'last'))
print(f"模式 ('*head', 'last'): {result}")
result = matcher.match_tuple(tpl, ('first', '*middle', 'last'))
print(f"模式 ('first', '*middle', 'last'): {result}")
if __name__ == '__main__':
demo_pattern_matching()3.5 命名元组的代数规范
3.5.1 命名元组ADT
ADT 3.2（NamedTuple）
ADT NamedTuple[N: ℕ, Fields: (String × Type)^N]
Types: NamedTuple[Fields]
Operations:
create: (v₁: T₁, ..., vₙ: Tₙ) → NamedTuple[Fields]
get: NamedTuple[Fields] × String → Tᵢ
get_by_index: NamedTuple[Fields] × ℕ → Tᵢ
fields: → (String)^N
asdict: NamedTuple[Fields] → Dict[String, Tᵢ]
replace: NamedTuple[Fields] × String × Tᵢ → NamedTuple[Fields]
Axioms:
∀nt: NamedTuple[Fields], ∀f: String, ∀v: Tᵢ
(A1) get(create(v₁, ..., vₙ), fᵢ) = vᵢ
(A2) get_by_index(create(v₁, ..., vₙ), i) = vᵢ
(A3) get(nt, fᵢ) = get_by_index(nt, i)
(A4) asdict(create(v₁, ..., vₙ)) = {f₁: v₁, ..., fₙ: vₙ}
(A5) get(replace(nt, fᵢ, v), fᵢ) = v
(A6) fⱼ ≠ fᵢ → get(replace(nt, fᵢ, v), fⱼ) = get(nt, fⱼ)3.5.2 类型安全的命名元组
from typing import NamedTuple, TypeVar, Generic, Optional, Dict, Any
from dataclasses import dataclass
from abc import ABC, abstractmethod
T = TypeVar('T')
class TypedNamedTuple(ABC):
"""类型安全的命名元组基类"""
@classmethod
@abstractmethod
def field_names(cls) -> Tuple[str, ...]:
"""返回字段名列表"""
pass
@classmethod
@abstractmethod
def field_types(cls) -> Dict[str, type]:
"""返回字段类型映射"""
pass
@abstractmethod
def as_dict(self) -> Dict[str, Any]:
"""转换为字典"""
pass
@abstractmethod
def validate(self) -> bool:
"""验证类型约束"""
pass
class Point2D(NamedTuple):
"""二维点 - 类型安全命名元组"""
x: float
y: float
def distance_to(self, other: 'Point2D') -> float:
"""计算两点距离"""
return ((self.x - other.x) ** 2 + (self.y - other.y) ** 2) ** 0.5
def distance_to_origin(self) -> float:
"""到原点距离"""
return self.distance_to(Point2D(0, 0))
def translate(self, dx: float, dy: float) -> 'Point2D':
"""平移（返回新点）"""
return Point2D(self.x + dx, self.y + dy)
def scale(self, factor: float) -> 'Point2D':
"""缩放"""
return Point2D(self.x * factor, self.y * factor)
class Vector3D(NamedTuple):
"""三维向量"""
x: float
y: float
z: float
def dot(self, other: 'Vector3D') -> float:
"""点积"""
return self.x * other.x + self.y * other.y + self.z * other.z
def cross(self, other: 'Vector3D') -> 'Vector3D':
"""叉积"""
return Vector3D(
self.y * other.z - self.z * other.y,
self.z * other.x - self.x * other.z,
self.x * other.y - self.y * other.x
)
def magnitude(self) -> float:
"""模长"""
return (self.dot(self)) ** 0.5
def normalize(self) -> 'Vector3D':
"""单位化"""
m = self.magnitude()
if m == 0:
raise ValueError("Cannot normalize zero vector")
return Vector3D(self.x / m, self.y / m, self.z / m)
def __add__(self, other: 'Vector3D') -> 'Vector3D':
return Vector3D(self.x + other.x, self.y + other.y, self.z + other.z)
def __sub__(self, other: 'Vector3D') -> 'Vector3D':
return Vector3D(self.x - other.x, self.y - other.y, self.z - other.z)
def __mul__(self, scalar: float) -> 'Vector3D':
return Vector3D(self.x * scalar, self.y * scalar, self.z * scalar)
def demo_named_tuple():
"""演示命名元组"""
p1 = Point2D(3, 4)
p2 = Point2D(6, 8)
print(f"点1: {p1}")
print(f"点2: {p2}")
print(f"p1到原点距离: {p1.distance_to_origin()}")
print(f"p1到p2距离: {p1.distance_to(p2)}")
print(f"p1平移(1, 1): {p1.translate(1, 1)}")
v1 = Vector3D(1, 0, 0)
v2 = Vector3D(0, 1, 0)
print(f"\nv1 × v2 = {v1.cross(v2)}")
print(f"v1 · v2 = {v1.dot(v2)}")
if __name__ == '__main__':
demo_named_tuple()3.6 不可变数据结构的设计模式
3.6.1 值对象模式
定义 3.12（值对象） 值对象是通过其属性值而非身份来定义的对象。两个值对象相等当且仅当它们的所有属性相等。
定理 3.10（值对象的不变性） 值对象必须是不可变的，以保证相等性语义的一致性。
证明：设值对象 $v_1, v_2$ 相等。若 $v_1$ 可变，修改后 $v_1 \neq v_2$，但 $v_2$ 未变，矛盾。∎
from dataclasses import dataclass, field
from typing import Tuple, Optional, List
from functools import total_ordering
import math
@dataclass(frozen=True, order=True)
class Money:
"""货币值对象"""
amount: float
currency: str = "USD"
def __post_init__(self):
if self.amount < 0:
raise ValueError("Amount cannot be negative")
def add(self, other: 'Money') -> 'Money':
if self.currency != other.currency:
raise ValueError("Cannot add different currencies")
return Money(self.amount + other.amount, self.currency)
def multiply(self, factor: float) -> 'Money':
return Money(self.amount * factor, self.currency)
def __str__(self) -> str:
return f"{self.amount:.2f} {self.currency}"
@dataclass(frozen=True)
class DateRange:
"""日期范围值对象"""
start: Tuple[int, int, int]
end: Tuple[int, int, int]
def __post_init__(self):
if self.start > self.end:
raise ValueError("Start date must be before end date")
def contains(self, date: Tuple[int, int, int]) -> bool:
return self.start <= date <= self.end
def overlaps(self, other: 'DateRange') -> bool:
return self.start <= other.end and other.start <= self.end
def duration_days(self) -> int:
return (self._to_days(self.end) - self._to_days(self.start))
@staticmethod
def _to_days(date: Tuple[int, int, int]) -> int:
y, m, d = date
return y * 365 + m * 30 + d
@dataclass(frozen=True)
class Coordinate:
"""地理坐标值对象"""
latitude: float
longitude: float
def __post_init__(self):
if not -90 <= self.latitude <= 90:
raise ValueError("Latitude must be between -90 and 90")
if not -180 <= self.longitude <= 180:
raise ValueError("Longitude must be between -180 and 180")
def distance_to(self, other: 'Coordinate') -> float:
"""Haversine公式计算球面距离（公里）"""
R = 6371
lat1, lon1 = math.radians(self.latitude), math.radians(self.longitude)
lat2, lon2 = math.radians(other.latitude), math.radians(other.longitude)
dlat = lat2 - lat1
dlon = lon2 - lon1
a = math.sin(dlat/2)**2 + math.cos(lat1) * math.cos(lat2) * math.sin(dlon/2)**2
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
return R * c
def __str__(self) -> str:
ns = 'N' if self.latitude >= 0 else 'S'
ew = 'E' if self.longitude >= 0 else 'W'
return f"{abs(self.latitude):.4f}°{ns}, {abs(self.longitude):.4f}°{ew}"3.6.2 不可变构建器模式
from typing import TypeVar, Generic, Optional, Dict, Any, Callable
from dataclasses import dataclass, field
from copy import deepcopy
T = TypeVar('T')
@dataclass(frozen=True)
class ImmutableConfig:
"""不可变配置"""
host: str
port: int
database: str
username: Optional[str] = None
password: Optional[str] = None
timeout: int = 30
ssl: bool = False
pool_size: int = 10
class Builder:
"""配置构建器"""
def __init__(self, config: Optional['ImmutableConfig'] = None):
self._data = {}
if config:
self._data = {
'host': config.host,
'port': config.port,
'database': config.database,
'username': config.username,
'password': config.password,
'timeout': config.timeout,
'ssl': config.ssl,
'pool_size': config.pool_size,
}
def host(self, value: str) -> 'ImmutableConfig.Builder':
self._data['host'] = value
return self
def port(self, value: int) -> 'ImmutableConfig.Builder':
self._data['port'] = value
return self
def database(self, value: str) -> 'ImmutableConfig.Builder':
self._data['database'] = value
return self
def credentials(self, username: str, password: str) -> 'ImmutableConfig.Builder':
self._data['username'] = username
self._data['password'] = password
return self
def timeout(self, value: int) -> 'ImmutableConfig.Builder':
self._data['timeout'] = value
return self
def ssl(self, enabled: bool = True) -> 'ImmutableConfig.Builder':
self._data['ssl'] = enabled
return self
def pool_size(self, value: int) -> 'ImmutableConfig.Builder':
self._data['pool_size'] = value
return self
def build(self) -> 'ImmutableConfig':
required = ['host', 'port', 'database']
for field in required:
if field not in self._data:
raise ValueError(f"Missing required field: {field}")
return ImmutableConfig(**self._data)
def with_port(self, new_port: int) -> 'ImmutableConfig':
"""返回修改端口的新配置"""
return ImmutableConfig(
host=self.host,
port=new_port,
database=self.database,
username=self.username,
password=self.password,
timeout=self.timeout,
ssl=self.ssl,
pool_size=self.pool_size,
)
def to_builder(self) -> Builder:
"""转换为构建器"""
return ImmutableConfig.Builder(self)
def demo_immutable_config():
"""演示不可变配置"""
config = (ImmutableConfig.Builder()
.host("localhost")
.port(5432)
.database("mydb")
.credentials("user", "pass")
.ssl()
.build())
print(f"原始配置: {config}")
new_config = config.with_port(5433)
print(f"修改端口: {new_config}")
print(f"原配置不变: {config}")
updated = (config.to_builder()
.port(5434)
.timeout(60)
.build())
print(f"更新配置: {updated}")
if __name__ == '__main__':
demo_immutable_config()3.7 持久化数据结构
3.7.1 持久化数据结构理论
定义 3.13（持久化数据结构） 持久化数据结构在修改时保留之前的版本，支持对历史版本的访问。
定义 3.14（完全持久化） 数据结构支持对任意版本的查询和修改，形成版本树。
定理 3.11（不可变数据结构的持久化） 不可变数据结构天然支持持久化，因为修改操作创建新版本而不破坏旧版本。
证明：设不可变数据结构 $D$，修改操作 $modify(D, op)$ 返回新结构 $D'$。由于 $D$ 不可变，$D$ 在 $modify$ 后保持不变，因此可以同时访问 $D$ 和 $D'$。∎
3.7.2 持久化列表实现
from typing import TypeVar, Generic, Optional, List, Iterator, Tuple
from dataclasses import dataclass
T = TypeVar('T')
@dataclass(frozen=True)
class PersistentList(Generic[T]):
"""
持久化列表（基于二叉树）
操作复杂度：
- get: O(log n)
- set: O(log n)
- push: O(log n)
- pop: O(log n)
空间复杂度：每次修改 O(log n) 新节点
"""
_size: int
_tree: Optional[Tuple[T, 'PersistentList[T]', 'PersistentList[T]']]
@classmethod
def empty(cls) -> 'PersistentList[T]':
return cls(0, None)
@classmethod
def from_list(cls, items: List[T]) -> 'PersistentList[T]':
result = cls.empty()
for item in items:
result = result.push(item)
return result
def is_empty(self) -> bool:
return self._size == 0
def __len__(self) -> int:
return self._size
def push(self, value: T) -> 'PersistentList[T]':
"""在头部添加元素"""
return PersistentList(self._size + 1, (value, self, PersistentList.empty()))
def head(self) -> Optional[T]:
"""获取头部元素"""
if self._tree is None:
return None
return self._tree[0]
def tail(self) -> 'PersistentList[T]':
"""获取尾部列表"""
if self._tree is None:
return self
return self._tree[1]
def get(self, index: int) -> Optional[T]:
"""获取指定位置元素"""
if not 0 <= index < self._size:
return None
return self._get(index, self._size)
def _get(self, index: int, size: int) -> T:
if size == 1:
return self._tree[0]
left_size = size // 2
if index < left_size:
return self._tree[1]._get(index, left_size)
else:
return self._tree[2]._get(index - left_size, size - left_size)
def set(self, index: int, value: T) -> 'PersistentList[T]':
"""设置指定位置元素（返回新列表）"""
if not 0 <= index < self._size:
raise IndexError("Index out of range")
return self._set(index, value, self._size)
def _set(self, index: int, value: T, size: int) -> 'PersistentList[T]':
if size == 1:
return PersistentList(1, (value, PersistentList.empty(), PersistentList.empty()))
left_size = size // 2
if index < left_size:
new_left = self._tree[1]._set(index, value, left_size)
return PersistentList(size, (self._tree[0], new_left, self._tree[2]))
else:
new_right = self._tree[2]._set(index - left_size, value, size - left_size)
return PersistentList(size, (self._tree[0], self._tree[1], new_right))
def to_list(self) -> List[T]:
"""转换为Python列表"""
result = []
self._to_list(result, self._size)
return result
def _to_list(self, result: List[T], size: int) -> None:
if size == 0:
return
if size == 1:
result.append(self._tree[0])
return
left_size = size // 2
self._tree[1]._to_list(result, left_size)
self._tree[2]._to_list(result, size - left_size)
def __iter__(self) -> Iterator[T]:
return iter(self.to_list())
def __repr__(self) -> str:
return f"PersistentList({self.to_list()})"
def demo_persistent_list():
"""演示持久化列表"""
l1 = PersistentList.from_list([1, 2, 3, 4, 5])
print(f"l1 = {l1}")
l2 = l1.set(2, 100)
print(f"l2 = l1.set(2, 100) = {l2}")
print(f"l1 不变 = {l1}")
l3 = l2.push(0)
print(f"l3 = l2.push(0) = {l3}")
print(f"l2 不变 = {l2}")
print(f"\n历史版本:")
print(f" l1[2] = {l1.get(2)}")
print(f" l2[2] = {l2.get(2)}")
print(f" l3[0] = {l3.get(0)}")
if __name__ == '__main__':
demo_persistent_list()3.8 本章小结
3.8.1 核心定理总结
| 定理 | 内容 | 应用 |
|---|---|---|
| 定理 3.1 | 元组同构性 | 类型推导 |
| 定理 3.4 | 哈希一致性约束 | 哈希表设计 |
| 定理 3.5 | 元组可哈希条件 | 字典键设计 |
| 定理 3.6 | 元组内存效率 | 性能优化 |
| 定理 3.10 | 值对象不变性 | 设计模式 |
3.8.2 元组 vs 列表对比
| 特性 | 元组 | 列表 |
|---|---|---|
| 可变性 | 不可变 | 可变 |
| 可哈希性 | 是（元素可哈希时） | 否 |
| 内存占用 | $O(n)$ | $O(n)$ + 容量开销 |
| 创建速度 | $O(1)$（常量折叠） | $O(n)$ |
| 作为字典键 | 可以 | 不可以 |
| 线程安全 | 是 | 需要锁 |
| 语义 | 值类型 | 引用类型 |
3.8.3 选择指南
# 使用元组的场景
coordinates = (x, y) # 固定结构数据
config = ("localhost", 5432) # 配置常量
return min_val, max_val # 函数返回多值
d[(key1, key2)] = value # 复合键
# 使用命名元组的场景
Point = namedtuple("Point", "x y") # 需要字段名
Employee = namedtuple("Employee", "id name dept") # 记录类型
# 使用frozen dataclass的场景
@dataclass(frozen=True)
class Money: # 需要方法和验证
amount: float
currency: str3.9 习题
理论题
证明：对于类型 $A, B, C$，有 $A \times (B + C) \cong A \times B + A \times C$（分配律）。
证明：若 $a = b$，则 $hash(a) = hash(b)$，但逆命题不成立。
分析持久化列表的
set操作空间复杂度为 $O(\log n)$。证明：不可变数据结构天然线程安全。
设计题
设计一个不可变的二叉搜索树，支持 $O(\log n)$ 的查找、插入和删除。
实现一个持久化字典，支持历史版本查询。
实现题
实现一个支持模式匹配的元组解包函数。
实现一个不可变的优先队列。
3.10 参考文献
Pierce, B. C. (2002). Types and Programming Languages. MIT Press. Chapter 11: Simple Extensions.
Okasaki, C. (1999). Purely Functional Data Structures. Cambridge University Press.
Abelson, H., & Sussman, G. J. (1996). Structure and Interpretation of Computer Programs (2nd ed.). MIT Press.
Bloch, J. (2018). Effective Java (3rd ed.). Addison-Wesley. Item 17: Minimize mutability.
CPython Source Code. (2024). Objects/tupleobject.c. https://github.com/python/cpython/blob/main/Objects/tupleobject.c
Fowlie, M. (2015). Pattern matching in Python. PyCon 2015.
下一章：第4章 字典与哈希表理论