从F#的映射中删除所有项

Question

C#：

在C#中，我有这样的代码：

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

我假设引入了方法ImmutableDictionary<K,V>.RemoveRange Method (IEnumerable<K>)，因为它比一系列Remove(K)调用更有效率。它仅在创建结果不可变对象时被创建一次，而不是针对从keys到删除的每个元素都被创建一次。 F#： 有什么办法可以以相同的方式实现中的操作吗？我想出了这个递归解决方案：

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

但我怀疑它的效率是否像上面的RemoveRange一样高。

问题：

1. F#中最有效的RemoveAll等效方法是什么？
2. 您认为F#递归优化是否会编译成同样高效的东西？

- George Mamaladze

---

有什么理由不使用C#中的RemoveRange吗？ - Camilo Terevinto

据我所知，F#的Map<K,V>没有RemoveRange方法，因此在这种情况下，我必须先将其转换为ImmutableDictionary<K,V>，然后再进行转换。 - George Mamaladze

Answer 1

Map.filter在这里将很有用，它可以避免创建许多中间映射，但是如果要高效地使用它处理许多键，则需要先将键放入集合中。

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

这段代码很短，可能不值得拆分成一个函数。例如，当你只有不超过10个键的数组时，先将它们转换为集合可能会更加低效。

你当前的函数是尾递归的，因此在创建多个堆栈帧方面应该进行了优化，但是你可以通过对列表进行模式匹配来更简单地编写它：

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

还要注意，可以通过删除类型注释或将其部分替换为 _ 来自动使其成为通用类型，告诉编译器推断类型。

- TheQuickBrownFox

---

过滤器解决方案是一个不错的选择，尽管我想知道递归解决方案是否仍会创建中间映射。 - George Mamaladze

是的，递归解决方案将创建中间映射。但是，它们可能会像任何良好的函数不可变数据结构一样使用结构共享。这意味着它们不会在每次迭代中完全复制，但我仍然猜测它比使用 Map.filter 更慢。不过这只是一个猜测！ - TheQuickBrownFox