List.filter and List.mem

Question

I am having a problem understanding this particular line

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

Answer 1

List.filter takes a function that takes each element in the list in turn and returns a boolean. If the boolean value is true, the element is part of the returned list.

In this case, any tuple in assoc whose first element is not in lst is returned as a new list.

Consider:

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

Note that this will not scale well, as each iteration over assoc requires a full traversal of lst. If we convert lst to a set then mem has O(log n) complexity, rather than 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