# Optimizing the Ackermann Function using Haskell – part 1

This article aims to be the first one of a series of articles concerning the optimization of the Ackermann function using Haskell. The overall goal is to solve a project Euler problem, where the goal is to find _{0 n 6} `A`(`n`, `n`) and give the answer mod 14^{8.}

The problem with this function is that it grows really fast even with very low numbers. It is not a primitive recursive function, however it is a total recursive function. Here is the simplest Haskell definition of it:

module Ackermann (ackermann) where ackermann m n | m == 0 = n+1 | m > 0 && n == 0 = ackermann (m-1) 1 | m > 0 && n > 0 = ackermann (m-1) (ackermann m (n-1))

This definition resembles very much its mathematical definition. If one tries to execute it with low inputs (less than m=4) it runs well, however if one tries to run this function with m=4 and n=1… well, I never waited long enough to see its output 🙂

The biggest problem is the recursion. For example, if both *n* and *m* are greater than zero, the function has a double recursion, which is very consuming both in terms of time and resources.

There are of course many possibilities for optimizing this function: using fix point, memoization (by using a state monad) or non-recursively by means of the Knuth’s up-arrow notation. In further articles I will try each one of those optimizations and see if I can compute the Ackermann function with m=6 and n=6 🙂