Map on Map<'a, int>

Question

I have the following type :

type MultiSet<'a when 'a: comparison> = MSet of Map<'a, int>

and I now want to declare af map function for this type with the signature :

('a -> 'b) -> Multiset<'a> -> Multiset<'b> when 'a : comparison and 'b : comparison

I have tried :

let map m ms =
    match ms with
    | MSet s -> MSet ( Map.map (fun key value -> m key) s )

But that it has the signature :

('a -> int) -> Multiset<'a> -> Multiset<'a> when 'a : comparison

What is wrong with my implementation when I want the first mentioned function signature?

Answer 1

Map.map maps values, not keys. And with good reason: it can't just go and plug the mapped keys instead of the original ones - they might not fit. Heck, they might not even be unique for all Map.map knows!

If you want to construct a map with different keys, you'll have to take it apart as a sequence, convert it, then construct another Map from it:

let map m (MSet s) =
  MSet ( Map.ofSeq <| seq { for KeyValue (key, value) in s -> m key, value } )

This implementation has your required signature.

(also, notice how you don't have to do match, you can include the pattern right in parameter declaration)

Beware that this implementation does nothing for validating the new keys: for example, if they turn out to be non-unique, some counts will be lost. I leave this as an exercise for the reader.