## Friday, 4 May 2012

### Lazily merging two sorted sequences

Lazy means slow but here is a solution using lazy lists:
``````let (++) = LazyList.consDelayed
let rec merge xs ys () =
match xs, ys with
| Cons(x, xs'), Cons(y, _) when x<y -> x ++ merge xs' ys
| Cons(x, _), Cons(y, ys') -> y ++ merge xs ys'
| Nil, xs | xs, Nil -> xs``````
Alternatively, given two ordinary (not lazy) lists, merge them on-demand:
``````let rec merge xs ys = seq {
match xs, ys with
| x::xs, y::_ when x<y ->
yield x
yield! merge xs ys
| x::_, y::ys ->
yield y
yield! merge xs ys
| [], xs | xs, [] -> yield! xs}
``````
This is very inefficient. However, a `seq`-based solution doesn't have to be slow. Here,`Seq.unfold` is your friend and can make this over 4× faster by my measurements:
``````let merge xs ys =
let rec gen = function
| x::xs, (y::_ as ys) when x<y -> Some(x, (xs, ys))
| xs, y::ys -> Some(y, (xs, ys))
| [], x::xs | x::xs, [] -> Some(x, ([], xs))
| [], [] | [], [] -> None
Seq.unfold gen (xs, ys)``````

#### 1 comment:

Daniel Santa Cruz said...

That last merge works no lists, not sequences, correct?