Haskell Ackermann function
Using Data.Memocombinators

Have a look at Data.Memocombinators module. It offers combinators for memoizing functions which is essentially what you are doing with the Map.

Here is the example from the documentation on how to use it to create a memoizing fibonacci function:

import Data.MemoCombinators

fib = Memo.integral fib'
   where
     fib' 0 = 0
     fib' 1 = 1
     fib' x = fib (x-1) + fib (x-2) 
              ^^^         ^^^


Things to note:


fib is the memoized version of fib' which is just a helper function
fib' calls fib for any recursive calls


The other thing which will help is to keep in mind that the type Memo a represents a a combinator which is able to memoize a function whose argument type is a. 

So:


integral is a combinator which can memoize functions taking an Int
pair integral integral is a combinator which memoize functions taking an (Int,Int)


And thus to memoize the Ackerman function:

ack = (pair integral integral) ack'
  where ack' (0,n) = n+1
        ack' (m,0) = ack (m-1,1)
        ack' (m,n) = ack (m-1, ack (m, n-1))


Again, note how ack is defined as the memoized version of ack' and ack' calls ack for recursive cases.

Using Array memoization

Faster results can be obtained by using arrays to memoize the functions ack(1,.), ack(2,.) and ack(3,.):

import Data.Array
import Data.Ix

-- memoize the function f using arrays
arrayMemo bnds f = g
  where g i = arr ! i
        arr = array bnds [ (i,f arr i) | i &lt;- range bnds ]

a0 n = n+1

a1 = arrayMemo (0,530000) f
  where f arr 0 = a0 1
        f arr n = a0 (arr ! (n-1))

a2 = arrayMemo (0,270000) f
  where f arr 0 = a1 1
        f arr n = a1 (arr ! (n-1))

a3 = arrayMemo (0,16) f
  where f arr 0 = a2 1
        f arr n = a2 (arr ! (n-1))


The only drawback is that explicit bounds have to be determined for each level function. This approach computes a3 16 in about half a second.