Merge two lists

Question

I am looking to merge 2 lists in F# in a purely functional way. I am having a hard time understanding the syntax.

Let say I have a tuple ([5;3;8],[2;9;4])

When I call the function, it should return [5;2;3;9;8;4]

Here is why I have so far, which is wrong I am sure. If someone could explain it in a simple way I would be grateful.

let rec interleave (xs,ys) = function
|([], ys) -> ys
|(x::xs, y::ys) -> x :: y::  interleave (xs,ys) 

Answer 1

One important point is that the function is not correct. It fails with the input ([1;2;3], []) since you missed the case of (xs, []) in pattern matching. Moreover, arguments are better in the curried form in order that it's easier to use with partial application. Here is the corrected version:

let rec interleave xs ys =
    match xs, ys with
    | [], ys -> ys
    | xs, [] -> xs
    | x::xs', y::ys' -> x::y::interleave xs' ys'

You can see that the function is not tail-recursive since it applies cons (::) constructor twice after the recursive call returned. One interesting way to make it tail-recursive is using sequence expression:

let interleave xs ys =
    let rec loop xs ys = 
       seq {
             match xs, ys with
             | [], ys -> yield! ys
             | xs, [] -> yield! xs
             | x::xs', y::ys' -> 
                   yield x
                   yield y
                   yield! loop xs' ys'
            }
    loop xs ys |> List.ofSeq

Answer 2

Since F# 4.5 (I think), assuming you want to continue yielding elements from the longer sequence when the shorter is exhausted, you can just do:

let interleave = Seq.transpose >> Seq.concat >> Seq.toList

> interleave [ [5;3;8]; [2;9;4] ];;
val it : int list = [5; 2; 3; 9; 8; 4]

> interleave [ [1;2;3]; [4;5]; [6;7;8;9] ];; // also works for any number of lists
val it : int list = [1; 4; 6; 2; 5; 7; 3; 8; 9]

(Note List.transpose throws if the sequences are of differing length but Seq.transpose does not, so you need to use the latter.)