F# のコレクション型

  • [アーティクル]

このトピックを読むと、特定のニーズに最も適した F# のコレクション型を特定できます。 これらのコレクション型は、.NET のコレクション型 (System.Collections.Generic 名前空間のものなど) とは異なります。F# のコレクション型は、オブジェクト指向の観点ではなく関数型プログラミングの観点で設計されています。 具体的には、配列コレクションのみに変更可能な要素があります。 したがって、コレクションを変更する場合は、元のコレクションを変更するのではなく、変更されたコレクションのインスタンスを作成します。

コレクション型には、オブジェクトが格納されるデータ構造の型にも違いがあります。 ハッシュ テーブル、リンク リスト、配列などのデータ構造には、パフォーマンス特性と使用可能な操作のセットに違いがあります。

コレクション型の表

F# のコレクション型を次の表に示します。

種類 説明 関連リンク
リスト 順序が指定されており、変更できない一連の同じ型の要素です。 リンク リストとして実装されます。 リスト

List モジュール
配列 0 から始まる一連のデータ要素の、固定サイズの変更可能なコレクションで、その型はすべて同じです。 配列

Array モジュール

Array2D モジュール

Array3D モジュール
seq すべてが 1 つの型である論理的な一連の要素です。 シーケンスは、順序付けられた大量のデータのコレクションがあり、必ずしもすべての要素を使用するとは限らない場合に特に便利です。 個々のシーケンス要素は必要に応じてのみ計算されるので、全部の要素を使用するわけではない場合、シーケンスはリストよりもパフォーマンスが優れています。 シーケンスは、IEnumerable<T> のエイリアスである seq<'T> 型によって表されます。 したがって、System.Collections.Generic.IEnumerable<'T> を実装するすべての .NET Framework 型をシーケンスとして使用できます。 シーケンス

Seq モジュール
Map 要素の変更できない辞書。 要素は、キーによってアクセスされます。 Map モジュール
Set バイナリ ツリーに基づく変更できないセット。ここでは、比較は F# の構造的な比較関数であり、キー値の System.IComparable インターフェイスの実装が使用される可能性があります。 Set モジュール

関数の表

このセクションでは、F# のコレクション型で使用できる関数を比較します。 関数の計算複雑度が示されます。ここで、N は最初のコレクションのサイズ、M は 2 番目のコレクション (存在する場合) のサイズです。 ダッシュ (-) は、この関数がコレクションで使用できないことを示します。 Seq.distinct などの関数では、即座の応答が行われるので、列挙された場合に、シーケンスのパフォーマンスへの影響は依然として残りますが、シーケンスがゆっくりと評価されるため、O(1) になることがあります。

