2

OCaml では、 list に対して常にfirst::rest. リストから最初の要素を取得するか、リストの前に要素を挿入すると便利です。

しかし、なぜ OCaml には がないのrest::lastでしょうか? の関数がなければList、リストの最後の要素を取得したり、リストの最後に要素を挿入したりすることは容易ではありません。

4

2 に答える 2

8

リストのデータ型は魔法の組み込みではなく、構文糖衣を備えた通常の再帰的なデータ型にすぎません。Nilの代わりに[]とのCons(first,rest)代わりにを使用first::restして、次のように自分で実装できます。

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

上記の定義があなたの質問に対する答えとして表示されるかどうかはわかりませんが、実際にはそうです: を記述するときfirst::rest、関数を呼び出すのではなく、新しい値を構築するデータ型コンストラクターを使用しているだけです (一定の時間と空間で）。

この定義は単純で、明確なアルゴリズム プロパティがあります。リストは不変、リスト is の最初の要素にO(1)アクセスする、k-th 要素 isにアクセスする、2 つのリストとisO(k)を連結する、などです。特に、最後の要素にアクセスするか、何かを追加しますリストの終わりは次のようになります。コストがかかるため、これを便利な操作として公開したくありません。li1li2O(length(li1))liO(length(li))

シーケンスの最後に要素を追加したい場合、リストは適切なデータ構造ではありません。キュー (先入れ先出しアクセス規律に従う場合)、 adequeなどを使用することができます。標準ライブラリには (変更可能な)構造があり、 CoreとBatteriesQueueの 2 つのサードパーティ オーバーレイがあります。 deque モジュール (バッテリーでは永続的、コアでは変更可能)。

于 2013-02-02T11:53:56.870 に答える
5

リストは次のように定義された単純なデータ型であるため、

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

Nilas[]およびConsinfixと綴ることを除いて::。つまり、必要に応じて、リストは「単一リンク」です。コンストラクターの構文を除いて、魔法は必要ありません。明らかに、最後の要素に到達する、または要素を追加するには、いくつかの補助関数が必要です。

于 2013-02-02T11:58:27.660 に答える