Why Don’t Variables Vary?

One source of confusion for people new to OCaml is the fact that variables are immutable. This seems pretty surprising even on linguistic terms. Isn’t the whole point of a variable that it can vary? 

The answer to this is that variables in OCaml (and generally in functional languages) are really more like variables in an equation than a variable in an imperative language. If you think about the mathematical identity x(y + z) = xy + xz, there’s no notion of mutating the variables x, y, and z. They vary in the sense that you can instantiate this equation with different numbers for those variables, and it still holds.

The same is true in a functional language. A function can be applied to different inputs, and thus its variables will take on different values, even without mutation.

Pattern Matching and Let

Another useful feature of let bindings is that they support the use of patterns on the left-hand side. Consider the following code, which uses List.unzip, a function for converting a list of pairs into a pair of lists.   

let (ints,strings) = List.unzip [(1,"one"); (2,"two"); (3,"three")];;
>val ints : int list = [1; 2; 3]
>val strings : string list = ["one"; "two"; "three"]

Here, (ints,strings) is a pattern, and the let binding assigns values to both of the identifiers that show up in that pattern. A pattern is essentially a description of the shape of a data structure, where some components are names to be bound to values. As we saw in Chapter 1, Tuples Lists Options And Pattern Matching, OCaml has patterns for a variety of different data types.

Using a pattern in a let binding makes the most sense for a pattern that is irrefutable, i.e., where any value of the type in question is guaranteed to match the pattern. Tuple and record patterns are irrefutable, but list patterns are not. Consider the following code that implements a function for upper casing the first element of a comma-separated list. 

let upcase_first_entry line =
  let (first :: rest) = String.split ~on:',' line in
  String.concat ~sep:"," (String.uppercase first :: rest);;
>Lines 2-3, characters 5-60:
>Warning 8 [partial-match]: this pattern-matching is not exhaustive.
>Here is an example of a case that is not matched:
>[]
>val upcase_first_entry : string -> string = <fun>

This case can’t really come up in practice, because String.split always returns a list with at least one element, even when given the empty string.

upcase_first_entry "one,two,three";;
>- : string = "ONE,two,three"
upcase_first_entry "";;
>- : string = ""

But the compiler doesn’t know this, and so it emits the warning. It’s generally better to use a match expression to handle such cases explicitly:

let upcase_first_entry line =
  match String.split ~on:',' line with
  | [] -> assert false (* String.split returns at least one element *)
  | first :: rest -> String.concat ~sep:"," (String.uppercase first :: rest);;
>val upcase_first_entry : string -> string = <fun>

Note that this is our first use of assert, which is useful for marking cases that should be impossible. We’ll discuss assert in more detail in Chapter 7, Error Handling.

Anonymous Functions

We’ll start by looking at the most basic style of function declaration in OCaml: the anonymous function. An anonymous function is a function that is declared without being named. These can be declared using the fun keyword, as shown here.    

(fun x -> x + 1);;
>- : int -> int = <fun>

Anonymous functions operate in much the same way as named functions. For example, we can apply an anonymous function to an argument:

(fun x -> x + 1) 7;;
>- : int = 8

or pass it to another function. Passing functions to iteration functions like List.map is probably the most common use case for anonymous functions.

List.map ~f:(fun x -> x + 1) [1;2;3];;
>- : int list = [2; 3; 4]

You can even stuff a function into a data structure, like a list:

let transforms = [ String.uppercase; String.lowercase ];;
>val transforms : (string -> string) list = [<fun>; <fun>]
List.map ~f:(fun g -> g "Hello World") transforms;;
>- : string list = ["HELLO WORLD"; "hello world"]

It’s worth stopping for a moment to puzzle this example out. Notice that (fun g -> g "Hello World") is a function that takes a function as an argument, and then applies that function to the string "Hello World". The invocation of List.map applies (fun g -> g "Hello World") to the elements of transforms, which are themselves functions. The returned list contains the results of these function applications.

The key thing to understand is that functions are ordinary values in OCaml, and you can do everything with them that you’d do with an ordinary value, including passing them to and returning them from other functions and storing them in data structures. We even name functions in the same way that we name other values, by using a let binding.

