compare.fs

type CompareResult<'a, 'b> =
  | FoundPair of 'a * 'b
  | UnmatchedLHS of 'a
  | UnmatchedRHS of 'b

[<RequireQualifiedAccess>]
module ListCompare =
  let compare xsKeySelector ysKeySelector xs ys =
    let xs =
      xs
      |> Seq.toList
      |> List.map (fun x -> x, xsKeySelector x)
      |> List.sortBy snd

    let ys =
      ys
      |> Seq.toList
      |> List.map (fun y -> y, ysKeySelector y)
      |> List.sortBy snd

    (xs, ys)
    |> List.unfold (function
         | [], [] -> None
         | (x, mx) :: xs, ((_, my) :: _ as ys) when mx < my -> Some(UnmatchedLHS x, (xs, ys))
         | (x, _) :: xs, [] -> Some(UnmatchedLHS x, (xs, []))
         | ((_, mx) :: _ as xs), (y, my) :: ys when my < mx -> Some(UnmatchedRHS y, (xs, ys))
         | [], (y, _) :: ys -> Some(UnmatchedRHS y, ([], ys))
         | (x, _) :: xs, (y, _) :: ys -> Some(FoundPair(x, y), (xs, ys)))