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...

Adjective

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    -> () })

Fateful

I think this is the most readable one yet... I've implemented it much like @Vandroiy below, but this looks much nicer – Adjective

Thanks, the other proposed solutions have their interesting point too. I remember first I tried with folds but I didn't like the code so I switched to this one which convinced me. It's a personal decision in the end. – Fateful

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)))

Scandinavia

Assuming Map.Count is a constant-time operation, it would be more efficient to fold over the smaller map. – Tap

@Tap : Agreed; I just checked ILSpy and unfortunately it's O(n) as I suspected. :-[ Of course, if performance were a real concern, I suspect Dictionary would be in play here rather than Map to begin with... That said, if the caller knows the relative map sizes in advance, they can document the function that it's more efficient to pass the smaller map as the first argument. – Scandinavia

Nice solution, but match m2.TryFind k with... reads a bit better than using Option.fold IMO and avoids some allocations. – Overwhelm

@Overwhelm : Agreed on the allocations, but readability is in the eye of the beholder – I prefer higher-order functions, personally. ;-] – Scandinavia

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

Tranquillize