let plusone = (fun x -> x + 1);;
>val plusone : int -> int = <fun>
plusone 3;;
>- : int = 4

Defining named functions is so common that there is some syntactic sugar for it. Thus, the following definition of plusone is equivalent to the previous definition.

let plusone x = x + 1;;
>val plusone : int -> int = <fun>

This is the most common and convenient way to declare a function, but syntactic niceties aside, the two styles of function definition are equivalent.

(fun x -> x + 1) 7;;
>- : int = 8
let x = 7 in x + 1;;
>- : int = 8

Multiargument Functions

OCaml of course also supports multiargument functions, such as:   

let abs_diff x y = abs (x - y);;
>val abs_diff : int -> int -> int = <fun>
abs_diff 3 4;;
>- : int = 1

You may find the type signature of abs_diff with all of its arrows a little hard to parse. To understand what’s going on, let’s rewrite abs_diff in an equivalent form, using the fun keyword.

let abs_diff =
(fun x -> (fun y -> abs (x - y)));;
>val abs_diff : int -> int -> int = <fun>

This rewrite makes it explicit that abs_diff is actually a function of one argument that returns another function of one argument, which itself returns the final result. Because the functions are nested, the inner expression abs (x - y) has access to both x, which was bound by the outer function application, and y, which was bound by the inner one.

This style of function is called a curried function. (Currying is named after Haskell Curry, a logician who had a significant impact on the design and theory of programming languages.) The key to interpreting the type signature of a curried function is the observation that -> is right-associative. The type signature of abs_diff can therefore be parenthesized as follows.   

val abs_diff : int -> (int -> int)

The parentheses don’t change the meaning of the signature, but they make it easier to see the currying.

Currying is more than just a theoretical curiosity. You can make use of currying to specialize a function by feeding in some of the arguments. Here’s an example where we create a specialized version of abs_diff that measures the distance of a given number from 3.

let dist_from_3 = abs_diff 3;;
>val dist_from_3 : int -> int = <fun>
dist_from_3 8;;
>- : int = 5
dist_from_3 (-1);;
>- : int = 4

The practice of applying some of the arguments of a curried function to get a new function is called partial application.  

Note that the fun keyword supports its own syntax for currying, so the following definition of abs_diff is equivalent to the previous one. 

let abs_diff = (fun x y -> abs (x - y));;
>val abs_diff : int -> int -> int = <fun>

You might worry that curried functions are terribly expensive, but this is not the case. In OCaml, there is no penalty for calling a curried function with all of its arguments. (Partial application, unsurprisingly, does have a small extra cost.)

Currying is not the only way of writing a multiargument function in OCaml. It’s also possible to use the different parts of a tuple as different arguments. So, we could write.

let abs_diff (x,y) = abs (x - y);;
>val abs_diff : int * int -> int = <fun>
abs_diff (3,4);;
>- : int = 1

OCaml handles this calling convention efficiently as well. In particular it does not generally have to allocate a tuple just for the purpose of sending arguments to a tuple-style function. You can’t, however, use partial application for this style of function.

There are small trade-offs between these two approaches, but most of the time, one should stick to currying, since it’s the default style in the OCaml world.

Recursive Functions

A function is recursive if it refers to itself in its definition. Recursion is important in any programming language, but is particularly important in functional languages, because it is the way that you build looping constructs. (As will be discussed in more detail in Chapter 8, Imperative Programming, OCaml also supports imperative looping constructs like for and while, but these are only useful when using OCaml’s imperative features.)  

In order to define a recursive function, you need to mark the let binding as recursive with the rec keyword, as shown in this function for finding the first sequentially repeated element in a list. 

let rec find_first_repeat list =
  match list with
  | [] | [_] ->
    (* only zero or one elements, so no repeats *)
    None
  | x :: y :: tl ->
    if x = y then Some x else find_first_repeat (y::tl);;
>val find_first_repeat : int list -> int option = <fun>

The pattern [] | [_] is itself a disjunction of multiple patterns, otherwise known as an or-pattern. An or-pattern matches if any of the sub-patterns match. In this case, [] matches the empty list, and [_] matches any single element list. The _ is there so we don’t have to put an explicit name on that single element. 

