Merging two sequences in F# using LazyList

Claudio Cherubino  had a post about solving one of the standard Amazon interview questions, and it prompted me to finally figure out how to use sequence expressions and LazyList in F#.

The problem is to merge two arrays into a third array in O(n) time.  I like the F# solution using sequences and pattern matching - it feels like a nice way to write this sort of thing. 

type MergeWithLazyLists() =
  static member merge(f, x: LazyList<'t>, y: LazyList<'t>) =
    seq {
      match x, y with
      | LazyList.Cons(xh, xt), LazyList.Cons(yh, yt) when f xh yh -> 
        yield xh
        yield! MergeWithLazyLists.merge(f, xt, y)
      | LazyList.Cons(xh, xt), LazyList.Cons(yh, yt) -> 
        yield yh
        yield! MergeWithLazyLists.merge(f, x, yt)
      | LazyList.Nil, LazyList.Cons(_, _) -> yield! y
      | LazyList.Cons(_, _), LazyList.Nil -> yield! x
      | LazyList.Nil, LazyList.Nil -> ()
    }

  static member merge(f, x: seq<'t>, y: seq<'t>) =
    MergeWithLazyLists.merge(f, (LazyList.ofSeq x), (LazyList.ofSeq y))

let result = MergeWithLazyLists.merge((fun x y -> x < y), (seq {2..6}), (seq {1..7..15}))

printfn "%A" (Seq.toArray result)

A sequence in F# is anything that implements IEnumerable<'t>, so arrays and lists both work just fine.

(An earlier version of this post used the older names for some methods – to_seq, to_array.  I updated this to the new methods in 1.9.7.8)