从地图派生关联容器

我认为这个问题适用于大多数语言,但是我在这里假设Haskell。

There is Map type (associative array) in Data.Map.Lazy module in containers package:

data Map k a = ...

I could derive Set from this type:

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

But the Data.Set module in the same package doesn't. Is that because of performance issues?

Furthermore, I could derive C++'s std::multiset and std::multimap equivalent by similar method:

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

For the containers package doesn't provide such types, I'm actually using my own implementations for these types.

The advantages were that it was easy to implement utilities for these types, such as (purely functional) equivalents of C++'s size, insert, and erase. For examples:

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)

这些实现中是否会有性能问题?