Array-Like Data

OCaml supports a number of array-like data structures; i.e., mutable integer-indexed containers that provide constant-time access to their elements. We’ll discuss several of them in this section.

<array_expr>.(<index_expr>)

<array_expr>.(<index_expr>) <- <value_expr>

let b = Bytes.of_string "foobar";;
>val b : bytes = "foobar"
Bytes.set b 0 (Char.uppercase (Bytes.get b 0));;
>- : unit = ()
Bytes.to_string b;;
>- : string = "Foobar"

<bigarray_expr>.{<index_expr>}
<bigarray_expr>.{<index_expr>} <- <value_expr>

Mutable Record and Object Fields and Ref Cells

As we’ve seen, records are immutable by default, but individual record fields can be declared as mutable. These mutable fields can be set using the <- operator, i.e., record.field <- expr.  

As we’ll see in Chapter 12, Objects, fields of an object can similarly be declared as mutable, and can then be modified in much the same way as record fields.    

type 'a ref = { mutable contents : 'a };;
>type 'a ref = { mutable contents : 'a; }

let x = ref 1;;
>val x : int ref = {Base.Ref.contents = 1}
!x;;
>- : int = 1
x := !x + 1;;
>- : unit = ()
!x;;
>- : int = 2

let ref x = { contents = x };;
>val ref : 'a -> 'a ref = <fun>
let (!) r = r.contents;;
>val ( ! ) : 'a ref -> 'a = <fun>
let (:=) r x = r.contents <- x;;
>val ( := ) : 'a ref -> 'a -> unit = <fun>

Foreign Functions

Another source of imperative operations in OCaml is resources that come from interfacing with external libraries through OCaml’s foreign function interface (FFI). The FFI opens OCaml up to imperative constructs that are exported by system calls or other external libraries. Many of these come built in, like access to the write system call or to the clock, while others come from user libraries. OCaml’s FFI is discussed in more detail in Chapter 22, Foreign Function Interface.      

Cyclic Data Structures

Doubly linked lists are a cyclic data structure, meaning that it is possible to follow a nontrivial sequence of pointers that closes in on itself. In general, building cyclic data structures requires the use of side effects. This is done by constructing the data elements first, and then adding cycles using assignment afterward.    

There is an exception to this, though: you can construct fixed-size cyclic data structures using let rec:

let rec endless_loop = 1 :: 2 :: 3 :: endless_loop;;
>val endless_loop : int list = [1; 2; 3; <cycle>]

This approach is quite limited, however. General-purpose cyclic data structures require mutation.

Modifying the List

Now, we’ll start considering operations that mutate the list, starting with insert_first, which inserts an element at the front of the list:  

let insert_first t value =
  let new_elt = { prev = None; next = !t; value } in
  (match !t with
  | Some old_first -> old_first.prev <- Some new_elt
  | None -> ());
  t := Some new_elt;
  new_elt

insert_first first defines a new element new_elt, and then links it into the list, finally setting the list itself to point to new_elt. Note that the precedence of a match expression is very low, so to separate it from the following assignment (t := Some new_elt), we surround the match with parentheses. We could have used begin ... end for the same purpose, but without some kind of bracketing, the final assignment would incorrectly become part of the None case.  

We can use insert_after to insert elements later in the list. insert_after takes as arguments both an element after which to insert the new node and a value to insert:

let insert_after elt value =
  let new_elt = { value; prev = Some elt; next = elt.next } in
  (match elt.next with
  | Some old_next -> old_next.prev <- Some new_elt
  | None -> ());
  elt.next <- Some new_elt;
  new_elt

We also need a remove function:

let remove t elt =
  let { prev; next; _ } = elt in
  (match prev with
  | Some prev -> prev.next <- next
  | None -> t := next);
  (match next with
  | Some next -> next.prev <- prev
  | None -> ());
  elt.prev <- None;
  elt.next <- None

Note that the preceding code is careful to change the prev pointer of the following element and the next pointer of the previous element, if they exist. If there’s no previous element, then the list pointer itself is updated. In any case, the next and previous pointers of the element itself are set to None.