機能 Array List Sequence マップ オン 説明
append O(N) O(N) O(N) - - 最初のコレクションの要素の後に 2 番目のコレクションの要素を含む新しいコレクションを返します。
add - - - O(log(N)) O(log(N)) 要素が追加された新しいコレクションを返します。
average O(N) O(N) O(N) - - コレクション内の要素の平均を返します。
averageBy O(N) O(N) O(N) - - 各要素に適用される指定された関数の結果の平均を返します。
blit O(N) - - - - 配列の一部をコピーします。
cache - - O(N) - - シーケンスの要素を計算して格納します。
キャスト - - O(N) - - 要素を指定した型に変換します。
choose O(N) O(N) O(N) - - 指定された関数 f をリストの各要素 x に適用します。 関数が Some(f(x)) を返す各要素の結果を含むリストを返します。
collect O(N) O(N) O(N) - - 指定された関数をコレクションの各要素に適用し、すべての結果を連結して、結合されたリストを返します。
compareWith - - O(N) - - 指定された比較関数を要素ごとに使用して、2 つのシーケンスを比較します。
concat O(N) O(N) O(N) - - 指定した列挙型の列挙型を 1 つの連結された列挙型として結合します。
次の値を含む - - - - O(log(N)) セットに指定された要素がある場合は "true" を返します。
containsKey - - - O(log(N)) - 要素がマップのドメイン内にあるかどうかをテストします。
count - - - - O(N) セット内の要素数を返します。
countBy - - O(N) - - シーケンスの各要素にキー生成関数を適用し、一意のキーと元のシーケンスでのその出現回数を生成するシーケンスを返します。
copy O(N) - O(N) - - コレクションをコピーします。
create O(N) - - - - 最初はすべてが指定された値である要素全体の配列を作成します。
delay - - O(1) - - シーケンスの指定された遅延指定に基づいて構築されたシーケンスを返します。
相違点 - - - - O(M*log(N)) 1 つ目のセットから削除された、2 つ目のセットの要素を含む新しいセットを返します。
distinct O(1)* エントリに対する汎用ハッシュと等価比較に従って、重複するエントリを含まないシーケンスを返します。 要素がシーケンス内で複数回出現する場合、後で出現する項目は破棄されます。
distinctBy O(1)* 指定されたキー生成関数が返すキーに対する汎用ハッシュと等価比較に従って、重複するエントリを含まないシーケンスを返します。 要素がシーケンス内で複数回出現する場合、後で出現する項目は破棄されます。
空 O(1) O(1) O(1) O(1) O(1) 空のコレクションを作成します。
exists O(N) O(N) O(N) O(log(N)) O(log(N)) シーケンスの要素が、指定された述語を満たすかどうかをテストします。
exists2 O(min(N,M)) - O(min(N,M)) 入力シーケンスの対応する要素のペアが、指定された述語を満たすかどうかをテストします。
fill O(N) 配列の要素の範囲を、指定された値に設定します。
filter O(N) O(N) O(N) O(N) O(N) 指定された述語が true を返すコレクションの要素のみを含む新しいコレクションを返します。
検索 O(N) O(N) O(N) O(log(N)) - 指定された関数が true を返す最初の要素を返します。 こうした要素が存在しない場合は、System.Collections.Generic.KeyNotFoundException を返します。
findIndex O(N) O(N) O(N) - - 指定された述語を満たす配列内の最初の要素のインデックスを返します。 述語を満たす要素がない場合、System.Collections.Generic.KeyNotFoundException を発生させます。
findKey - - - O(log(N)) - コレクション内の各マッピングで関数を評価し、関数が true を返す最初のマッピングのキーを返します。 このような要素が存在しない場合、この関数は System.Collections.Generic.KeyNotFoundException を発生させます。
fold O(N) O(N) O(N) O(N) O(N) コレクションの各要素に関数を適用し、計算を通じてアキュムレータ引数を処理します。 入力関数が f で、要素が i0...iN の場合、この関数は f (... (f s i0)...) iN を計算します。
fold2 O(N) O(N) - - - 2 つのコレクションの対応する要素に関数を適用し、計算を通じてアキュムレータ引数を処理します。 コレクションのサイズは同じである必要があります。 入力関数が f で、要素が i0...iN および j0...jN の場合、この関数は、f (... (f s i0 j0)...) iN jN を計算します。
foldBack O(N) O(N) - O(N) O(N) コレクションの各要素に関数を適用し、計算を通じてアキュムレータ引数を処理します。 入力関数が f で、要素が i0...iN の場合、この関数は f i0 (...(f iN s)) を計算します。
foldBack2 O(N) O(N) - - - 2 つのコレクションの対応する要素に関数を適用し、計算を通じてアキュムレータ引数を処理します。 コレクションのサイズは同じである必要があります。 入力関数が f で、要素が i0...iN および j0...jN の場合、この関数は f i0 j0 (...(f iN jN s)) を計算します。
forall O(N) O(N) O(N) O(N) O(N) コレクションのすべての要素が、指定された述語を満たすかどうかをテストします。
forall2 O(N) O(N) O(N) - - コレクションのすべての要素が、指定された述語をペアで満たすかどうかをテストします。
get / nth O(1) O(N) O(N) - - そのインデックスが指定されている、コレクションから要素を返します。
head - O(1) O(1) - - コレクションの最初の要素を返します。
Init O(N) O(N) O(1) - - ディメンションが指定されたコレクションと、要素を計算するジェネレーター関数を作成します。
initInfinite - - O(1) - - 反復処理時に、指定された関数を呼び出して、連続する要素を返すシーケンスを生成します。
intersect - - - - O(log(N)*log(M)) 2 つのセットの積集合を計算します。
intersectMany - - - - O(N1*N2...) セットのシーケンスの積集合を計算します。 シーケンスを空にすることはできません。
isEmpty O(1) O(1) O(1) O(1) - コレクションが空の場合に、true を返します。
isProperSubset - - - - O(M*log(N)) 1 番目のセットのすべての要素が 2 番目のセットに含まれ、2 番目のセットの少なくとも 1 つの要素が 1 番目のセットに含まれていない場合、true を返します。
isProperSuperset - - - - O(M*log(N)) 2 番目のセットのすべての要素が 1 番目のセットに含まれ、1 番目のセットの少なくとも 1 つの要素が 2 番目のセットに含まれていない場合、true を返します。
isSubset - - - - O(M*log(N)) 1 番目のセットのすべての要素が 2 番目のセットに含まれている場合、true を返します。
isSuperset - - - - O(M*log(N)) 2 番目のセットのすべての要素が 1 番目のセットに含まれている場合、true を返します。
iter O(N) O(N) O(N) O(N) O(N) 指定された関数をコレクションの各要素に適用します。
iteri O(N) O(N) O(N) - - 指定された関数をコレクションの各要素に適用します。 関数に渡される整数は、要素のインデックスを示します。
iteri2 O(N) O(N) - - - 2 つの配列内の一致するインデックスから抽出された要素のペアに、指定された関数を適用します。 関数に渡される整数は、要素のインデックスを示します。 2 つの配列は同じ長さにする必要があります。
iter2 O(N) O(N) O(N) - - 2 つの配列内の一致するインデックスから抽出された要素のペアに、指定された関数を適用します。 2 つの配列は同じ長さにする必要があります。
last O(1) O(N) O(N) - - 適用可能なコレクション内の最後の項目を返します。
length O(1) O(N) O(N) - - コレクション内の要素の数を返します。
map O(N) O(N) O(1) - - 指定された関数を配列の各要素に適用した結果を要素とするコレクションを構築します。
map2 O(N) O(N) O(1) - - 指定された関数を 2 つのコレクションの対応する要素にペアで適用した結果を要素とするコレクションを構築します。 2 つの入力配列は同じ長さにする必要があります。
map3 - O(N) - - - 指定された関数を 3 つのコレクションの対応する要素に同時に適用した結果を要素とするコレクションを構築します。
mapi O(N) O(N) O(N) - - 指定された関数を配列の各要素に適用した結果を要素とする配列を構築します。 関数に渡される整数インデックスは、変換される要素のインデックスを示します。
mapi2 O(N) O(N) - - - 指定された関数を 2 つのコレクションの対応する要素にペアで適用し、さらに要素のインデックスを渡した結果を要素とするコレクションを構築します。 2 つの入力配列は同じ長さにする必要があります。
max O(N) O(N) O(N) - - max 演算子を使用して比較し、コレクション内の最大の要素を返します。
maxBy O(N) O(N) O(N) - - 関数の結果に対して、max 演算子を使用して比較し、コレクション内の最大の要素を返します。
maxElement - - - - O(log(N)) セットで使用されている順序に従って、セット内の最大の要素を返します。
分 O(N) O(N) O(N) - - min 演算子を使用して比較し、コレクション内の最小の要素を返します。
minBy O(N) O(N) O(N) - - 関数の結果に対して、min 演算子を使用して比較し、コレクション内の最小の要素を返します。
minElement - - - - O(log(N)) セットで使用されている順序に従って、セット内の最小の要素を返します。
ofArray - O(N) O(1) O(N) O(N) 指定された配列と同じ要素を含むコレクションを作成します。
ofList O(N) - O(1) O(N) O(N) 指定されたリストと同じ要素を含むコレクションを作成します。
ofSeq O(N) O(N) - O(N) O(N) 指定されたシーケンスと同じ要素を含むコレクションを作成します。
pairwise - - O(N) - - 入力シーケンス内の各要素 (2 番目の要素の先行要素としてのみ返される最初の要素は除かれます) とその先行要素のシーケンスを返します。
partition O(N) O(N) - O(N) O(N) コレクションを 2 つのコレクションに分割します。 最初のコレクションには、指定された述語によって true が返される要素が含まれ、2 番目のコレクションには、指定された述語によって false が返される要素が含まれます。
permute O(N) O(N) - - - 指定された順列に従ってすべての要素を並べ変えた配列を返します。
pick O(N) O(N) O(N) O(log(N)) - 指定された関数を一連の要素に適用し、関数が Some を返す最初の結果を返します。 関数が Some を返さない場合 System.Collections.Generic.KeyNotFoundException が発生します。
readonly - - O(N) - - 指定されたシーケンス オブジェクトにデリゲートするシーケンス オブジェクトを作成します。 この操作により、型キャストは元のシーケンスを再検出および再処理できなくなります。 たとえば、配列が指定されている場合、返されるシーケンスは配列の要素を返しますが、返されたシーケンス オブジェクトを配列にキャストすることはできません。
reduce O(N) O(N) O(N) - - コレクションの各要素に関数を適用し、計算を通じてアキュムレータ引数を処理します。 この関数は、まず、最初の 2 つの要素に関数を適用し、3 番目の要素と共にこの結果を関数に渡します。以降も同じ操作が続きます。 関数は、最終結果を返します。
reduceBack O(N) O(N) - - - コレクションの各要素に関数を適用し、計算を通じてアキュムレータ引数を処理します。 入力関数が f で、要素が i0...iN の場合、この関数は f i0 (...(f iN-1 iN)) を計算します。
remove - - - O(log(N)) O(log(N)) マップのドメインから要素を削除します。 要素が存在しない場合、例外は発生しません。
replicate - O(N) - - - 指定した値に設定されたすべての要素を使用して、指定した長さのリストを作成します。
rev O(N) O(N) - - - 要素を逆順にした新しいリストを返します。
scan O(N) O(N) O(N) - - コレクションの各要素に関数を適用し、計算を通じてアキュムレータ引数を処理します。 この操作では、関数を 2 番目の引数とリストの最初の要素に適用します。 次に、操作によって、この結果が 2 番目の要素と共に関数に渡されます。以降も同様です。 最後に、操作によって、中間結果と最終結果のリストが返されます。
scanBack O(N) O(N) - - - foldBack 操作に似ていますが、中間と最終の両方の結果が返されます。
singleton - - O(1) - O(1) 項目を 1 つだけ生成するシーケンスを返します。
set O(1) - - - - 配列の要素を指定された値に設定します。
skip - - O(N) - - 基になるシーケンスの N 個の要素をスキップし、シーケンスの残りの要素を生成するシーケンスを返します。
skipWhile - - O(N) - - 反復処理時に、指定された述語が true を返したときに、基になるシーケンスの要素をスキップし、シーケンスの残りの要素を生成するシーケンスを返します。
sort O(N*log(N)) 平均

