Joining and Interleaving Sequences

appendq: lazy concatenation

let rec appendq xq yq =
  match xq with
  | Nil -> yq
  | Cons (x, xf) -> Cons (x, fun () -> appendq (xf ()) yq)
(* val appendq : 'a seq -> 'a seq -> 'a seq = <fun> *)

This is the lazy analogue of list append (@). It copies elements from xq until exhausted, then switches to yq.

Critical limitation

If xq is infinite, appendq never reaches yq. The second argument is silently lost. Concatenation of infinite sequences is not terribly useful for this reason.

interleave: fair combination

let rec interleave xq yq =
  match xq with
  | Nil -> yq
  | Cons (x, xf) -> Cons (x, fun () -> interleave yq (xf ()))
(* val interleave : 'a seq -> 'a seq -> 'a seq = <fun> *)

interleave exchanges the arguments in the recursive call. This means:

• First element comes from xq
• Second element comes from yq (the old second argument, now first)
• Third element comes from the rest of xq
• And so on, alternating

This is fair: no elements from either sequence are lost, even if both are infinite. Interleaving is the right way to combine two potentially infinite information sources into one.

The key pattern: delay around force

In both appendq and interleave, observe that each xf() (a force) is enclosed within fun () -> ... (a delay):

Cons (x, fun () -> appendq (xf ()) yq)

This is the standard recipe for maintaining laziness. A force not enclosed in a delay (as in the get function) will compute the next element immediately rather than on demand.

Comparison

Operation	Fair?	Use case
appendq	No - loses second arg if first is infinite	Finite prefixes
interleave	Yes - alternates between both	Merging infinite streams