Loading article…
コンピュータ科学において、リストまたはシーケンスとは、数が有限で特定の順序で並んだ項目の集合のことである。リストのインスタンスは、タプルまたは有限シーケンスという数学的概念をコンピュータ上で表現したものである。
リストには同じ値が複数回含まれることがありますが、それぞれの出現箇所は個別の項目として扱われます。
リストという用語は、抽象リストを実装するために使用できるいくつかの具体的なデータ構造、特にリンクリストと配列にも使用されます。Lispプログラミングなどの一部のコンテキストでは、リストという用語は配列ではなくリンクリストを具体的に指す場合があります。クラスベースのプログラミングでは、リストは通常、汎用的な「リスト」クラスのサブクラスのインスタンスとして提供され、個別のイテレータを介して走査されます。
多くのプログラミング言語はリストデータ型をサポートしており、リストとリスト操作には特別な構文と意味論が用いられています。リストは、括弧 '()'、角括弧 '[]'、中括弧 '{}'、山括弧 '<>' などの区切り文字で区切られた項目を、カンマ、セミコロン、スペースなどで区切って順番に記述することで作成できます。言語によっては、リスト型を配列型のようにインデックス付けしたりスライスしたりできる場合があり、その場合はデータ型は配列としてより正確に表現できます。
型理論と関数型プログラミングでは、抽象リストは通常、空のリストを生成するnilと、リストの先頭に項目を追加するconsという2 つの操作によって帰納的に定義されます。 [ 1 ]
リストデータ構造の実装では、以下の操作の一部または全部を低レベルのプリミティブとして提供する場合があります。
リストは通常、リンクリスト（単方向または双方向リンク）または配列（通常は可変長または動的配列）として実装されます。
プログラミング言語Lispに由来するリストの標準的な実装方法は、リストの各要素にその値と、リスト内の次の要素の位置を示すポインタの両方を持たせることです。これにより、リストにネストされたサブリストがあるかどうかに応じて、リンクリストまたはツリーが生成されます。一部の古い Lisp 実装 ( Symbolics 3600の Lisp 実装など) では、特別な内部表現 (ユーザーには見えない) を持つ「圧縮リスト ( CDR コーディングを使用)」もサポートされていました。リストは、反復または再帰を使用して操作できます。前者は命令型プログラミング言語でよく好まれ、後者は関数型言語で標準となっています。
リストは、インデックスと値のペアを保持する自己平衡二分探索木として実装でき、任意の要素（例えば、フリンジに存在するすべての要素、および検索をガイドするために使用される最も右の子のインデックスを格納する内部ノード）に等時間でアクセスでき、リストのサイズに対して対数的な時間を要しますが、サイズが大きく変化しない限り、ランダムアクセスの錯覚を提供し、スワップ、プレフィックス、および追加操作も対数時間で実行できます。[ 3 ]
一部の言語ではリストデータ構造が提供されていませんが、連想配列や何らかのテーブルを使用してリストをエミュレートできます。たとえば、 Lua はテーブルを提供しています。Lua は数値インデックスを持つリストを内部的に配列として格納しますが、それらは依然として辞書として表示されます。[ 4 ]
Lispでは、リストは基本的なデータ型であり、プログラム コードとデータの両方を表すことができます。ほとんどの方言では、最初の 3 つの素数のリストは と書くことができます(list 2 3 5)。Scheme を含むいくつかの Lisp の方言では、リストは値と次のペア (または null 値) へのポインタで構成されるペアの集合であり、単方向連結リストになります。[ 5 ]
配列とは異なり、リストは拡張したり縮小したりできます。
コンピューティングにおいては、リストはセットよりも実装が容易です。数学的な意味での有限セットは、追加の制約（重複要素の禁止、順序の無関係など）を持つリストとして実現できます。リストをソートすることで、特定の項目が既にセットに含まれているかどうかを判断する速度は向上しますが、順序を保証するためには、リストに新しい項目を追加するのに時間がかかります。しかし、効率的な実装では、セットはリストではなく、自己平衡二分探索木やハッシュテーブルを用いて実装されます。
ある型Eの要素を持つ抽象リスト型L（単相リスト）は、以下の関数によって定義されます。
公理と共に
任意の要素eと任意のリストlに対して、次のことが暗黙のうちに成り立つ。
first (nil ()) と rest (nil ()) は定義されていないことに注意してください。
これらの公理は、抽象スタックデータ型の公理と同等である。
型理論では、上記の定義は、 nilとconsというコンストラクタによって定義される帰納型としてより単純に考えられます。代数的には、これは 1 + E × L → Lという変換として表すことができます。first とrest は、consコンストラクタに対するパターンマッチングと、 nil の場合を個別に処理することによって得られます。
リスト型は、以下の関数を持つモナドを形成します（要素が型Eである単相リストを表すために、 LではなくE *を使用します）。
ここで、appendは次のように定義されます。
あるいは、モナドは、 return、fmap、joinという操作によって定義することもできます。
fmap、join、append、bindは、再帰呼び出しのたびに段階的に深い引数に適用されるため、明確に定義されていることに注意してください。
リスト型は加算型モナドであり、nilはモナドのゼロ、appendはモナドの和を表します。
リストは、追加操作に関してモノイドを形成します。モノイドの単位元は空リスト、つまりnilです。実際、これはリスト要素の集合上の自由モノイドです。
