Find the union of lists of pairs without duplicates

If two keys, match then the pair with the highest value is added to the list. So for example, [("a",1);("a",4);("b",2)] U [("a",5);("b",1);("c",3)] = [("a",5);("b",2);("c",3)].

I tried creating a function that would compare the given pair to pairs of the other list:

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

This would return the pair with the greatest value, you can assume the list was sorted by descending order prior to calling this function. However, the obvious bug with this function is that if several pairs with the same key have greater values than that of the other list, then they will also be added to the new list.

I am unsure of how to go about doing this correctly. Learning Ocaml

Solution

One way is to convert your lists to maps, and use the Map module's merge function to join them:

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

When creating the map, if you have duplicate keys in the list of pairs being added, the last one is used in the final map - so if your lists are sorted already, you get the highest one. Then the two maps are merged together, and when a key exists in both, the highest value is used.

Or if you can use Jane Street's Base replacement standard library, it has a number of relevant useful functions in its List module:

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

Using Core or Core_kernel lets you simplify it a bit with the Tuple module's compare function:

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

And finally, for good measure, the first algorithm using the Base/Core Map, which has a very different interface than the Stdlib one:

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