List.filter 和 List.mem [已关闭]

Question

我在理解这条特定的线路时遇到问题

let lst = ["a", "b", "c"];
List.filter (fun (a, _b) -> not (List.mem a lst)) assoc

Answer 1

List.filter

采用一个函数，该函数依次获取列表中的每个元素并返回一个布尔值。如果布尔值为 true，则该元素是返回列表的一部分。

在这种情况下，

assoc

中第一个元素不在

lst

中的任何元组都会作为新列表返回。

考虑：

let lst = ["a"; "b"; "c"]
let assoc = [("a", 42); ("g", 27)]

let filtered = List.filter (fun (a, _) -> not @@ List.mem a lst) assoc
(* [("g", 27)] *)

请注意，这不会很好地扩展，因为

assoc

上的每次迭代都需要完全遍历

lst

。如果我们将

lst

转换为 集合，那么

mem

的复杂度为 O(log n)，而不是 O(n)。

module StringSet = Set.Make (String)

let lst = ["a"; "b"; "c"]
let assoc = [("a", 42); ("g", 27)]

let s = StringSet.of_list lst

let filtered = List.filter (fun (a, _) -> not @@ StringSet.mem a s) assoc