RemoveAll from map in F#

Question

C#:

In C# I have something like this:

IImmutableDictionary<string, string> map = new Dictionary<string, string>
{
    {"K1", "V1"},
    {"K2", "V2"},
    {"K3", "V3"},
}.ToImmutableDictionary();

IEnumerable<string> keys = new[] {"K1,K3"};

map = map.RemoveRange(keys);

I assume that the method ImmutableDictionary<K,V>.RemoveRange Method (IEnumerable<K>) was introduced since it is much more efficient than series of Remove(K)calls. It creates the resulting immutable object only once instead of once for every element from keys to remove.

F#:

What is the best way to achieve the same in F#. I came up with this recursive solution:

let rec removeAll (map:Map<string, string>,  keys:list<string>) =
    match keys with
        | [] -> map
        | _ -> removeAll(map.Remove(keys |> Seq.head), keys.Tail)     

but I doubt it is as efficient as the RemoveRange from above.

Questions:

1. What is the most efficient equivalent of RemoveAll in F#?
2. Do you think F# recursion optimization is going to compile to something equally efficient?

Answer 1

Map.filter will be useful here and will presumably prevent creating many intermediate maps, though to use it efficiently for many keys you'll want to put the keys into a set first.

let removeAll keys map =
    let keySet = set keys
    map |> Map.filter (fun k _ -> k |> keySet.Contains |> not)

[ 1, 2
  3, 4
  5, 6
  7, 8 ]
|> Map
|> removeAll [1; 5]
// map [(3, 4); (7, 8)]

This is small enough that it's potentially not worth breaking out into a function. For example in a case where you have an array of no more than 10 keys, then it may be less efficient to make a set out of them first.

Your current function is tail-recursive so it should be optimised in terms of not creating multiple stack frames, however you can write it a bit more simply by using pattern matching on the list:

let rec removeAll (map:Map<_,_>,  keys:list<_>) =
    match keys with
        | [] -> map
        | key :: rest -> removeAll(map.Remove(key), rest)

Also note that it can automatically be made generic by either removing type annotations or replacing parts of them with _, telling the compiler to infer the type.