CODEWITHSUNDEEP
listf#
user1838768
user1838768

Reputation: 143

Union of two lists in order f#

I have this code that unites two lists:

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

However, this doesn't give me the result I would like; I want the result to be in order with the smallest first. How would I go about doing this?

Upvotes: 2

Views: 2185

Answers (2)

Mark Pattison
Mark Pattison

Reputation: 3039

This will work even if your inputs are not sorted:

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

Upvotes: 0

Tomas Petricek
Tomas Petricek

Reputation: 243106

If the two arguments are already sorted than you can just iterate over both of them and add smaller elements to the result:

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)

Upvotes: 1

Related Questions