Skip to main content
Code Review

Return to Answer

added 875 characters in body
Source Link
ErikR
ErikR
  • 1.9k
  • 10
  • 7

Using Data.Memocombinators

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 <- 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.

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

Using Data.Memocombinators

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 <- 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.

Source Link
ErikR
ErikR
  • 1.9k
  • 10
  • 7

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.