list - 按 f# 顺序合并两个列表

Question

我有这个代码，它结合了两个列表：

let rec union list1 list2 =
    match list2 with
    | [] -> list1
    | x::xs when mem x list1 -> union list1 xs
    | x::xs -> x::(union list1 xs)

但是，这并没有给我想要的结果；我希望结果按照最小的顺序排列。我该怎么做呢？

Answer 1

如果这两个参数已经排序，那么您可以遍历它们并在结果中添加更小的元素：

let rec union list1 list2 =
    match list1, list2 with
    | [], other | other, [] -> other
    | x::xs, y::ys when x < y -> x :: (union xs list2)
    | x::xs, y::ys -> y :: (union list1 ys)

Answer 2

即使您的输入未排序，这也将起作用：

let sortedUnion list1 list2 =
    let rec union list1 list2 =
        match list2 with
        | [] -> list1
        | x::xs when mem x list1 -> union list1 xs
        | x::xs -> x::(union list1 xs)
    let unsorted = union list1 list2
    List.sort unsorted