# 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.

CLICK HERE to find out more related problems solutions.

Scroll to Top