These functions are more fragile than they may seem. In particular, misuse of the interface may lead to corrupted data. For example, double-removing an element will cause the main list reference to be set to None, thus emptying the list. Similar problems arise from removing an element from a list it doesn’t belong to.

This shouldn’t be a big surprise. Complex imperative data structures can be quite tricky, considerably trickier than their pure equivalents. The issues described previously can be dealt with by more careful error detection, and such error correction is taken care of in modules like Core’s Doubly_linked. You should use imperative data structures from a well-designed library when you can. And when you can’t, you should make sure to put great care into your error handling.    

Iteration Functions

When defining containers like lists, dictionaries, and trees, you’ll typically want to define a set of iteration functions like iter, map, and fold, which let you concisely express common iteration patterns.   

Dlist has two such iterators: iter, the goal of which is to call a unit-producing function on every element of the list, in order; and find_el, which runs a provided test function on each value stored in the list, returning the first element that passes the test. Both iter and find_el are implemented using simple recursive loops that use next to walk from element to element and value to extract the element from a given node:

let iter t ~f =
  let rec loop = function
    | None -> ()
    | Some el ->
      f (value el);
      loop (next el)
  in
  loop !t

let find_el t ~f =
  let rec loop = function
    | None -> None
    | Some elt -> if f (value elt) then Some elt else loop (next elt)
  in
  loop !t

This completes our implementation, but there’s still considerably more work to be done to make a really usable doubly linked list. As mentioned earlier, you’re probably better off using something like Core Doubly_linked module that has a more complete interface and has more of the tricky corner cases worked out. Nonetheless, this example should serve to demonstrate some of the techniques you can use to build nontrivial imperative data structure in OCaml, as well as some of the pitfalls.

Memoization and Dynamic Programming

Another benign effect is memoization. A memoized function remembers the result of previous invocations of the function so that they can be returned without further computation when the same arguments are presented again.   

Here’s a function that takes as an argument an arbitrary single-argument function and returns a memoized version of that function. Here we’ll use Base’s Hashtbl module, rather than our toy Dictionary.

This implementation requires an argument of a Hashtbl.Key.t, which plays the role of the hash and equal from Dictionary. Hashtbl.Key.t is an example of what’s called a first-class module, which we’ll see more of in Chapter 11, First Class Modules.

let memoize m f =
  let memo_table = Hashtbl.create m in
  (fun x ->
     Hashtbl.find_or_add memo_table x ~default:(fun () -> f x));;
>val memoize : 'a Hashtbl.Key.t -> ('a -> 'b) -> 'a -> 'b = <fun>

The preceding code is a bit tricky. memoize takes as its argument a function f and then allocates a polymorphic hash table (called memo_table), and returns a new function which is the memoized version of f. When called, this new function uses Hashtbl.find_or_add to try to find a value in the memo_table, and if it fails, to call f and store the result. Note that memo_table is referred to by the function, and so won’t be collected until the function returned by memoize is itself collected.  

Memoization can be useful whenever you have a function that is expensive to recompute and you don’t mind caching old values indefinitely. One important caution: a memoized function by its nature leaks memory. As long as you hold on to the memoized function, you’re holding every result it has returned thus far.

Memoization is also useful for efficiently implementing some recursive algorithms. One good example is the algorithm for computing the edit distance (also called the Levenshtein distance) between two strings. The edit distance is the number of single-character changes (including letter switches, insertions, and deletions) required to convert one string to the other. This kind of distance metric can be useful for a variety of approximate string-matching problems, like spellcheckers.    

Consider the following code for computing the edit distance. Understanding the algorithm isn’t important here, but you should pay attention to the structure of the recursive calls:  

let rec edit_distance s t =
  match String.length s, String.length t with
  | (0,x) | (x,0) -> x
  | (len_s,len_t) ->
    let s' = String.drop_suffix s 1 in
    let t' = String.drop_suffix t 1 in
    let cost_to_drop_both =
      if Char.(=) s.[len_s - 1] t.[len_t - 1] then 0 else 1
    in
    List.reduce_exn ~f:Int.min
      [ edit_distance s' t  + 1
      ; edit_distance s  t' + 1
      ; edit_distance s' t' + cost_to_drop_both
      ];;
