7

私は良いアーランガーになり、「++」を避けようとしています。ネストされたリストを作成せずにリストの最後にタプルを追加する必要があります (できれば、逆に構築して逆にする必要はありません)。タプル T とリスト L0 および L1 が与えられた場合:

[T|L0]を使用すると、 [tuple,list0]が得られます。

しかし、[L0|T]を使用すると、ネストされたリスト[[list0]|tuple]が得られます。同様に、[L0|L1]は[[list0]|list1]を返します。

外側のリスト ブラケットL0|[T]を削除すると、構文エラーが発生します。

なぜ「|」なのか 対称的ではない?「|」を使用してやりたいことを行う方法はありますか?

4

1 に答える 1

20

|空でないリストには頭と尾があり、頭が単一の項目で、尾が別のリストであるため、「対称」ではありません。In 式[foo | bar] fooはリストの先頭を表し、barは末尾です。末尾が適切なリストでない場合、結果も適切なリストにはなりません。ヘッドがリストの場合、結果はそのリストを最初の要素とする単純なリストになります。

リンクされたリストの最後に O(n) 時間未満で追加する方法はありません。これが、++for that の使用が一般的に敬遠される理由です。リストの最後に追加する特別な構文があったとしても、それでも O(n) 時間かかる必要があり、その構文を使用しても、使用++するよりも「良いアーランガー」にはなりません。

挿入あたりの O(n) コストを回避したい場合は、前に追加してから逆にする必要があります。コストを支払う意思がある場合は、 を使用することもできます++

リストの仕組みについてもう少し詳しく説明します。

[ x | y ]コンスセルと呼ばれるものです。C の用語では、基本的に 2 つのメンバーを持つ構造体です。適切なリストは、空のリスト ( []) または 2 番目のメンバーが適切なリストであるコンス セルです (この場合、最初のメンバーはそのヘッドと呼ばれ、2 番目のメンバーはそのテールと呼ばれます)。

したがって、[1, 2, 3]これを記述すると、次のコンス セルが作成されます[1 | [2 | [3 | []]]]。つまり、リストは、最初のメンバー (先頭) が 1 で、2 番目のメンバー (末尾) が別のコンス セルであるコンス セルとして表されます。そのもう 1 つのコンス セルは、先頭に 2 を持ち、さらにもう 1 つのコンス セルを末尾に持っています。そのセルには、先頭に 3 があり、末尾に空のリストがあります。

このようなリストのトラバースは、最初にリストの先頭に作用し、次にリストの末尾でトラバーサル関数を呼び出すことによって再帰的に行われます。

そのリストの先頭に項目を追加したい場合、これは非常に簡単です。頭が新しい項目で、末尾が古いリストである別のコンス セルを作成するだけです。

ただし、単一のコンス セルを作成するだけでは十分でないため、アイテムの追加ははるかにコストがかかります。古いものと同じリストを作成する必要がありますが、最後のコンス セルの末尾は、先頭が新しい要素で末尾が空のリストである新しいコンス セルでなければなりません。したがって、O(n) であるリスト全体を調べずにリストに追加することはできません。

于 2010-07-12T22:40:36.137 に答える