Union of two lists in order f#

Question

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?

Possible duplicate: http://stackoverflow.com/questions/4100251/merge-two-lists-in-f-recursively — Be Brave Be Like Ukraine, Nov 23 '12 at 14:16
@bytebuster I was only looking for the word union when I searched for it, my bad. That code helped a lot but the list [4;3;2] and [8;7;6] doesnt work — user1838768, Nov 25 '12 at 17:16

score 2 · Answer 1 · answered Nov 23 '12 at 13:59

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)

score 0 · Accepted Answer · answered Nov 23 '12 at 14:01

0

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

answered Nov 23 '12 at 14:01

Mark Pattison

2,964
1
22
42

is there any way to do it without duplicates? – user1838768 Nov 27 '12 at 11:56
Your code already removes duplicates, assuming that `mem x list1` checks whether `x` is a member of `list1`. – Mark Pattison Nov 27 '12 at 13:56

Union of two lists in order f#

2 Answers2