Introduction

Functional Programming in Ocaml

Ocaml supports three major paradignms: functional, imperative, and object-oriented. Most people are used to the C-style imperative programming style: that is, writing functions that execute a sequence of expressions and then returning a value. Although it is perfectly legal to structure Ocaml functions like this, you will realize sooner or later that it will be more natural to structure your programs functionally.

Basically, there are two guidelines in functional programming:

Procedures have no side effects, which means that no globals have been modified
Functions have no destructive operations

In other words, functions should be mathematical in nature: if you call a function twice, with the same arguments, you will always get the same results, and the global state will not change in any way.

So, what is a side effect? A side effect is an expression that modifies some state other than its return value. Take a look at this snippet:

# Printf.printf "hello\n";;
hello
- : unit = ()

The return value of the call to printf is the unit (). However, by making this call, a file is modified (stdout). This is an example of a side effect. After you make the call to printf, the global state has been modified.

Destructive operations are similar in nature. In Ocaml, you can only perform destructive operations on two things: references and mutable type members. This is an example of a destructive operation:

# let lst = ref [1;2;3];;
val lst : int list ref = {contents = [1; 2; 3]}
# lst := [12; 13; 14];;
- : unit = ()
# lst;;
- : int list ref = {contents = [12; 13; 14]}

Note how the original content of lst is destroyed. This type of operation is not permitted in functional programming. However, operations with side-effects are sometimes necessary. They can usually be separated with a semicolon. Remember, the last expression in a function is always the return value:

let sum x y = 
  let s = x + y in
    Printf.printf "The sum is %d\n" s;
    s

It is a good idea to try and keep functional code separate from imperative code. Functions should be created for specific purposes and should not contain a myriad of imperative statements. One common practice is to have some sort of an imperative main function in an Ocaml program which calls other functional procedures. Remember, because functional programming is constructive in nature, there shouldn't be any unpredicatable effects, as there are with imperative code. So, it is recommended to write functional code as much as possible in Ocaml.

Looping and Recursion

While loops are used extensively in C (no pun intended), their usage is depreciated in Ocaml. Why? Recursion!. In functional programming, all looping is done through recursion. In writing recursive procedures, there are just two important steps:

Start with the base cases
Trust the recursion

Base cases can be described as 'special interest'. These have to be treated differently in the code. For instance, let's write a factorial function, there are two bases cases ('special interest cases'):

The factorial of 0 is 1
The factorial of a negative number is undefined

Otherwise, the factorial of a positive integer n is (n * (factorial n - 1)). Now, we can write the function:

let rec factorial x = 
  if (0 > x) then (raise Exit) else
  match x with
      0 -> 1
    | n -> (n * (factorial (n - 1)))

Although this may seem like an overly simplified explanation of recursive functions, it is really all you need to know. Remember, it is usually unnecessary to think recursively in order to write a recursive procedure.

Recursive vs. Iterative Processes

A recursive procedure is one defined with the rec keyword. However, one should pay attention to the type of recursive procedure that is being written. There are two types: Those which generate recursive processes, and those that generate iterative processes (tail recursive). The factorial function, for instance, generates a recursive process . What's the difference? A recursive process means there is a series of deferred calls. When you call (factorial 5), it translates to:

# (factorial 5);;
  factorial 5
  5 * factorial 4
  5 * 4 * factorial 3
  5 * 4 * 3 * factorial 2
  5 * 4 * 3 * 2 * factorial 1
  5 * 4 * 3 * 2 * 1 * factorial 0
  5 * 4 * 3 * 2 * 1 * 1
  5 * 4 * 3 * 2 * 1
  5 * 4 * 3 * 2
  5 * 4 * 6
  5 * 24
  120
- : int = 120

Notice the deferred calls? When the shape of the trace resembles a triangle, or a tree, then you are dealing with a recursive process. You can also have an iterative process, which is tail recursive. Let's write the factorial in a tail recursive way:

let rec factorial x = 
  if (0 > x) then (raise Exit) else
    let rec helper x so_far = 
      match x with
	  0 -> so_far
	| n -> (helper (n - 1) (so_far * n))
    in
      (helper x 1)

A trace of this function may resemble something like:

# (factorial 5);;
  helper 5 1
  helper 4 5
  helper 3 20
  helper 2 60
  helper 1 120
- : int = 120

In this example, there are no deferred calls when computing the factorial. This is because the recursive procedure keeps a state variable as an argument. Tail recursion is often more efficient because it runs in constant space. Whereas a recursive process adds to the stack on each call.