Search code examples
ocaml

Implementation of List.of_seq

If we look at the source for the OCaml List module, of_seq is defined as:

let[@tail_mod_cons] rec of_seq seq =
  match seq () with
  | Seq.Nil -> []
  | Seq.Cons (x1, seq) ->
      begin match seq () with
      | Seq.Nil -> [x1]
      | Seq.Cons (x2, seq) -> x1 :: x2 :: of_seq seq
      end

This makes perfect sense except why is the extra work performed within the function as opposed to writing the seemingly more straightforward following function?

let[@tail_mod_cons] rec of_seq seq =
  match seq () with
  | Seq.Nil -> []
  | Seq.Cons (x1, seq) -> x1 :: of_seq seq

What insight am I missing to make this make sense?

Solution

  • This looks like straightforward loop unrolling to me. I.e., it spreads the loop overhead over twice as many calls to seq ()