Merge Two Lists in F# Recursively

Question

I am looking to write a recursive function to merge to integer lists in F#

I started with this, but not sure what to do next.

let rec merge xs ys =
    match xs with
    | [] -> ys
    | 

let li = [1;3;5;7;]
let ll = [2;4;5;8;]

Answer 1

As I said in my comment, it's probably easiest if you pattern match on xs and ys simultaneously:

let rec merge xs ys = 
  match xs,ys with
  | [],l | l,[] -> l
  | x::xs', y::ys' -> 
     if x < y then x :: (merge xs' ys) //'
     else y :: (merge xs ys')          //'

Answer 2

I found a way that might suit what the asker wanted. I for one had to solve this very same problem and was barely given a week's worth of lessons on F# so the whole syntax wasn't discussed in class and when I saw the answer above the use of multiple matching ( match lst1, list2 with ... ) I recognized it's use instantly but the professor wouldn't allow it's use, therefor I had to come up with this other alternative. Even thought it's basically the same algorithm it uses more basic code. Just thought I should post it =)

let rec merge2 list1 list2 = 
    let head list = match list with | [] -> 0 | h::t -> h
    let tail list = match list with | [] -> [] | h::t -> t
    match list1 with
    | [] -> []
    | h::t -> 
        //list2's head is 0 then list is empty then return whats in the first list 
        //(i.e no more values of second list to compare)
        if head list2 = 0 then list1
        elif h < head list2 then h :: merge2 t list2 
        else head list2 :: merge2 list1 (tail list2)

Answer 3

You already have one of the base cases right: If xs is empty, just return ys.

Likewise, if ys empty, return xs.

For the case where both xs and ys are not empty, you need to look at xs's and ys's first elements (let's call them x and y):

If x is less than y, than it needs to be inserted before y in the final list. So you take y and prepend to the result of merging the tail of xs with ys (including y).

Otherwise y needs to come first. So prepend y to the result of merging xs (including x) with the tail of ys.

Answer 4

I would use List.fold to do this:

let merge a b =
    List.fold (fun acc x ->
        if List.exists ((=)x) acc = false then
            elem :: acc
        else
            acc
    ) (List.sort a) b

This may not be the fastest way to do it, though.

Answer 5

It's not recursive, but if the inputs aren't sorted:

let merge xs ys = (Seq.append xs ys) |> Seq.sort |> Seq.toList

Answer 6

I don't think this is a recursion problem

let a = [1;3;5]
let b = [2;4;6]

let c = Seq.append a b |> Seq.sort

output from fsi session: c:

val it : seq<int> = seq [1; 2; 3; 4; ...]