How do I intersect two Maps by their keys in F#

Question

I want to interesct two F# Maps, which have common keys, into a Map that has the common keys and a tuple of both values as it's value.

i.e the signature is something like:

Map<K, T1> -> Map<K, T2> -> Map<K, T1 * T2>

Any ideas of an easy functional & performant way to do it?

I know I can intersect the sets of keys and then build out a new map, I'd just like to do something that doesn't feel so dirty...

Answer 1

I had a similar problem before and finally solved it like this:

let intersect a b = Map (seq {
    for KeyValue(k, va) in a do
        match Map.tryFind k b with
        | Some vb -> yield k, (va, vb)
        | None    -> () })

Answer 2

One approach is to implement this in terms of Map.fold:

module Map =
    let intersect (m1:Map<'K, 'V1>) (m2:Map<'K, 'V2>) =
        (Map.empty, m1) ||> Map.fold (fun acc k v1 ->
            (acc, Map.tryFind k m2) ||> Option.fold (fun acc v2 ->
                acc |> Map.add k (v1, v2)))

Answer 3

I posted this prematurely and deleted it, as I'm unsure whether this counts as just intersecting the keys... but I guess it can't hurt to undelete it, since it's fairly short:

let intersect otherMap =
    Map.filter (fun k _ -> Map.containsKey k otherMap)
    >> Map.map (fun k v1 -> v1, otherMap.[k])

Edit Without intermediate map, via a sequence:

let intersect otherMap =
    Map.toSeq >> Seq.choose (fun (k, v) ->
        Map.tryFind k otherMap |> Option.map (fun v2 -> v, v2))
    >> Map.ofSeq