Range Over Iterators in OCaml

Starting with version 1.23, there is support for iterators, which lets us range over pretty much anything!

Let’s look at the List type from the previous example again. In that example, we had an AllElements method that returned a list of all elements in the list. With enumerators, we can do it better - as shown below.

type 'a element = {
    mutable next: 'a element option;
    val: 'a;
}

type 'a list = {
    mutable head: 'a element option;
    mutable tail: 'a element option;
}

let create_list () = {
    head = None;
    tail = None;
}

let push lst v =
  let new_element = { next = None; val = v } in
  match lst.tail with
  | None ->
      lst.head <- Some new_element;
      lst.tail <- Some new_element;
  | Some tail_element ->
      tail_element.next <- Some new_element;
      lst.tail <- Some new_element

let iter_list lst yield =
  let rec aux e =
    match e with
    | None -> ()
    | Some element ->
        if yield element.val then aux element.next
  in
  aux lst.head

All returns an enumerator, which in OCaml is usually achieved with generator-like functions.

The enumerator function takes another function as a parameter, called yield by convention (but the name can be arbitrary). It will call yield for every element we want to iterate over, and note yield’s return value for a potential early termination.

let all_elements lst =
  fun yield ->
    iter_list lst yield

Iteration doesn’t require an underlying data structure, and doesn’t even have to be finite! Here’s a function returning an enumerator over Fibonacci numbers: it keeps running as long as yield keeps returning true.

let generate_fib () =
  fun yield ->
    let rec aux a b =
      if yield a then aux b (a + b)
    in
    aux 1 1

The main function demonstrates how to push values to the list and how to use the enumerator.

let () =
  let lst = create_list () in
  push lst 10;
  push lst 13;
  push lst 23;

  (* Using the enumerator *)
  let all = all_elements lst in
  all (fun v -> print_endline (string_of_int v); true);

  (* Collecting values into a list *)
  let all_values = ref [] in
  all (fun v -> all_values := v :: !all_values; true);
  print_endline ("all: [" ^ (String.concat " " (List.rev_map string_of_int !all_values)) ^ "]");

  (* Fibonacci example *)
  let fib = generate_fib () in
  try
    fib (fun n ->
      if n >= 10 then raise Exit;
      print_endline (string_of_int n);
      true
    )
  with Exit -> ()

Output:

10
13
23
all: [10 13 23]
1
1
2
3
5
8

Generics in OCaml

Errors in OCaml

Learn X By Example

Title here

Range Over Iterators in OCaml