We can also define multiple mutually recursive values by using let rec combined with the and keyword. Here’s a (gratuitously inefficient) example.

let rec is_even x =
  if x = 0 then true else is_odd (x - 1)
and is_odd x =
  if x = 0 then false else is_even (x - 1);;
>val is_even : int -> bool = <fun>
>val is_odd : int -> bool = <fun>
List.map ~f:is_even [0;1;2;3;4;5];;
>- : bool list = [true; false; true; false; true; false]
List.map ~f:is_odd [0;1;2;3;4;5];;
>- : bool list = [false; true; false; true; false; true]

OCaml distinguishes between nonrecursive definitions (using let) and recursive definitions (using let rec) largely for technical reasons: the type-inference algorithm needs to know when a set of function definitions are mutually recursive, and these have to be marked explicitly by the programmer.  

But this decision has some good effects. For one thing, recursive (and especially mutually recursive) definitions are harder to reason about than nonrecursive ones. It’s therefore useful that, in the absence of an explicit rec, you can assume that a let binding is nonrecursive, and so can only build upon previous definitions.

In addition, having a nonrecursive form makes it easier to create a new definition that extends and supersedes an existing one by shadowing it.

Prefix and Infix Operators

So far, we’ve seen examples of functions used in both prefix and infix style.    

Int.max 3 4  (* prefix *);;
>- : int = 4
3 + 4        (* infix  *);;
>- : int = 7

You might not have thought of the second example as an ordinary function, but it very much is. Infix operators like + really only differ syntactically from other functions. In fact, if we put parentheses around an infix operator, you can use it as an ordinary prefix function.

(+) 3 4;;
>- : int = 7
List.map ~f:((+) 3) [4;5;6];;
>- : int list = [7; 8; 9]

In the second expression, we’ve partially applied (+) to create a function that increments its single argument by 3.

A function is treated syntactically as an operator if the name of that function is chosen from one of a specialized set of identifiers. This set includes identifiers that are sequences of characters from the following set:

~ ! $ % & * + - . / : < = > ? @ ^ |

as long as the first character is not ~, !, or $.

There are also a handful of predetermined strings that count as infix operators, including mod, the modulus operator, and lsl, for “logical shift left,” a bit-shifting operation.

We can define (or redefine) the meaning of an operator. Here’s an example of a simple vector-addition operator on int pairs.

let (+!) (x1,y1) (x2,y2) = (x1 + x2, y1 + y2);;
>val ( +! ) : int * int -> int * int -> int * int = <fun>
(3,2) +! (-2,4);;
>- : int * int = (1, 6)

You have to be careful when dealing with operators containing *. Consider the following example.

let (***) x y = (x **. y) **. y;;
>Line 1, characters 18-19:
>Error: This expression has type int but an expression was expected of type
>         float

What’s going on is that (***) isn’t interpreted as an operator at all; it’s read as a comment! To get this to work properly, we need to put spaces around any operator that begins or ends with *.

let ( *** ) x y = (x **. y) **. y;;
>val ( *** ) : float -> float -> float = <fun>

The syntactic role of an operator is typically determined by its first character or two, though there are a few exceptions. The OCaml manual has an explicit table of each class of operator and its associated precedence.

We won’t go through the full list here, but there’s one important special case worth mentioning: - and -., which are the integer and floating-point subtraction operators, and can act as both prefix operators (for negation) and infix operators (for subtraction). So, both -x and x - y are meaningful expressions. Another thing to remember about negation is that it has lower precedence than function application, which means that if you want to pass a negative value, you need to wrap it in parentheses, as you can see in this code.    

Int.max 3 (-4);;
>- : int = 3
Int.max 3 -4;;
>Line 1, characters 1-10:
>Warning 5 [ignored-partial-application]: this function application is partial,
>maybe some arguments are missing.
>Line 1, characters 1-10:
>Error: This expression has type int -> int
>       but an expression was expected of type int

Here, OCaml is interpreting the second expression as equivalent to.

