Ackermann Example

// Ackermann function variants, ready to be tested at e.g. scalakata.com
// the purpose is ONLY to play around with the Scala syntax and notions like currying

// "usual" imperative variant, no functions
def ack( n : Int , m : Int ) : Int = {
  if ( n == 0 ) m + 1
  else if ( m == 0 ) ack( n - 1 , 1 )
  else ack( n - 1 , ack( n , m - 1 ) )
}

// examples
ack(0,4) // 5 -- in general, ack(0,m) = m + 1
ack(1,1) // 3 -- in general, ack(1,m) = m + 2
ack(1,2) // 4
ack(1,3) // 5
ack(2,2) // 7 -- in general, ack(2,m) = 2*m + 3
ack(3,3) // 61 -- in general, ack(3,m) = 2^(m+3) - 3

// we will construct a function ackCurried taking an Int, producing an Int=Int function
// such that ackCurried(n)(m) = ack(n,m), e.g. ackCurried(2) is _ => 2*_+3

// helper function ver 1: iterate( f, n ) computes f(f(f(...(f(1))..))), the number of f's being n+1
def iterate( f : Int=>Int , n : Int ) : Int = {
  if( n == 0 ) f(1)
  else f( iterate( f, n - 1 ) )
}

//examples
iterate( _+1, 6 ) // 8
iterate( _+1, 9 ) // 11

// curried version of iterate: iterateCurried( f ) returns the function g s.t. g(n) = f(f(f(...(f(1))...)))
def iterateCurried( f : Int=>Int ) : Int=>Int = {
  n => if( n == 0 ) f(1) else f ( iterateCurried(f)(n-1) )
}

// examples
def addTwo = iterateCurried( _+1 )
addTwo( 6 ) //still 8
addTwo( 9 ) //still 11
def nextFunction = iterateCurried( addTwo )
nextFunction( 1 ) //5
nextFunction( 2 ) //7
nextFunction( 3 ) //9
def oneMoreFunction = iterateCurried( nextFunction )
oneMoreFunction( 1 ) //13
oneMoreFunction( 2 ) //29
oneMoreFunction( 3 ) //61
//got the pattern? ack( n ) is iterateCurried( ack(n-1) )

// then, ackCurried can be an Int => (Int=>Int) function with a(n)(m) = a(n,m), as
// a(n) is _+1 if n==0, and iterateCurried( a(n-1) ) otherwise
def ackCurried( n : Int ) : Int=>Int = {
  if( n == 0 ) _ + 1
  else iterateCurried( ackCurried( n - 1 ) )
}

// example
ackCurried(2)(2) //7
ackCurried(3)(3) //61