从地图中导出关联容器

Question

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

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

容器中的Data.Map.Lazy模块 Set 类型没有实现为 Map k () 因为在该实现中，每个条目也携带着一个价值为 ()，这是纯粹的开销。

你的多组实现基本上和你的 一个在Hackage.

该多图另一方面，它是以列表图的形式实现的。这并不意味着你的建议有什么问题；事实上，对于某些用例来说，它可能更好。

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