可变与不可变数据结构为何不应形成子类型关系

在编程语言设计中，可变数据结构和不可变数据结构不应该互为子类型。这一结论源于对Liskov替换原则的严格应用。1根据该原则，类型S成为T的子类型当且仅当S的值可以在期望T值的任何上下文中使用。1

可变对和不可变对虽然提供相同的操作集（如car、cdr），但二者之间存在根本的契约差异。1不可变对额外保证了返回值的恒定性，这一承诺是哈希一致性的前提条件。1若将可变对作为不可变对的子类型使用，破坏这一不变性契约会导致类型检查保证失效。1因此在形式上，可变性和不可变性无法满足替换原则的要求。1

为了在可变与不可变数据结构间实现多态，编程语言可以采用替代方案。1推荐使用类型类、接口或特征等机制来实现ad hoc多态，而非依赖子类型关系。1

A discussion on Hacker News examines why mutable and immutable data structures should not be considered subtypes of one another, despite their apparent similarities 1. The core issue centers on the Liskov Substitution Principle, which defines that a type S qualifies as a subtype of type T only when values of S can be safely used in any context expecting values of T 1.

While mutable and immutable pairs provide the same set of operations—such as car and cdr functions—they carry fundamentally different implicit contracts 1. Immutable pairs guarantee that returned values will remain constant, whereas mutable pairs allow their values to be modified 1. This distinction violates the strict requirements of the Liskov Substitution Principle, as substituting one for the other in certain contexts would break expected guarantees 1. Immutability serves as a prerequisite for hash consistency, and breaking this contract can cause type-checking guarantees to fail 1.

Rather than attempting to establish subtype relationships between mutable and immutable structures, the article recommends using alternative mechanisms to achieve polymorphism between them 1. These approaches include type classes, interfaces, and traits, which enable ad hoc polymorphism without relying on traditional subtyping hierarchies 1.