Taking two streams and combining them in OCaml

If the the input sequences are sorted, there is not much difference between merging lists and sequences. Consider the following merge function on lists:

let rec merge s t =
  match s, t with
  | x :: s , [] | [], x :: s -> x :: s
  | [], [] -> s
  | x :: s', y :: t' ->
    if x < y then
      x :: (merge s' t)
    else if x = y then
      x :: (merge s' t')
    else
       y :: (merge s t')

This function is only using two properties of lists:

• the ability to split the potential first element from the rest of the list
• the ability to add an element to the front of the list

This suggests that we could rewrite this function as a functor over the signature

module type seq = sig
  type 'a t
 
  (* if the seq is non-empty we split the seq into head and tail *)
  val next: 'a t -> ('a * 'a t) option

  (* add back to the front *)
  val cons: 'a -> 'a t -> 'a t
end

Then if we replace the pattern matching on the list with a call to next, and the cons operation with a call to cons, the previous function is transformed into:

module Merge(Any_seq: seq ) = struct

  open Any_seq

  let rec merge s t =
    match next s, next t with
    | Some(x,s), None | None, Some (x,s) ->
      cons x s
    | None, None -> s
    | Some (x,s'), Some (y,t') ->
      if x < y then
        cons x (merge s' t)
      else if x = y then
        cons x (merge s' t')
      else
        cons y (merge s t')

end

Then, with list, our implementation was:

module List_core = struct
  type 'a t = 'a list
  let cons = List.cons
  let next = function
  | [] -> None
  | a :: q -> Some(a,q)
end
module List_implem = Merge(List_core)

which can be tested with

let test = List_implem.merge [1;5;6] [2;4;9]

Implementing the same function for your stream type is then just a matter of writing a similar Stream_core module for stream.