Benefits of OCaml

Functional programming

The term "functional programming" means different things to different people. There are three main aspects to functional programming:

  • Functions as first-class values
  • Immutable data structures
  • No side-effecting expressions

First-class functions lead to the concepts of currying, higher-order functions and anonymous functions. Immutability leads to a variety of data structures that are often easier to use and can be substantially faster than conventional imperative equivalents. Avoiding side-effects leads to more mathematically elegant programs that are easier to reason about.

Currying

In functional languages, a function of many arguments can be written as a function that accepts one argument and returns a function to consume the remaining arguments. This transformation is known as currying. A curried function may then be partially applied to obtain a more specialised function.

For example, a recursive function to raise a floating point number x to an integer power n could accept its arguments simultaneously as a 2-tuple (n, x):

# let rec pow(n, x) =
    if n=0 then 1. else x *. pow(n-1, x);;
val pow : int * float -> float = <fun>

When written in curried form, this function accepts n and returns a function to raise the given x to the power n:

# let rec pow(n)(x) =
    if n=0 then 1. else x *. pow(n-1)(x);;
val pow : int -> float -> float = <fun>

Unlike the conventional form, the curried form of this function can then exploited to produce a more specialised function. For example, to create a function to cube a given number by applying only the first argument n=3:

# let cube = pow(3);;
val cube : float -> float = <fun>
# cube 2.;;
- : float = 8.

In fact, we added superfluous parentheses to clarify the code. The code can actually be written more succinctly as:

# let rec pow n x =
    if n=0 then 1. else x *. pow (n-1) x;;
val pow : int -> float -> float = <fun>
# let cube = pow 3;;
val cube : float -> float = <fun>

Note that partial application is not the same as partial specialisation. Specifically, the cube function is not optimised for n=3 but, rather, is simply a reference to the pow function and its partially applied arguments (just n=3 in this case). Indeed, calling cube x is actually likely to be slower than calling pow 3 x.

In OCaml, functions of many arguments are conventionally written in curried form. Consequently, the OCaml compilers are better at optimising functions that are written in curried form. In contrast, functions are conventionally written in uncurried form, using tuples, in the SML programming language.

Currying is a practically useful method that can be used to reduce code size and aid clarity, particularly when the order of function arguments is carefully chosen.

Higher-order functions

In functional programming languages, functions can accept other functions as arguments. A function that has a function argument is known as a higher-order function.

Operators in mathematics are one example of higher-order functions. For example, the derivative operator can be thought of as a function that accepts a function as an argument and returns its derivative function as the result. A numerical form of the derivative operator is easy to write in functional languages like OCaml:

# let d f x =
    let dx = sqrt epsilon_float in
    (f(x +. dx) -. f(x -. dx)) /. (2. *. dx);;
val d : (float -> float) -> float -> float = <fun>

Given a function g(x)=x3-x-1:

# let g x = x ** 3. -. x -. 1.;;
val g : float -> float = <fun>

the derivative g' of g can be obtained simply by applying the function d to g:

# let g' = d g;;
val g' : float -> float = <fun>

For example, g'(3)=26:

# g'(3.);;
- : float = 26.

Compared to conventional imperative languages (e.g. C, C++, Java, C#), higher-order functions provide an additional way to factor programs. This is applicable to all programs, not just mathematical programs. For example, the OCaml standard library contains many higher-order functions that are used to provide common functionality in most OCaml programs.

Higher-order functions reduce program size and accelerate development speed, particularly for large programs.

Mutable Data Structures

Impure functional programming languages, including OCaml, mix pure functional programming with imperative constructs. In OCaml, immutable data (like ints) can be made imperative by handling references to them, allowing them to be replaced:

# let i = ref 1 in
  i := 2;
  !i;;
- : int = 2

The OCaml standard library provides several mutable data structures, including strings, arrays, hash tables, queues and stacks.

Mutable data structures can be faster and clearer than immutable data structures for many simple problems, such as solving Sudoku puzzles, but immutable data structures are clearer and sometimes faster for a wide variety of problems.

Immutable Data Structures

The OCaml standard library provides several immutable data structures, including ints, floats, chars, lists, sets and maps.

Our book Objective CAML for Scientists contains an example program for computing the nth-nearest neighbours of atoms in molecules that benefits from the use of immutable data structures. Specifically, shells of neighbours are best represented as sets as they have the set-theoretic operations union and difference applied to them repeatedly. Using an immutable set not only simplifies the code but also allows these set-theoretic operations to be implemented more efficiently (as they are in the OCaml standard library).