(Int.max 3) - 4;;
>Line 1, characters 1-12:
>Warning 5 [ignored-partial-application]: this function application is partial,
>maybe some arguments are missing.
>Line 1, characters 1-12:
>Error: This expression has type int -> int
>       but an expression was expected of type int

which obviously doesn’t make sense.

Here’s an example of a very useful operator from the standard library whose behavior depends critically on the precedence rules described previously.  

let (|>) x f = f x;;
>val ( |> ) : 'a -> ('a -> 'b) -> 'b = <fun>

This is called the reverse application operator, and it’s not quite obvious at first what its purpose is: it just takes a value and a function and applies the function to the value. Despite that bland-sounding description, it has the useful role of sequencing operations, similar in spirit to using the pipe character in the UNIX shell. Consider, for example, the following code for printing out the unique elements of your PATH.      

open Stdio;;
let path = "/usr/bin:/usr/local/bin:/bin:/sbin:/usr/bin";;
>val path : string = "/usr/bin:/usr/local/bin:/bin:/sbin:/usr/bin"
String.split ~on:':' path
|> List.dedup_and_sort ~compare:String.compare
|> List.iter ~f:print_endline;;
>/bin
>/sbin
>/usr/bin
>/usr/local/bin
>- : unit = ()

We can do this without |> by naming the intermediate values, but the result is a bit more verbose.

let split_path = String.split ~on:':' path in
let deduped_path = List.dedup_and_sort ~compare:String.compare split_path in
List.iter ~f:print_endline deduped_path;;
>/bin
>/sbin
>/usr/bin
>/usr/local/bin
>- : unit = ()

An important part of what’s happening here is partial application. For example, List.iter takes two arguments: a function to be called on each element of the list, and the list to iterate over. We can call List.iter with all its arguments:  

List.iter ~f:print_endline ["Two"; "lines"];;
>Two
>lines
>- : unit = ()

or, we can pass it just the function argument, leaving us with a function for printing out a list of strings.

List.iter ~f:print_endline;;
>- : string list -> unit = <fun>

It is this later form that we’re using in the preceding |> pipeline.

But |> only works in the intended way because it is left-associative. Let’s see what happens if we try using a right-associative operator, like (^>).

let (^>) x f = f x;;
>val ( ^> ) : 'a -> ('a -> 'b) -> 'b = <fun>
String.split ~on:':' path
^> List.dedup_and_sort ~compare:String.compare
^> List.iter ~f:print_endline;;
>Line 3, characters 6-32:
>Error: This expression has type string list -> unit
>       but an expression was expected of type
>         (string list -> string list) -> 'a
>       Type string list is not compatible with type
>         string list -> string list

The type error is a little bewildering at first glance. What’s going on is that, because ^> is right associative, the operator is trying to feed the value List.dedup_and_sort ~compare:String.compare to the function List.iter ~f:print_endline. But List.iter ~f:print_endline expects a list of strings as its input, not a function.

The type error aside, this example highlights the importance of choosing the operator you use with care, particularly with respect to associativity.

(@@);;
>- : ('a -> 'b) -> 'a -> 'b = <fun>

Declaring Functions with function

Another way to define a function is using the function keyword. Instead of having syntactic support for declaring multiargument (curried) functions, function has built-in pattern matching. Here’s an example.   

let some_or_zero = function
  | Some x -> x
  | None -> 0;;
>val some_or_zero : int option -> int = <fun>
List.map ~f:some_or_zero [Some 3; None; Some 4];;
>- : int list = [3; 0; 4]

This is equivalent to combining an ordinary function definition with a match.

let some_or_zero num_opt =
  match num_opt with
  | Some x -> x
  | None -> 0;;
>val some_or_zero : int option -> int = <fun>

We can also combine the different styles of function declaration together, as in the following example, where we declare a two-argument (curried) function with a pattern match on the second argument.

let some_or_default default = function
  | Some x -> x
  | None -> default;;
>val some_or_default : 'a -> 'a option -> 'a = <fun>
some_or_default 3 (Some 5);;
>- : int = 5
List.map ~f:(some_or_default 100) [Some 3; None; Some 4];;
>- : int list = [3; 100; 4]

Also, note the use of partial application to generate the function passed to List.map. In other words, some_or_default 100 is a function that was created by feeding just the first argument to some_or_default.

