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?