我认为这个问题适用于大多数语言，但是我在这里假设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)
```

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