从地图派生关联容器

Question

containers 包中的 Data.Map.Lazy 模块中有 Map 类型（关联数组）：

data Map k a = ...

我可以从这个类型推导出 Set:

import qualified Data.Map.Lazy as Map
newtype Set a = Set (Map.Map a ())

但是同一个包中的Data.Set模块没有。是因为性能问题吗？

此外，我可以通过类似的方法导出 C++ 的 std::multiset 和 std::multimap 等价物：

type Occur = Int
newtype MultiSet a = MultiSet (Map.Map a Occur)
newtype MultiMap k a = MultiMap (Map.Map k (MultiSet a))

因为 containers 包没有提供这些类型，我实际上是在使用我自己的实现来实现这些类型。

优点是很容易为这些类型实现实用程序，例如 C++ 的 size、insert 和 erase 的（纯功能）等价物。例如：

instance Foldable MultiSet where
    foldMap f (MultiSet xs) = Map.foldMapWithKey (\x o -> stimes o (f x)) xs
    toList = toAscList
    null (MultiSet xs) = null xs
    length = size

size :: MultiSet a -> Occur
size (MultiSet xs) = sum xs

insert :: Ord a => a -> MultiSet a -> MultiSet a
insert x = insertMany x 1

insertMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a
insertMany x n (MultiSet xs) = MultiSet (Map.alter (\maybeo -> case maybeo of
    Nothing -> Just n
    Just m -> maybeClampNeg (m + n)
    ) x xs)

clampNeg :: Occur -> Occur
clampNeg n = if n < 0 then 0 else n

maybeClampNeg :: Occur -> Maybe Occur
maybeClampNeg n = case clampNeg n of
    0 -> Nothing
    n' -> Just n'

delete :: Ord a => a -> MultiSet a -> MultiSet a
delete x = deleteMany x 1

deleteMany :: Ord a => a -> Occur -> MultiSet a -> MultiSet a
deleteMany x n (MultiSet xs) = MultiSet (Map.update (maybeClampNeg . subtract n) x xs)

这些实现会不会有性能问题？

Answer 1

Set 类型未实现为 Map k ()，因为在该实现中每个条目还携带值 ()，这是纯粹的开销。

您的多重集实现与 one in Hackage 基本相同。

另一方面，

This Multimap 被实现为列表映射。这并不意味着您的建议有任何问题；事实上，对于某些用例来说它可能更好。

然而，这确实说明了更广泛的设计问题； Haskell 中像这样的数据结构的可组合性意味着在实践中创建这样的结构比尝试创建包含嵌套容器的所有可能组合的库更容易。

从地图派生关联容器

Deriving associative containers from map

dictionary

haskell

set

multimap

multiset