Monday, June 15, 2009

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)