list - f＃の順序で2つのリストを結合

Question

私は2つのリストを結合するこのコードを持っています：

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

2 つの引数が既に並べ替えられている場合は、両方を反復処理して、結果に小さい要素を追加することができます。

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