使用 OCaml 查找两个列表中不重复的公共元素

Question

我试图在OCaml中实现一个rec函数，但我不知道如何过滤掉结果列表中重复的公共元素，这是我的实现：

let rec common twolists =
    match twolists with
    | (x, y) ->
         match x with
         | [] -> []
         | s :: ss ->
             if memberof (s, y) then
                 s :: common (ss, y)
             else 
                 common (ss, y)
;;

我在两个列表中找到了所有共同元素，但我不知道如何做到没有任何重复。

Answer 1

一个想法是替换这个表达式：

s :: common (ss, y)

有一些更复杂的事情。

如果

s

已经是

common (ss, y)

的成员，您不想再次添加。因此，您可以根据

s

是否已经存在，用两种情况替换此表达式。

为此，您可能需要使用

let

：

let rest = common (ss, y) in
. . .

（请注意，如果这是列表可能会变长的生产代码，您将希望避免重复调用

memberof

。您最终可能会使用树。即集合。然后结果是一个完全简单的集合交集。）

Answer 2

首先，让我们简化您的代码，因为我们可以直接在顶级匹配表达式中的

x

上进行模式匹配。

let rec common twolists =
  match twolists with
  | ([], _) -> []
  | (s::ss, y) ->
    if memberof (s, y) then
      s :: common (ss, y)
    else 
      common (ss, y)

现在，让我们使用累加器，不要将两个列表作为元组传递，因为这对于 OCaml 来说不是很惯用。奖励：这现在是尾递归。

let rec common lst1 lst2 acc =
  match lst1, lst2 with
  | ([], _) -> List.rev acc
  | (s::ss, y) ->
    if memberof (s, y) then
      common ss y (s :: acc)
    else 
      common ss y acc

我们可能想通过使其成为本地绑定函数来隐藏此累加器。

let common lst1 lst2 =
  let rec common' lst1 lst2 acc =
    match lst1, lst2 with
    | ([], _) -> List.rev acc
    | (s::ss, y) ->
      if memberof (s, y) then
        common' ss y (s :: acc)
      else 
        common' ss y acc
  in
  common' lst1 lst2 []

但诀窍是一遍又一遍地在

memberof

中进行查找。如果我们不需要保留顺序，那么如果两个列表都已排序，这会容易得多。

let common lst1 lst2 =
  let rec common' lst1 lst2 acc =
    match lst1, lst2 with
    | ([], _) -> List.rev acc
    | (s::ss, y) ->
      if memberof (s, y) then
        common' ss y (s :: acc)
      else 
        common' ss y acc
  in
  List.(
    common' (sort compare lst1) (sort compare lst2) []
  )

现在如果我们这样称呼：

common [1; 4; 4; 3; 6; 2] [5; 7; 2; 6; 4; 4]

我们真的在呼唤：

common' [1; 2; 3; 4; 4; 6] [2; 4; 4; 5; 6; 7]

知道我们已经排序，事情就变得简单了。让我们匹配

lst1

、

lst2

和

acc

。因为

acc

是“向后”构建的，所以我们可以轻松地对添加到其中的最后一个元素进行模式匹配以检查重复项。

let common lst1 lst2 = 
  let rec common' lst1 lst2 acc =
    match lst1, lst2, acc with
    | [], _, _  
    | _, [], _ -> List.rev acc
    | x::xs, y::ys, z::_ when x = y && x = z -> common' xs ys acc
    | x::xs, y::ys, _ when x = y -> common' xs ys (x :: acc)
    | x::xs, y::_, _ when x < y -> common' xs lst2 acc
    | _, _::ys, _ -> common' lst1 ys acc
  in
  common' 
    (List.sort compare lst1) 
    (List.sort compare lst2)
    []

测试：

# common [1; 5; 2; 3; 3; 9; 0] [0; 3; 1; 7; 3; 8];;
- : int list = [0; 1; 3]

如果我们分解一下：

common [1; 5; 2; 3; 3; 9; 0] [0; 3; 1; 7; 3; 8]
common' [0; 1; 2; 3; 3; 5; 9] [0; 1; 3; 3; 7; 8] []
common' [1; 2; 3; 3; 5; 9] [1; 3; 3; 7; 8] [0]
common' [2; 3; 3; 5; 9] [3; 3; 7; 8] [1; 0]
common' [3; 3; 5; 9] [3; 3; 7; 8] [1; 0]
common' [3; 5; 9] [3; 7; 8] [3; 1; 0]
common' [5; 9] [7; 8] [3; 1; 0]
common' [9] [7; 8] [3; 1; 0]
common' [9] [8] [3; 1; 0]
common' [9] [] [3; 1; 0]
List.rev [3; 1; 0]
[0; 1; 3]

当然，我们最终可以意识到这是一个集合交集并利用

Set

模块。

# let common lst1 lst2 =
    let open Set.Make (Int) in
    let set1 = of_list lst1 in
    let set2 = of_list lst2 in
    set1 |> inter set2 |> to_list;;
val common : int list -> int list -> int list = <fun>
# common [1; 5; 2; 3; 3; 9; 0] [0; 3; 1; 7; 3; 8];;
- : int list = [0; 1; 3]