F# 集合类型
通过查看本主题，可以确定最适合特定需求的 F# 集合类型。 这些集合类型与 .NET 中的集合类型（例如 System.Collections.Generic 命名空间中的集合类型）不同，因为 F# 集合类型是从函数编程的角度而不是面向对象的角度设计的。 更具体地说，只有数组集合具有可变元素。 因此，修改集合时会创建已修改集合的实例，而不是更改原始集合。
集合类型在存储对象的数据结构类型上也有所不同。 哈希表、链接列表和数组等数据结构具有不同的性能特征和一组不同的可用操作。
集合类型表
下表显示了 F# 集合类型。
| 类型 | 说明 | 相关链接 |
|---|---|---|
| 列表 | 有序的、不可变的同类型元素系列。 作为链接列表实现。 | 列表 List 模块 |
| 数组 | 固定大小、从零开始、类型相同的连续数据元素的可变集合。 | 数组 Array 模块 Array2D 模块 Array3D 模块 |
| seq | 同类型元素的逻辑系列。 当你拥有一个有序的大型数据集合但不一定希望使用所有元素时，序列特别有用。 系统仅根据需要计算单个序列元素，因此，如果不使用所有元素，序列可以提供比列表更好的性能。 序列由 seq<'T> 类型（IEnumerable<T> 的别名）表示。 因此，任何实现 System.Collections.Generic.IEnumerable<'T> 的 .NET Framework 类型都可以用作序列。 |
序列 Seq 模块 |
| Map | 元素的不可变字典。 通过键访问元素。 | Map 模块 |
| 设置 | 基于二叉树的不可变集，其中比较是 F# 结构比较函数，它可能会对键值使用 System.IComparable 接口的实现。 |
Set 模块 |
函数表
本部分对可用于 F# 集合类型的函数进行比较。 给定函数的计算复杂度，其中 N 是第一个集合的大小，M 是第二个集合（如果有）的大小。 破折号 (-) 表示此函数不可用于集合。 因为序列会延迟计算，所以像 Seq.distinct 这样的函数可能为 O(1)，因为它会立即返回，不过它在枚举时仍会影响序列的性能。
| 函数 | Array | 列出 | 序列 | 映射 | 设置 | 说明 |
|---|---|---|---|---|---|---|
| append | O(N) | O(N) | O(N) | - | - | 返回一个新集合，该集合包含第一个集合的元素，后跟第二个集合的元素。 |
| 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) | - | - | 使用给定的比较函数逐个元素地比较两个序列。 |
| concat | O(N) | O(N) | O(N) | - | - | 将由枚举组成的给定枚举组合为单个串联枚举。 |
| contains | - | - | - | - | 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)) | 返回一个新集，其中的元素是从第一个集中删除第二个集的元素后剩余的元素。 |
| distinct | O(1)* | 根据对条目的泛型哈希和相等比较，返回不包含重复条目的序列。 如果一个元素在序列中出现多次，则放弃后面出现的元素。 | ||||
| distinctBy | O(1)* | 根据对给定键生成函数返回的键的泛型哈希和相等比较，返回不包含重复条目的序列。 如果一个元素在序列中出现多次，则放弃后面出现的元素。 | ||||
| empty | 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 的集合元素。 |
| find | 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。 |
| 折叠 | O(N) | O(N) | O(N) | O(N) | O(N) | 将函数应用于集合的每个元素，通过计算对累加器参数进行线程处理。 如果输入函数为 f 且元素为 i0...iN，则此函数计算 f (... (f s i0)...) iN。 |
| fold2 | O(N) | O(N) | - | - | - | 将函数应用于两个集合的对应元素，通过计算对累加器参数进行线程处理。 集合必须具有相同的大小。 如果输入函数为 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) | - | - | - | 将函数应用于两个集合的对应元素，通过计算对累加器参数进行线程处理。 集合必须具有相同的大小。 如果输入函数为 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)) | 计算两个集的交集。 |
| intersectMany | - | - | - | - | O(N1*N2...) | 计算集序列的交集。 序列不能为空。 |
| isEmpty | O(1) | O(1) | O(1) | O(1) | - | 如果集合为空，则返回 true。 |
| isProperSubset | - | - | - | - | O(M*log(N)) | 如果第一个集的所有元素都在第二个集中，而第二个集的至少一个元素不在第一个集中，则返回 true。 |
| isProperSuperset | - | - | - | - | O(M*log(N)) | 如果第二个集的所有元素都在第一个集中，而第一个集的至少一个元素不在第二个集中，则返回 true。 |
| isSubset | - | - | - | - | O(M*log(N)) | 如果第一个集的所有元素都在第二个集中，则返回 true。 |
| isSuperset | - | - | - | - | O(M*log(N)) | 如果第二个集的所有元素都在第一个集中，则返回 true。 |
| iter | O(N) | O(N) | O(N) | O(N) | O(N) | 将给定函数应用于集合的每个元素。 |
| iteri | O(N) | O(N) | O(N) | - | - | 将给定函数应用于集合的每个元素。 传递给函数的整数表示元素的索引。 |
| iteri2 | O(N) | O(N) | - | - | - | 将给定函数应用于从两个数组中的匹配索引中提取的一对元素。 传递给函数的整数表示元素的索引。 两个数组必须具有相同的长度。 |
| iter2 | O(N) | O(N) | O(N) | - | - | 将给定函数应用于从两个数组中的匹配索引中提取的一对元素。 两个数组必须具有相同的长度。 |
| 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) | - | - | 生成一个集合，其元素是将给定函数成对应用于两个集合的对应元素的结果。 两个输入数组必须具有相同的长度。 |
| map3 | - | O(N) | - | - | - | 生成一个集合，其元素是将给定函数同时应用于三个集合的对应元素的结果。 |
| mapi | O(N) | O(N) | O(N) | - | - | 生成一个数组，其元素是将给定函数应用于数组的每个元素的结果。 传递给函数的整数索引指示正在转换的元素的索引。 |
| mapi2 | O(N) | O(N) | - | - | - | 生成一个集合，其元素是将给定函数成对应用于两个集合的对应元素，同时传递元素索引的结果。 两个输入数组必须具有相同的长度。 |
| 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) | - | - | 返回一个序列，其中包含输入序列中的每个元素及其前导元素，但不包含第一个元素，该元素仅作为第二个元素的前导元素返回。 |
| partition | O(N) | O(N) | - | O(N) | O(N) | 将集合拆分为两个集合。 第一个集合包含给定谓词返回 true 的元素，第二个集合包含给定谓词返回 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) | - | - | 将函数应用于集合的每个元素，通过计算对累加器参数进行线程处理。 此函数首先将函数应用于前两个元素，然后将此结果与第三个元素一起传递给函数，依此类推。 该函数返回最终结果。 |
| reduceBack | O(N) | O(N) | - | - | - | 将函数应用于集合的每个元素，通过计算对累加器参数进行线程处理。 如果输入函数为 f 且元素为 i0...iN，则此函数计算 f i0 (...(f iN-1 iN))。 |
| 删除 | - | - | - | O(log(N)) | O(log(N)) | 从映射域中删除某个元素。 如果该元素不存在，系统不会引发异常。 |
| replicate | - | O(N) | - | - | - | 创建一个指定长度的列表，其中每个元素都设置为给定值。 |
| rev | O(N) | O(N) | - | - | - | 返回一个新列表，其中的元素采用相反的顺序。 |
| scan | O(N) | O(N) | O(N) | - | - | 将函数应用于集合的每个元素，通过计算对累加器参数进行线程处理。 此操作将函数应用于第二个参数和列表的第一个元素。 然后，该操作将此结果与第二个元素一起传递给函数，依此类推。 最后，该操作返回中间结果和最终结果的列表。 |
| scanBack | O(N) | O(N) | - | - | - | 与 foldBack 操作类似，但同时返回中间结果和最终结果。 |
| singleton | - | - | O(1) | - | O(1) | 返回仅包含一个项的序列。 |
| set | O(1) | - | - | - | - | 将数组的元素设置为指定值。 |
| skip | - | - | O(N) | - | - | 返回一个序列，该序列跳过基础序列的 N 个元素，然后包含序列的剩余元素。 |
| skipWhile | - | - | O(N) | - | - | 返回一个序列，该序列在循环访问时跳过基础序列中给定谓词返回 true 的元素，然后包含序列的剩余元素。 |
| sort | O(N*log(N)) 平均值 O(N^2) 最坏情况 |
O(N*log(N)) | O(N*log(N)) | - | - | 按元素值对集合排序。 使用 compare 比较元素。 |
| sortBy | O(N*log(N)) 平均值 O(N^2) 最坏情况 |
O(N*log(N)) | O(N*log(N)) | - | - | 使用给定投影提供的键对给定列表进行排序。 使用 compare 比较键。 |
| sortInPlace | O(N*log(N)) 平均值 O(N^2) 最坏情况 |
- | - | - | - | 通过就地转变数组并使用给定的比较函数，对数组元素进行排序。 使用 compare 比较元素。 |
| sortInPlaceBy | O(N*log(N)) 平均值 O(N^2) 最坏情况 |
- | - | - | - | 通过就地转变数组并对键使用给定的投影，对数组元素进行排序。 使用 compare 比较元素。 |
| sortInPlaceWith | O(N*log(N)) 平均值 O(N^2) 最坏情况 |
- | - | - | - | 通过就地转变数组并使用给定的比较函数作为顺序，对数组元素进行排序。 |
| sortWith | O(N*log(N)) 平均值 O(N^2) 最坏情况 |
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)) | 计算两个集的并集。 |
| unionMany | - | - | - | - | O(N1*N2...) | 计算集序列的并集。 |
| unzip | O(N) | O(N) | O(N) | - | - | 将一个对列表拆分为两个列表。 |
| unzip3 | O(N) | O(N) | O(N) | - | - | 将一个三元组列表拆分为三个列表。 |
| windowed | - | - | O(N) | - | - | 返回一个序列，其中包含从输入序列中提取的包含元素的滑动窗口。 每个窗口都作为一个新数组返回。 |
| zip | O(N) | O(N) | O(N) | - | - | 将两个集合组合成一个对列表。 这两个列表的长度必须相等。 |
| zip3 | O(N) | O(N) | O(N) | - | - | 将三个集合组合成一个三元组列表。 列表的长度必须相等。 |
