なぜmutableはimmutableのサブタイプになれないのか
Why isn't mutable a subtype of immutable, or vice versa?
immutableとmutableのデータ構造がサブタイプ関係になれない理由を、Liskovの置換原則とpairを例に解説。immutable pairのcar/cdrには「常に同じ値を返す」という暗黙の契約があり、mutable pairはそれを保証できない。そのため両者は別の型として扱う必要があり、型クラスやduck typingによるアドホック多相が代替となる。
immutable pairのcarやcdrを取るとき、そのpairに対して呼び出すたびに結果が常に同じになるという契約に依存できる。この契約のおかげで、例えばpairの内容に基づいてハッシュ値を安全に計算し、別のデータ構造に保存しておき、後で取り出そうと再計算しても値が変わらないと確信できる。（言い換えれば、immutabilityはhash consingの前提条件なのだ！）
HNでの議論
13- js8
説明は過剰に複雑化されている気がする。型は変数ではなく値の性質だ。可変性は値ではなく変数の性質だ。
つまり、これは一種のカテゴリー錯誤なんだ。「変数の型」と言うとき、その変数には特定の型の値しか代入（束縛）できないという意味だ。これは再代入可能かどうか（つまり可変性）とは何の関係もない。
だから、これを説明するのにサブタイピングの概念すら必要ない。
それに、変数はその型上のモナドとして定義することもできるだろう。
- BlackFly
可変性を排他的アクセスと組み合わせれば、ここで（過度に厳格だと一部の人は言うかもしれない）サブタイピングの定義が提起した反論、そしてその反論に対する反論の試みにも対処できる。immutableなインスタンスを要求するコードが可変性を観察することは決してない。なぜなら、immutableな参照を求めることは排他的だからだ。したがって、mutableな参照を渡すことはできるが、誰かがその参照を保持している限り、可変性は他のコードからは利用できなくなる。
つまり、可変性 XOR エイリアシングがこの厳格なサブタイピング関係を提供する。もちろん、そうした契約を持たないオブジェクトを提供することでこれを緩める方法も必要になり、内部可変性の世界に入り込む。そこでもまた、mutableなメソッドはサブタイプの一部として理解できる。なぜなら、mutableなメソッドを持たない参照の保持者は、そのオブジェクトが変化しないという保証はないと明示的に告げられていたからだ。
- raincole
言い換えれば、immutable != read only ということだ。
C#では、まさにこの理由から ReadOnlyCollection<T> と ImmutableArray<T> は完全に別物だ。