Labeled Arguments

Up until now, the functions we’ve defined have specified their arguments positionally, i.e., by the order in which the arguments are passed to the function. OCaml also supports labeled arguments, which let you identify a function argument by name. Indeed, we’ve already encountered functions from Base like List.map that use labeled arguments. Labeled arguments are marked by a leading tilde, and a label (followed by a colon) is put in front of the variable to be labeled. Here’s an example.   

let ratio ~num ~denom = Float.of_int num /. Float.of_int denom;;
>val ratio : num:int -> denom:int -> float = <fun>

We can then provide a labeled argument using a similar convention. As you can see, the arguments can be provided in any order.

ratio ~num:3 ~denom:10;;
>- : float = 0.3
ratio ~denom:10 ~num:3;;
>- : float = 0.3

OCaml also supports label punning, meaning that you get to drop the text after the colon if the name of the label and the name of the variable being used are the same. We were actually already using label punning when defining ratio. The following shows how punning can be used when invoking a function.  

let num = 3 in
let denom = 4 in
ratio ~num ~denom;;
>- : float = 0.75

val create_hashtable : int -> bool -> ('a,'b) Hashtable.t

val create_hashtable :
  init_size:int -> allow_shrinking:bool -> ('a,'b) Hashtable.t

val substring: string -> int -> int -> string

val substring: string -> pos:int -> len:int -> string

String.split ~on:':' path
|> List.dedup_and_sort ~compare:String.compare
|> List.iter ~f:print_endline;;
>/bin
>/sbin
>/usr/bin
>/usr/local/bin
>- : unit = ()