>val edit_distance : string -> string -> int = <fun>
edit_distance "OCaml" "ocaml";;
>- : int = 2

The thing to note is that if you call edit_distance "OCaml" "ocaml", then that will in turn dispatch the following calls:

And these calls will in turn dispatch other calls:

As you can see, some of these calls are repeats. For example, there are two different calls to edit_distance "OCam" "oca". The number of redundant calls grows exponentially with the size of the strings, meaning that our implementation of edit_distance is brutally slow for large strings. We can see this by writing a small timing function, using Core’s Time module.

let time f =
  let open Core in
  let start = Time.now () in
  let x = f () in
  let stop = Time.now () in
  printf "Time: %F ms\n" (Time.diff stop start |> Time.Span.to_ms);
  x;;
>val time : (unit -> 'a) -> 'a = <fun>

And now we can use this to try out some examples:

time (fun () -> edit_distance "OCaml" "ocaml");;
>Time: 0.655651092529 ms
>- : int = 2
time (fun () -> edit_distance "OCaml 4.13" "ocaml 4.13");;
>Time: 2541.6533947 ms
>- : int = 2

Just those few extra characters made it thousands of times slower!

Memoization would be a huge help here, but to fix the problem, we need to memoize the calls that edit_distance makes to itself. Such recursive memoization is closely related to a common algorithmic technique called dynamic programming, except that with dynamic programming, you do the necessary sub-computations bottom-up, in anticipation of needing them. With recursive memoization, you go top-down, only doing a sub-computation when you discover that you need it.   

To see how to do this, let’s step away from edit_distance and instead consider a much simpler example: computing the nth element of the Fibonacci sequence. The Fibonacci sequence by definition starts out with two 1s, with every subsequent element being the sum of the previous two. The classic recursive definition of Fibonacci is as follows:

let rec fib i =
if i <= 1 then i else fib (i - 1) + fib (i - 2);;
>val fib : int -> int = <fun>

This is, however, exponentially slow, for the same reason that edit_distance was slow: we end up making many redundant calls to fib. It shows up quite dramatically in the performance:

time (fun () -> fib 20);;
>Time: 1.14369392395 ms
>- : int = 6765
time (fun () -> fib 40);;
>Time: 14752.7184486 ms
>- : int = 102334155

As you can see, fib 40 takes thousands of times longer to compute than fib 20.

So, how can we use memoization to make this faster? The tricky bit is that we need to insert the memoization before the recursive calls within fib. We can’t just define fib in the ordinary way and memoize it after the fact and expect the first call to fib to be improved.

let fib = memoize (module Int) fib;;
>val fib : int -> int = <fun>
time (fun () -> fib 40);;
>Time: 18174.5970249 ms
>- : int = 102334155
time (fun () -> fib 40);;
>Time: 0.00524520874023 ms
>- : int = 102334155

In order to make fib fast, our first step will be to rewrite fib in a way that unwinds the recursion. The following version expects as its first argument a function (called fib) that will be called in lieu of the usual recursive call.

let fib_norec fib i =
  if i <= 1 then i
  else fib (i - 1) + fib (i - 2);;
>val fib_norec : (int -> int) -> int -> int = <fun>

We can now turn this back into an ordinary Fibonacci function by tying the recursive knot:

let rec fib i = fib_norec fib i;;
>val fib : int -> int = <fun>
fib 20;;
>- : int = 6765

We can even write a polymorphic function that we’ll call make_rec that can tie the recursive knot for any function of this form:

let make_rec f_norec =
  let rec f x = f_norec f x in
  f;;
>val make_rec : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
let fib = make_rec fib_norec;;
>val fib : int -> int = <fun>
fib 20;;
>- : int = 6765

This is a pretty strange piece of code, and it may take a few moments of thought to figure out what’s going on. Like fib_norec, the function f_norec passed in to make_rec is a function that isn’t recursive but takes as an argument a function that it will call. What make_rec does is to essentially feed f_norec to itself, thus making it a true recursive function.

This is clever enough, but all we’ve really done is find a new way to implement the same old slow Fibonacci function. To make it faster, we need a variant of make_rec that inserts memoization when it ties the recursive knot. We’ll call that function memo_rec:

let memo_rec m f_norec x =
  let fref = ref (fun _ -> assert false) in
  let f = memoize m (fun x -> f_norec !fref x) in
  fref := f;
  f x;;
>val memo_rec : 'a Hashtbl.Key.t -> (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b =
>  <fun>

Note that memo_rec has almost the same signature as make_rec.

We’re using the reference here as a way of tying the recursive knot without using a let rec, which for reasons we’ll describe later wouldn’t work here.

Using memo_rec, we can now build an efficient version of fib:

let fib = memo_rec (module Int) fib_norec;;
>val fib : int -> int = <fun>
time (fun () -> fib 40);;
>Time: 0.121355056763 ms
>- : int = 102334155

As you can see, the exponential time complexity is now gone.

The memory behavior here is important. If you look back at the definition of memo_rec, you’ll see that the call memo_rec fib_norec does not trigger a call to memoize. Only when fib is called and thereby the final argument to memo_rec is presented does memoize get called. The result of that call falls out of scope when the fib call returns, and so calling memo_rec on a function does not create a memory leak—the memoization table is collected after the computation completes.

We can use memo_rec as part of a single declaration that makes this look like it’s little more than a special form of let rec:

let fib = memo_rec (module Int) (fun fib i ->
if i <= 1 then 1 else fib (i - 1) + fib (i - 2));;
>val fib : int -> int = <fun>

Memoization is overkill for implementing Fibonacci, and indeed, the fib defined above is not especially efficient, allocating space linear in the number passed into fib. It’s easy enough to write a Fibonacci function that takes a constant amount of space.

But memoization is a good approach for optimizing edit_distance, and we can apply the same approach we used on fib here. We will need to change edit_distance to take a pair of strings as a single argument, since memo_rec only works on single-argument functions. (We can always recover the original interface with a wrapper function.) With just that change and the addition of the memo_rec call, we can get a memoized version of edit_distance. The memoization key is going to be a pair of strings, so we need to get our hands on a module with the necessary functionality for building a hash-table in Base.

Writing hash-functions and equality tests and the like by hand can be tedious and error prone, so instead we’ll use a few different syntax extensions for deriving the necessary functionality automatically. By enabling ppx_jane, we pull in a collection of such derivers, three of which we use in defining String_pair below.    

#require "ppx_jane";;
module String_pair = struct
  type t = string * string [@@deriving sexp_of, hash, compare]
end;;
>module String_pair :
>  sig
>    type t = string * string
>    val sexp_of_t : t -> Sexp.t
>    val hash_fold_t : Hash.state -> t -> Hash.state
>    val hash : t -> int
>    val compare : t -> t -> int
>  end

With that in hand, we can define our optimized form of edit_distance.

let edit_distance = memo_rec (module String_pair)
  (fun edit_distance (s,t) ->
     match String.length s, String.length t with
     | (0,x) | (x,0) -> x
     | (len_s,len_t) ->
       let s' = String.drop_suffix s 1 in
       let t' = String.drop_suffix t 1 in
       let cost_to_drop_both =
         if Char.(=) s.[len_s - 1] t.[len_t - 1] then 0 else 1
       in
       List.reduce_exn ~f:Int.min
         [ edit_distance (s',t ) + 1
         ; edit_distance (s ,t') + 1
         ; edit_distance (s',t') + cost_to_drop_both
]);;
>val edit_distance : String_pair.t -> int = <fun>

This new version of edit_distance is much more efficient than the one we started with; the following call is many thousands of times faster than it was without memoization.

time (fun () -> edit_distance ("OCaml 4.09","ocaml 4.09"));;
>Time: 0.964403152466 ms
>- : int = 2

let memo_rec m f_norec =
  let rec f = memoize m (fun x -> f_norec f x) in
  f;;
>Line 2, characters 17-49:
>Error: This kind of expression is not allowed as right-hand side of `let rec'

let rec x = x + 1

let rec x = lazy (force x + 1);;
>val x : int lazy_t = <lazy>

force x;;
>Exception: Lazy.Undefined.

let lazy_memo_rec m f_norec x =
  let rec f = lazy (memoize m (fun x -> f_norec (force f) x)) in
  (force f) x;;
>val lazy_memo_rec : 'a Hashtbl.Key.t -> (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b =
>  <fun>
time (fun () -> lazy_memo_rec (module Int) fib_norec 40);;
>Time: 0.181913375854 ms
>- : int = 102334155

Terminal I/O

OCaml’s buffered I/O library is organized around two types: in_channel, for channels you read from, and out_channel, for channels you write to. The In_channel and Out_channel modules only have direct support for channels corresponding to files and terminals; other kinds of channels can be created through the Unix module.    

We’ll start our discussion of I/O by focusing on the terminal. Following the UNIX model, communication with the terminal is organized around three channels, which correspond to the three standard file descriptors in Unix:

In_channel.stdin

The “standard input” channel. By default, input comes from the terminal, which handles keyboard input.

Out_channel.stdout

The “standard output” channel. By default, output written to stdout appears on the user terminal.

Out_channel.stderr

The “standard error” channel. This is similar to stdout but is intended for error messages.

The values stdin, stdout, and stderr are useful enough that they are also available in the top level of Core’s namespace directly, without having to go through the In_channel and Out_channel modules.

Let’s see this in action in a simple interactive application. The following program, time_converter, prompts the user for a time zone, and then prints out the current time in that time zone. Here, we use Core’s Zone module for looking up a time zone, and the Time module for computing the current time and printing it out in the time zone in question:

open Core

let () =
  Out_channel.output_string stdout "Pick a timezone: ";
  Out_channel.flush stdout;
  match In_channel.(input_line stdin) with
  | None -> failwith "No timezone provided"
  | Some zone_string ->
    let zone = Time_unix.Zone.find_exn zone_string in
    let time_string = Time.to_string_abs (Time.now ()) ~zone in
    Out_channel.output_string stdout
      (String.concat
         ["The time in ";Time_unix.Zone.to_string zone;" is ";time_string;".\n"]);
    Out_channel.flush stdout

We can build this program using dune and run it, though you’ll need to add a dune-project and dune file, as described in Chapter 4, Files Modules and Programs. You’ll see that it prompts you for input, as follows:

$ dune exec ./time_converter.exe
Pick a timezone:

You can then type in the name of a time zone and hit Return, and it will print out the current time in the time zone in question:

Pick a timezone: Europe/London
The time in Europe/London is 2013-08-15 00:03:10.666220+01:00.

We called Out_channel.flush on stdout because out_channels are buffered, which is to say that OCaml doesn’t immediately do a write every time you call output_string. Instead, writes are buffered until either enough has been written to trigger the flushing of the buffers, or until a flush is explicitly requested. This greatly increases the efficiency of the writing process by reducing the number of system calls.

Note that In_channel.input_line returns a string option, with None indicating that the input stream has ended (i.e., an end-of-file condition). Out_channel.output_string is used to print the final output, and Out_channel.flush is called to flush that output to the screen. The final flush is not technically required, since the program ends after that instruction, at which point all remaining output will be flushed anyway, but the explicit flush is nonetheless good practice.

Formatted Output with printf

Generating output with functions like Out_channel.output_string is simple and easy to understand, but can be a bit verbose. OCaml also supports formatted output using the printf function, which is modeled after printf in the C standard library. printf takes a format string that describes what to print and how to format it, as well as arguments to be printed, as determined by the formatting directives embedded in the format string. So, for example, we can write:     

printf
  "%i is an integer, %F is a float, \"%s\" is a string\n"
3 4.5 "five";;
>3 is an integer, 4.5 is a float, "five" is a string
>- : unit = ()

Unlike C’s printf, the printf in OCaml is type-safe. In particular, if we provide an argument whose type doesn’t match what’s presented in the format string, we’ll get a type error:

printf "An integer: %i\n" 4.5;;
>Line 1, characters 27-30:
>Error: This expression has type float but an expression was expected of type
>         int

let fmt = "%i is an integer\n";;
>val fmt : string = "%i is an integer\n"
printf fmt 3;;
>Line 1, characters 8-11:
>Error: This expression has type string but an expression was expected of type
>         ('a -> 'b, Stdio.Out_channel.t, unit) format =
>           ('a -> 'b, Stdio.Out_channel.t, unit, unit, unit, unit) format6

open CamlinternalFormatBasics;;
let fmt : ('a, 'b, 'c) format =
"%i is an integer\n";;
>val fmt : (int -> 'c, 'b, 'c) format =
>  Format
>   (Int (Int_i, No_padding, No_precision,
>     String_literal (" is an integer\n", End_of_format)),
>   "%i is an integer\n")

printf fmt 3;;
>3 is an integer
>- : unit = ()

Now let’s see how we can rewrite our time conversion program to be a little more concise using printf:

open Core

let () =
  printf "Pick a timezone: %!";
  match In_channel.input_line In_channel.stdin with
  | None -> failwith "No timezone provided"
  | Some zone_string ->
    let zone = Time_unix.Zone.find_exn zone_string in
    let time_string = Time.to_string_abs (Time.now ()) ~zone in
    printf "The time in %s is %s.\n%!" (Time_unix.Zone.to_string zone) time_string

In the preceding example, we’ve used only two formatting directives: %s, for including a string, and %! which causes printf to flush the channel.

printf’s formatting directives offer a significant amount of control, allowing you to specify things like:     

• Alignment and padding

• Escaping rules for strings

• Whether numbers should be formatted in decimal, hex, or binary

• Precision of float conversions

There are also printf-style functions that target outputs other than stdout, including:    

• eprintf, which prints to stderr

• fprintf, which prints to an arbitrary out_channel

• sprintf, which returns a formatted string

All of this, and a good deal more, is described in the API documentation for the Printf module in the OCaml Manual.

File I/O

Another common use of in_channels and out_channels is for working with files. Here are a couple of functions—one that creates a file full of numbers, and the other that reads in such a file and returns the sum of those numbers:   

let create_number_file filename numbers =
  let outc = Out_channel.create filename in
  List.iter numbers ~f:(fun x -> Out_channel.fprintf outc "%d\n" x);
  Out_channel.close outc;;
>val create_number_file : string -> int list -> unit = <fun>
let sum_file filename =
  let file = In_channel.create filename in
  let numbers = List.map ~f:Int.of_string (In_channel.input_lines file) in
  let sum = List.fold ~init:0 ~f:(+) numbers in
  In_channel.close file;
  sum;;
>val sum_file : string -> int = <fun>
create_number_file "numbers.txt" [1;2;3;4;5];;
>- : unit = ()
sum_file "numbers.txt";;
>- : int = 15

For both of these functions, we followed the same basic sequence: we first create the channel, then use the channel, and finally close the channel. The closing of the channel is important, since without it, we won’t release resources associated with the file back to the operating system.

One problem with the preceding code is that if it throws an exception in the middle of its work, it won’t actually close the file. If we try to read a file that doesn’t actually contain numbers, we’ll see such an error:

sum_file "/etc/hosts";;
>Exception:
>(Failure
>  "Int.of_string: \"127.0.0.1   localhost localhost.localdomain localhost4 localhost4.localdomain4\"")

And if we do this over and over in a loop, we’ll eventually run out of file descriptors:

for i = 1 to 10000 do try ignore (sum_file "/etc/hosts") with _ -> () done;;
>- : unit = ()
sum_file "numbers.txt";;
>Error: I/O error: ...: Too many open files

And now, you’ll need to restart your toplevel if you want to open any more files!

To avoid this, we need to make sure that our code cleans up after itself. We can do this using the protect function described in Chapter 7, Error Handling, as follows:

let sum_file filename =
  let file = In_channel.create filename in
  Exn.protect ~f:(fun () ->
    let numbers = List.map ~f:Int.of_string (In_channel.input_lines file) in
    List.fold ~init:0 ~f:(+) numbers)
    ~finally:(fun () -> In_channel.close file);;
>val sum_file : string -> int = <fun>

And now, the file descriptor leak is gone:

for i = 1 to 10000 do try ignore (sum_file "/etc/hosts" : int) with _ -> () done;;
>- : unit = ()
sum_file "numbers.txt";;
>- : int = 15

This is really an example of a more general issue with imperative programming and exceptions. If you’re changing the internal state of your program and you’re interrupted by an exception, you need to consider quite carefully if it’s safe to continue working from your current state.

In_channel has functions that automate the handling of some of these details. For example, In_channel.with_file takes a filename and a function for processing data from an in_channel and takes care of the bookkeeping associated with opening and closing the file. We can rewrite sum_file using this function, as shown here:

let sum_file filename =
  In_channel.with_file filename ~f:(fun file ->
    let numbers = List.map ~f:Int.of_string (In_channel.input_lines file) in
    List.fold ~init:0 ~f:(+) numbers);;
>val sum_file : string -> int = <fun>

Another misfeature of our implementation of sum_file is that we read the entire file into memory before processing it. For a large file, it’s more efficient to process a line at a time. You can use the In_channel.fold_lines function to do just that:

let sum_file filename =
  In_channel.with_file filename ~f:(fun file ->
    In_channel.fold_lines file ~init:0 ~f:(fun sum line ->
      sum + Int.of_string line));;
>val sum_file : string -> int = <fun>

This is just a taste of the functionality of In_channel and Out_channel. To get a fuller understanding, you should review the API documentation.

The Value Restriction

So, when does the compiler infer weakly polymorphic types? As we’ve seen, we need weakly polymorphic types when a value of unknown type is stored in a persistent mutable cell. Because the type system isn’t precise enough to determine all cases where this might happen, OCaml uses a rough rule to flag cases that don’t introduce any persistent mutable cells, and to only infer polymorphic types in those cases. This rule is called the value restriction.  

The core of the value restriction is the observation that some kinds of expressions, which we’ll refer to as simple values, by their nature can’t introduce persistent mutable cells, including:

• Constants (i.e., things like integer and floating-point literals)

• Constructors that only contain other simple values

• Function declarations, i.e., expressions that begin with fun or function, or the equivalent let binding, let f x = ...

• let bindings of the form let var = expr1 in expr2, where both expr1 and expr2 are simple values

Thus, the following expression is a simple value, and as a result, the types of values contained within it are allowed to be polymorphic:

(fun x -> [x;x]);;
>- : 'a -> 'a list = <fun>

But, if we write down an expression that isn’t a simple value by the preceding definition, we’ll get different results.

identity (fun x -> [x;x]);;
>- : '_weak2 -> '_weak2 list = <fun>

In principle, it would be safe to infer a fully polymorphic variable here, but because OCaml’s type system doesn’t distinguish between pure and impure functions, it can’t separate those two cases.

The value restriction doesn’t require that there is no mutable state, only that there is no persistent mutable state that could share values between uses of the same function. Thus, a function that produces a fresh reference every time it’s called can have a fully polymorphic type:

let f () = ref None;;
>val f : unit -> 'a option ref = <fun>

But a function that has a mutable cache that persists across calls, like memoize, can only be weakly polymorphic.

Partial Application and the Value Restriction

Most of the time, when the value restriction kicks in, it’s for a good reason, i.e., it’s because the value in question can actually only safely be used with a single type. But sometimes, the value restriction kicks in when you don’t want it. The most common such case is partially applied functions. A partially applied function, like any function application, is not a simple value, and as such, functions created by partial application are sometimes less general than you might expect.  

Consider the List.init function, which is used for creating lists where each element is created by calling a function on the index of that element:

List.init;;
>- : int -> f:(int -> 'a) -> 'a list = <fun>
List.init 10 ~f:Int.to_string;;
>- : string list = ["0"; "1"; "2"; "3"; "4"; "5"; "6"; "7"; "8"; "9"]

Imagine we wanted to create a specialized version of List.init that always created lists of length 10. We could do that using partial application, as follows:

let list_init_10 = List.init 10;;
>val list_init_10 : f:(int -> '_weak3) -> '_weak3 list = <fun>

As you can see, we now infer a weakly polymorphic type for the resulting function. That’s because there’s nothing that guarantees that List.init isn’t creating a persistent ref somewhere inside of it that would be shared across multiple calls to list_init_10. We can eliminate this possibility, and at the same time get the compiler to infer a polymorphic type, by avoiding partial application:

let list_init_10 ~f = List.init 10 ~f;;
>val list_init_10 : f:(int -> 'a) -> 'a list = <fun>

This transformation is referred to as eta expansion and is often useful to resolve problems that arise from the value restriction.

Relaxing the Value Restriction

OCaml is actually a little better at inferring polymorphic types than was suggested previously. The value restriction as we described it is basically a syntactic check: you can do a few operations that count as simple values, and anything that’s a simple value can be generalized.

But OCaml actually has a relaxed version of the value restriction that can make use of type information to allow polymorphic types for things that are not simple values.

For example, we saw that a function application, even a simple application of the identity function, is not a simple value and thus can turn a polymorphic value into a weakly polymorphic one:

identity (fun x -> [x;x]);;
>- : '_weak4 -> '_weak4 list = <fun>

But that’s not always the case. When the type of the returned value is immutable, then OCaml can typically infer a fully polymorphic type:

identity [];;
>- : 'a list = []

On the other hand, if the returned type is mutable, then the result will be weakly polymorphic:

[||];;
>- : 'a array = [||]
identity [||];;
>- : '_weak5 array = [||]

A more important example of this comes up when defining abstract data types. Consider the following simple data structure for an immutable list type that supports constant-time concatenation:

module Concat_list : sig
  type 'a t
  val empty : 'a t
  val singleton : 'a -> 'a t
  val concat  : 'a t -> 'a t -> 'a t  (* constant time *)
  val to_list : 'a t -> 'a list       (* linear time   *)
end = struct

  type 'a t = Empty | Singleton of 'a | Concat of 'a t * 'a t

  let empty = Empty
  let singleton x = Singleton x
  let concat x y = Concat (x,y)

  let rec to_list_with_tail t tail =
    match t with
    | Empty -> tail
    | Singleton x -> x :: tail
    | Concat (x,y) -> to_list_with_tail x (to_list_with_tail y tail)

  let to_list t =
    to_list_with_tail t []

end;;
>module Concat_list :
>  sig
>    type 'a t
>    val empty : 'a t
>    val singleton : 'a -> 'a t
>    val concat : 'a t -> 'a t -> 'a t
>    val to_list : 'a t -> 'a list
>  end

The details of the implementation don’t matter so much, but it’s important to note that a Concat_list.t is unquestionably an immutable value. However, when it comes to the value restriction, OCaml treats it as if it were mutable:

Concat_list.empty;;
>- : 'a Concat_list.t = <abstr>
identity Concat_list.empty;;
>- : '_weak6 Concat_list.t = <abstr>

The issue here is that the signature, by virtue of being abstract, has obscured the fact that Concat_list.t is in fact an immutable data type. We can resolve this in one of two ways: either by making the type concrete (i.e., exposing the implementation in the mli), which is often not desirable; or by marking the type variable in question as covariant. We’ll learn more about covariance and contravariance in Chapter 12, Objects, but for now, you can think of it as an annotation that can be put in the interface of a pure data structure.  

In particular, if we replace type 'a t in the interface with type +'a t, that will make it explicit in the interface that the data structure doesn’t contain any persistent references to values of type 'a, at which point, OCaml can infer polymorphic types for expressions of this type that are not simple values:

module Concat_list : sig
  type +'a t
  val empty : 'a t
  val singleton : 'a -> 'a t
  val concat  : 'a t -> 'a t -> 'a t  (* constant time *)
  val to_list : 'a t -> 'a list       (* linear time   *)
end = struct

  type 'a t = Empty | Singleton of 'a | Concat of 'a t * 'a t

  let empty = Empty
  let singleton x = Singleton x
  let concat x y = Concat (x,y)

  let rec to_list_with_tail t tail =
    match t with
    | Empty -> tail
    | Singleton x -> x :: tail
    | Concat (x,y) -> to_list_with_tail x (to_list_with_tail y tail)

  let to_list t =
    to_list_with_tail t []

end;;
>module Concat_list :
>  sig
>    type +'a t
>    val empty : 'a t
>    val singleton : 'a -> 'a t
>    val concat : 'a t -> 'a t -> 'a t
>    val to_list : 'a t -> 'a list
>  end

Now, we can apply the identity function to Concat_list.empty without losing any polymorphism:

identity Concat_list.empty;;
>- : 'a Concat_list.t = <abstr>