时间戳

首页 > 解决方案 > 找到没有重复的对列表的并集

ocaml - 找到没有重复的对列表的并集

问题描述

如果两个键匹配，则将具有最高值的对添加到列表中。例如，[("a",1);("a",4);("b",2)]U [("a",5);("b",1);("c",3)]= [("a",5);("b",2);("c",3)]。

我尝试创建一个函数，将给定对与另一个列表对进行比较：

`let max_val (k,v) o_lst =  if (v > (List.assoc k o_lst)) then (k,v) else (k,(List.assoc k o_lst))`

这将返回具有最大值的对，您可以假设列表在调用此函数之前按降序排序。但是，这个函数的一个明显错误是，如果具有相同键的多个对具有比另一个列表更大的值，那么它们也会被添加到新列表中。

我不确定如何正确执行此操作。学习 Ocaml

标签： ocaml

解决方案

一种方法是将列表转换为地图，并使用Map模块的merge功能加入它们：

module StrMap = Map.Make(String)

let list1 = [ "a", 1; "a", 4; "b", 2 ]
let list2 = [ "a", 5; "b", 1; "c", 3 ]

let map1 = List.to_seq list1 |> StrMap.of_seq
let map2 = List.to_seq list2 |> StrMap.of_seq

let max_merge =
  StrMap.merge (fun key x y ->
      match x, y with
      | Some a, None -> Some a
      | None, Some b -> Some b
      | Some a, Some b -> Some (max a b)
      | None, None -> None (* Shouldn't happen but silences a warning. *))

let map3 = max_merge map1 map2
let list3 = StrMap.bindings map3 (* [("a", 5); ("b", 2); ("c", 3)] *)

创建映射时，如果您在添加的对列表中有重复的键，则最后一个将用于最终映射 - 因此，如果您的列表已经排序，您将获得最高的键。然后将这两个映射合并在一起，当两者都存在一个键时，使用最大值。

或者，如果您可以使用 Jane Street 的Base替换标准库，它的List模块中有许多相关的有用功能：

open Base

let list1 = [ "a", 1; "a", 4; "b", 2 ]
let list2 = [ "a", 5; "b", 1; "c", 3 ]

let apply_first (a,_) (b,_) ~f = f a b

let max_merge a b =
  List.merge a b ~compare:(fun (xs, xi) (ys, yi) ->
      let cmp = String.compare xs ys in
      if cmp = 0 then Int.compare xi yi else cmp) |>
    List.remove_consecutive_duplicates ~which_to_keep:`Last
      ~equal:(apply_first ~f:String.equal)

let list3 = max_merge list1 list2 (* [("a", 5); ("b", 2); ("c", 3)] *)

使用Coreor可以让你通过模块的功能Core_kernel稍微简化它：Tuplecompare

open Core

let list1 = [ "a", 1; "a", 4; "b", 2 ]
let list2 = [ "a", 5; "b", 1; "c", 3 ]

let apply_first (a,_) (b,_) ~f = f a b

let max_merge a b =
  List.merge a b ~compare:(Tuple.T2.compare ~cmp1:String.compare ~cmp2:Int.compare) |>
    List.remove_consecutive_duplicates ~which_to_keep:`Last
      ~equal:(apply_first ~f:String.equal)

let list3 = max_merge list1 list2

最后，为了更好地衡量，第一个使用 Base/Core 的算法Map，它的接口与 Stdlib 的接口非常不同：

open Base

let list1 = [ "a", 1; "a", 4; "b", 2 ]
let list2 = [ "a", 5; "b", 1; "c", 3 ]

let list_to_map = Map.of_alist_reduce (module String) ~f:max

let map1 = list_to_map list1
let map2 = list_to_map list2

let max_merge = Map.merge_skewed ~combine:(fun ~key a b -> max a b)

let map3 = max_merge map1 map2
let list3 = Map.to_alist map3

推荐阅读