let apply_to_tuple f (first,second) = f ~first ~second;;
>val apply_to_tuple : (first:'a -> second:'b -> 'c) -> 'a * 'b -> 'c = <fun>

let apply_to_tuple_2 f (first,second) = f ~second ~first;;
>val apply_to_tuple_2 : (second:'a -> first:'b -> 'c) -> 'b * 'a -> 'c = <fun>

let divide ~first ~second = first / second;;
>val divide : first:int -> second:int -> int = <fun>

apply_to_tuple_2 divide (3,4);;
>Line 1, characters 18-24:
>Error: This expression has type first:int -> second:int -> int
>       but an expression was expected of type second:'a -> first:'b -> 'c

let apply_to_tuple f (first,second) = f ~first ~second;;
>val apply_to_tuple : (first:'a -> second:'b -> 'c) -> 'a * 'b -> 'c = <fun>
apply_to_tuple divide (3,4);;
>- : int = 0

Optional Arguments

An optional argument is like a labeled argument that the caller can choose whether or not to provide. Optional arguments are passed in using the same syntax as labeled arguments, and, like labeled arguments, can be provided in any order.  

Here’s an example of a string concatenation function with an optional separator. This function uses the ^ operator for pairwise string concatenation.

let concat ?sep x y =
  let sep = match sep with None -> "" | Some s -> s in
  x ^ sep ^ y;;
>val concat : ?sep:string -> string -> string -> string = <fun>
concat "foo" "bar"             (* without the optional argument *);;
>- : string = "foobar"
concat ~sep:":" "foo" "bar"    (* with the optional argument    *);;
>- : string = "foo:bar"

Here, ? is used in the definition of the function to mark sep as optional. And while the caller can pass a value of type string for sep, internally to the function, sep is seen as a string option, with None appearing when sep is not provided by the caller.

The preceding example needed a bit of boilerplate to choose a default separator when none was provided. This is a common enough pattern that there’s an explicit syntax for providing a default value, which allows us to write concat more concisely.

let concat ?(sep="") x y = x ^ sep ^ y;;
>val concat : ?sep:string -> string -> string -> string = <fun>

Optional arguments are very useful, but they’re also easy to abuse. The key advantage of optional arguments is that they let you write functions with multiple arguments that users can ignore most of the time, only worrying about them when they specifically want to invoke those options. They also allow you to extend an API with new functionality without changing existing code.

The downside is that the caller may be unaware that there is a choice to be made, and so may unknowingly (and wrongly) pick the default behavior. Optional arguments really only make sense when the extra concision of omitting the argument outweighs the corresponding loss of explicitness.

This means that rarely used functions should not have optional arguments. A good rule of thumb is to avoid optional arguments for functions internal to a module, i.e., functions that are not included in the module’s interface, or mli file. We’ll learn more about mlis in Chapter 4, Files Modules And Programs.

concat ~sep:":" "foo" "bar" (* provide the optional argument *);;
>- : string = "foo:bar"
concat ?sep:(Some ":") "foo" "bar" (* pass an explicit [Some] *);;
>- : string = "foo:bar"

concat "foo" "bar" (* don't provide the optional argument *);;
>- : string = "foobar"
concat ?sep:None "foo" "bar" (* explicitly pass `None` *);;
>- : string = "foobar"

let uppercase_concat ?(sep="") a b = concat ~sep (String.uppercase a) b;;
>val uppercase_concat : ?sep:string -> string -> string -> string = <fun>
uppercase_concat "foo" "bar";;
>- : string = "FOObar"
uppercase_concat "foo" "bar" ~sep:":";;
>- : string = "FOO:bar"

let uppercase_concat ?sep a b = concat ?sep (String.uppercase a) b;;
>val uppercase_concat : ?sep:string -> string -> string -> string = <fun>

let numeric_deriv ~delta ~x ~y ~f =
  let x' = x +. delta in
  let y' = y +. delta in
  let base = f ~x ~y in
  let dx = (f ~x:x' ~y -. base) /. delta in
  let dy = (f ~x ~y:y' -. base) /. delta in
  (dx,dy);;
>val numeric_deriv :
>  delta:float ->
>  x:float -> y:float -> f:(x:float -> y:float -> float) -> float * float =
>  <fun>

val numeric_deriv :
  delta:float ->
  x:float -> y:float -> f:(?x:float -> y:float -> float) -> float * float

let numeric_deriv ~delta ~x ~y ~f =
  let x' = x +. delta in
  let y' = y +. delta in
  let base = f ~x ~y in
  let dx = (f ~y ~x:x' -. base) /. delta in
  let dy = (f ~x ~y:y' -. base) /. delta in
  (dx,dy);;
>Line 5, characters 15-16:
>Error: This function is applied to arguments
>       in an order different from other calls.
>       This is only allowed when the real type is known.

let numeric_deriv ~delta ~x ~y ~(f: x:float -> y:float -> float) =
  let x' = x +. delta in
  let y' = y +. delta in
  let base = f ~x ~y in
  let dx = (f ~y ~x:x' -. base) /. delta in
  let dy = (f ~x ~y:y' -. base) /. delta in
  (dx,dy);;
>val numeric_deriv :
>  delta:float ->
>  x:float -> y:float -> f:(x:float -> y:float -> float) -> float * float =
>  <fun>

let colon_concat = concat ~sep:":";;
>val colon_concat : string -> string -> string = <fun>
colon_concat "a" "b";;
>- : string = "a:b"

let prepend_pound = concat "# ";;
>val prepend_pound : string -> string = <fun>
prepend_pound "a BASH comment";;
>- : string = "# a BASH comment"

prepend_pound "a BASH comment" ~sep:":";;
>Line 1, characters 1-14:
>Error: This function has type Base.String.t -> Base.String.t
>       It is applied to too many arguments; maybe you forgot a `;'.

let concat x ?(sep="") y = x ^ sep ^ y;;
>val concat : string -> ?sep:string -> string -> string = <fun>

let prepend_pound = concat "# ";;
>val prepend_pound : ?sep:string -> string -> string = <fun>
prepend_pound "a BASH comment";;
>- : string = "# a BASH comment"
prepend_pound "a BASH comment" ~sep:"--- ";;
>- : string = "# --- a BASH comment"

concat "a" "b" ~sep:"=";;
>- : string = "a=b"

let concat x y ?(sep="") = x ^ sep ^ y;;
>Line 1, characters 18-24:
>Warning 16 [unerasable-optional-argument]: this optional argument cannot be erased.
>val concat : string -> string -> ?sep:string -> string = <fun>

concat "a" "b";;
>- : ?sep:string -> string = <fun>