O(N^2) worst case		 O(N*log(N)) O(N*log(N)) - - 要素の値でコレクションを並べ替えます。 要素は compare を使用して比較されます。
sortBy O(N*log(N)) 平均

O(N^2) worst case		 O(N*log(N)) O(N*log(N)) - - 指定されたプロジェクションによって提供されるキーを使用して、指定されたリストを並べ替えます。 キーは compare を使用して比較されます。
sortInPlace O(N*log(N)) 平均

O(N^2) worst case		 - - - - 配列にインプレースで変更を加え、指定された比較関数を使用して、配列の要素を並べ替えます。 要素は compare を使用して比較されます。
sortInPlaceBy O(N*log(N)) 平均

O(N^2) worst case		 - - - - 配列にインプレースで変更を加え、キーに対して指定されたプロジェクションを使用して、配列の要素を並べ替えます。 要素は compare を使用して比較されます。
sortInPlaceWith O(N*log(N)) 平均

O(N^2) worst case		 - - - - 配列にインプレースで変更を加え、指定された比較関数を順序として使用して、配列の要素を並べ替えます。
sortWith O(N*log(N)) 平均

O(N^2) worst case		 O(N*log(N)) - - - コレクションの要素を並べ替えます。指定された比較関数が順序として使用され、新しいコレクションが返されます。
sub O(N) - - - - 開始インデックスと長さによって指定された、指定済みサブ範囲を含む配列を構築します。
Sum O(N) O(N) O(N) - - コレクション内の要素の合計を返します。
sumBy O(N) O(N) O(N) - - 関数をコレクションの各要素に適用して生成される結果の合計を返します。
tail - O(1) - - - 最初の要素を含まないリストを返します。
take - - O(N) - - 指定した数までシーケンスの要素を返します。
takeWhile - - O(1) - - 反復処理時に、指定された述語が true を返したときに基になるシーケンスの要素を生成し、それ以上要素を返さないシーケンスを返します。
toArray - O(N) O(N) O(N) O(N) 指定したコレクションから配列を作成します。
toList O(N) - O(N) O(N) O(N) 指定したコレクションからリストを作成します。
toSeq O(1) O(1) - O(1) O(1) 指定したコレクションからシーケンスを作成します。
truncate - - O(1) - - 列挙された場合に N 個を超える要素を返さないシーケンスを返します。
tryFind O(N) O(N) O(N) O(log(N)) - 指定された述語を満たす要素を検索します。
tryFindIndex O(N) O(N) O(N) - - 指定された述語を満たす最初の要素を検索し、一致する要素のインデックスを返します。そのような要素が存在しない場合は None を返します。
tryFindKey - - - O(log(N)) - 指定された述語を満たすコレクション内の最初のマッピングのキーを返します。そのような要素が存在しない場合は None を返します。
tryPick O(N) O(N) O(N) O(log(N)) - 指定された関数を一連の要素に適用し、関数が何らかの値について Some を返す最初の結果を返します。 そのような要素が存在しない場合は、操作によって None が返されます。
unfold - - O(N) - - 指定された計算によって生成された要素を含むシーケンスを返します。
union - - - - O(M*log(N)) 2 つのセットの和集合を計算します。
unionMany - - - - O(N1*N2...) セットのシーケンスの和集合を計算します。
unzip O(N) O(N) O(N) - - ペアのリストを 2 つのリストに分割します。
unzip3 O(N) O(N) O(N) - - 3 要素のリストを 3 つのリストに分割します。
windowed - - O(N) - - 入力シーケンスから抽出される、含まれる要素のスライディング ウィンドウを生成するシーケンスを返します。 各ウィンドウは、新しい配列として返されます。
zip O(N) O(N) O(N) - - 2 つのコレクションをペアのリストに結合します。 2 つのリストの長さは同じである必要があります。
zip3 O(N) O(N) O(N) - - 3 つのコレクションを 3 要素のリストに結合します。 リストの長さは同じである必要があります。

関連項目