functional-programming - OCaml の `list` が最後の要素へのポインタを維持しないのはなぜですか?

Question

を行うときはl1 @ l2、O(length(l1))l1 を経由して l1 と l2 を接続する必要があるためです。

last_elementだから私の質問は、なぜ実装がポインタを維持しないのですか?

OCamlの標準ライブラリ実装の意思決定プロセスを学び/理解したいので、これを尋ねます。

Answer 1

の最後の要素に行くだけではl1役に立ちません。の内容全体をコピーする必要があり、l1それを実行せずにそれを行うことはできません。したがって、の最後へのポインタを持ってl1いても役に立ちません。

Answer 2

sepp2k の回答に基づいて構築するには: リストは OCaml でこのように実装されています。

type 'a list = Nil | Cons of 'a * 'a list

リスト l1 [1;2;3] は、次のように考えることができます。

Cons (1, Cons(2, Cons(3, Nil)))

Cons(3, Nil) で l2 と連結したい場合、Nil を l2 に置き換える必要がありますが、これらの要素は不変であるため、これは不可能です。新しいリストは次のように構成されます。

Cons (1, Cons(2, Cons(3, l2)))

O(長さ(l1))

Answer 3

Octref と sepp2kO(1)は、cons リストを追加することが不可能な理由をよく説明しています。一定時間 (償却または最悪の場合) の追加をサポートする他のデータ構造をいつでも使用できることを指摘したいと思います。

その他のオプションは次のとおりです。

1) 差分リストにはO(1)追加がありますが、O(n)それらをコンス リストに変換する必要があります。(ただし、OCaml での実装は認識していません)

2) Catenable リストにはO(1)償却された追加があります。

3) 変更可能なリンク リストはいつでも使用できます。DllList電池など。