Ackermann function (OCaml)
From LiteratePrograms
The Ackermann function or Ackermann-Péter function is defined recursively for non-negative integers m and n as follows:
In the theory of computation, the Ackermann function is a simple example of a recursive function that is not primitively recursive. Note that this function grows very quickly -- even A(4, 3) cannot be feasibly computed on ordinary computers.
This page explains how to implement the Ackermann function in OCaml. For this example, we will be using OCaml's "function" syntax for defining functions. We choose this style as it most closely resembles the problem definition.
Source code
We begin the code by defining a recursive value named ackermann and indicate that this value will be a function
<<ackermann.ml>>= let rec ackermann = function
First, we add a case to catch the cases when either argument is negative, because the Ackermann function is only defined for non-negative integers. While that may be fine in math, when it comes to programming, one should be aware that invalid inputs may be used. These cases should be caught and handled. Here we raise an exception with an informative message that can be handled by the caller of ackermann.
<<ackermann.ml>>= | m,n when m < 0 || n < 0 -> invalid_arg "Ackermann's function is only defined over the non-negative integers"
We then use pattern matching on the function's parameter to handle the three cases given in the definition of the Ackermann function. The first case we handle is the base case of the recursion, when m = 0. Note that because of the way we are doing the pattern matching, our function takes a single tuple as input.
<<ackermann.ml>>= | 0,n -> n+1
For the second case, when m > 0 and n = 0, we make a simple recursive call to the ackermann function.
<<ackermann.ml>>= | m,0 -> ackermann (m-1,1)
In the third case, when m, n > 0, a pair of recursive calls are made. The first call determines the new value of n, and the second call which uses this new value along with the new value of m (a simple decrement).
<<ackermann.ml>>= | m,n -> ackermann (m-1,ackermann (m,n-1))
Execution result
In this section we show the output of a few applications of ackermann:
# ackermann (0,0);; - : int = 1 # ackermann (1,1);; - : int = 3 # ackermann (2,13);; - : int = 29 # ackermann (3,1);; - : int = 13 # ackermann (3,7);; - : int = 1021 # ackermann (3,9);; - : int = 4093 # ackermann (-1,9);; Exception: Invalid_argument "Ackermann's function is only defined over the non-negative integers".
Note, however, that due to the tremendous growth rate of Ackermann's function, the number of recursive calls to ackermann quickly becomes too much to handle, even for relatively small values of m and n.
# ackermann (4,1);; Stack overflow during evaluation (looping recursion?).
| Download code |
