找到不重复的对列表的并集

问题描述 投票：0回答：4

如果两个键匹配，则将具有最高值的对添加到列表中。 例如，

[("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
4个回答
2
投票

一种方法是将列表转换为地图，然后使用 

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

使用 

Core
或 
Core_kernel
可以让您通过 
Tuple
模块的 
compare
功能来简化它：

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
0
投票

您的函数正在处理单对。从整个配对列表的角度进行更高层次的思考可能会有所帮助。

获得所需结果的一种方法（在我看来）是附加两个列表，然后按键（作为主排序键）然后按降序值（作为辅助排序键）对结果列表进行排序。之后，您可以应用“uniq”函数来抑制除每个键第一次出现之外的所有键。

您说无论如何您都计划对列表进行排序。所以唯一的新东西就是“uniq”函数。事实上，如果您正确定义比较，您可能可以使用 

List.sort_uniq
来实现此目的。如果这不起作用，您可以编写自己的“uniq”函数（在移动窗口中一次查看列表的两个元素）。

0
投票

您可以使用 

Map.Make(String)
作为累加器。

let select_max =
  let module StrMap = Map.Make(String) in
  let rec process acc = function 
    | ((k, v) :: t) :: src ->
        let acc = match StrMap.find_opt k acc with
          | Some vmax when vmax >= v -> acc
          | Some _ | None -> acc |> StrMap.remove k
                                 |> StrMap.add k v in
        process acc (t :: src) 
    | [] :: src -> process acc src
    | [] -> StrMap.bindings acc in
  process StrMap.empty

let test = select_max
    [ ["a", 7; "a", 9; "a", 1];
      ["a", 1; "b", 5; "c", 7];
      ["c", 5; "c", 5; "b", 7]
    ]


val select_max : (String.t * int) list list -> (String.t * int) list = <fun>

val test : (String.t * int) list = [("a", 9); ("b", 7); ("c", 7)]

0
投票

使用 

Map.Make (String)
的想法是一个很棒的想法，但是可以使用 
StrMap.update
简化演示的方法，这样就无需显式确定某个键是否存在以及删除和添加它。

# let lst1 = [("a",1);("a",4);("b",2)];;
val lst1 : (string * int) list = [("a", 1); ("a", 4); ("b", 2)]
# let lst2 = [("a",5);("b",1);("c",3)];;
val lst2 : (string * int) list = [("a", 5); ("b", 1); ("c", 3)]
# let lst3 = lst1 @ lst2;;
val lst3 : (string * int) list =
  [("a", 1); ("a", 4); ("b", 2); ("a", 5); ("b", 1); ("c", 3)]
# lst3 
  |> List.fold_left 
       (fun m (k, v) -> 
          m |> StrMap.update k 
            (function
             | Some v' as orig when v' >= v -> orig
             | _ -> Some v)) 
       StrMap.empty 
  |> StrMap.bindings;;
- : (string * int) list = [("a", 5); ("b", 2); ("c", 3)]

出于教学目的，我们可以编写类似的命令式方法。

# let m = ref StrMap.empty in
  lst3 |> List.iter 
    (fun (k, v) -> 
       m := StrMap.update k 
         (function 
          | Some v' as orig when v' >= v -> orig 
          | _ -> Some v) 
         !m);
  StrMap.bindings !m;;
- : (string * int) list = [("a", 5); ("b", 2); ("c", 3)]

不过，如果我们意识到使用 

StrMap.of_list
会获取元组列表并将其转换为 
StrMap.t
值，我们可以做得比这些方法更好。唯一的问题是，这只会保留每个键的 last 值，而不是 greatest 值。

幸运的是，我们可以使用排序将最大值放在最后。

# let lst1 = [("a",1);("a",4);("b",2)] in
  let lst2 = [("a",5);("b",1);("c",3)] in
  let lst3 = lst1 @ lst2 in
  let sort_by f lst = List.sort (fun a b -> compare (f a) (f b)) lst in
  let open Map.Make (String) in
  lst3
  |> sort_by snd
  |> of_list
  |> to_list;;
- : (string * int) list = [("a", 5); ("b", 2); ("c", 3)]
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.