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

Your function is almost right. let f = function is shorthand for let f x = match x with so you don't need explicit args. Also, your algorithm needs some tweaking.

let rec interleave = function //same as: let rec interleave (xs, ys) = match xs, ys with
  |([], ys) -> ys
  |(xs, []) -> xs
  |(x::xs, y::ys) -> x :: y :: interleave (xs,ys)

interleave ([5;3;8],[2;9;4]) //output: [5; 2; 3; 9; 8; 4]

Answer 2

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 3

You can use this opportunity to define a more general higher order function - zipWith, and then implement interleave using it.

let rec zipWith f xlist ylist = 
  match f, xlist, ylist with
  | f, (x :: xs), (y :: ys) -> f x y :: zipWith f xs ys
  | _, _, _ -> []

let interleave xs ys = zipWith (fun a b -> [a; b]) xs ys |> List.concat

Edit:

As @pad said below, F# already has zipWith under the nameList.map2. So you can rewrite interleave as follows:

let interleave xs ys = List.map2 (fun a b -> [a; b]) xs ys |> List.concat

Answer 4

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.)

Answer 5

From the OP it's not clear what should happen if the lists have different lengths, but here's a generic, tail-recursive implementation that fully consumes both lists:

// 'a list -> 'a list -> 'a list
let interleave xs ys =
    let rec imp xs ys acc =
        match xs, ys with
        |    [],    [] -> acc
        | x::xs,    [] -> imp xs [] (x::acc)
        |    [], y::ys -> imp [] ys (y::acc)
        | x::xs, y::ys -> imp xs ys (y::x::acc)
    imp xs ys [] |> List.rev

Examples:

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

Answer 6

Gonna throw another variation into the mix. This handles lists of different lengths by simply appending the remainder of the longer list at the end.

let rec interleave lst1 lst2 = [
    match lst1 with
    | lst1H :: lst1T ->
        yield lst1H
        yield! interleave lst2 lst1T
    | [] -> yield! lst2
]

How it works:

Assuming we have let a = [1;2;3]; let b = [4;5;6] and call interleave a b.

• We match on the first branch because the left list is not empty.
• We yield the head of the first list (1).
• We then recurse into the function with the second list and the tail of the first list. Note that the order of the parameters was swapped.

At this intermediate point we've two lists: the remainder of the first one [2;3] and the second one [4;5;6]. Since we swapped the order of the arguments, we're now focusing on the second list.

• The list is not empty so we match on the first branch.
• We yield the head of the list (4).
• We then recurse again, switching the parameters once more.

The lists at this point are [2;3] and [5;6] while the output contains [1;4].

This process repeats until the operated list is empty, which matches into the second branch, yielding the remainder of the other list.