haskell - Haskell的Data.Vector没有提供集合运算符，原因是什么

Question

我的应用程序涉及大量数组操作(例如 log(1) 索引)，因此 Data.Vector和 Data.Vector.Unboxed优先于Data.List 。 它还涉及许多集合操作(​​例如 intersectBy)，但是 Data.Vector 不提供这些操作。

每个函数都可以像 Data.List 中那样用 3-4 行来实现。 有什么原因它们都没有用 Data.Vector 实现吗？我只能推测。也许出于性能原因，不鼓励在 Data.Vector 中进行集合操作，即 intersectBy 首先通过列表理解生成交集，然后将列表转换为 Data.Vector？

Answer 1

我认为它丢失了，因为未排序、不可变数组的交集必须具有Ω(n*m)的最坏情况运行时间，而不使用额外的空间和Data.Vector 针对性能进行了优化。如果您愿意，您可以自己编写该函数:

import Data.Vector as V

intersect :: Eq a => V.Vector a -> V.Vector a -> V.Vector a
intersect x = V.filter (`V.elem` x)

或者使用a temporary set data structure达到预期的 O(n + m) 复杂度:

import Data.HashSet as HS

intersect :: (Hashable a, Eq a) => V.Vector a -> V.Vector a -> V.Vector a
intersect x = V.filter (`HS.member` set)
    where set = HS.fromList $ V.toList x

如果您能负担得起额外的内存使用量，也许您可​​以为数据使用某种聚合类型，例如用于快速随机访问的数组和用于快速随机访问的哈希特里树，例如 Data.HashSet成员资格检查并始终使两个容器保持最新。这样你就可以将交集的渐近复杂度降低到类似 O(min(n, m))