ack.scala

package ack

import cats.Eval
import spire.math.SafeLong

object Ackermann {
  import SafeLong.{zero, one}

  // requires m >= 0 and n >= 0
  def run(m: SafeLong, n: SafeLong): Eval[SafeLong] =
    if (m.isZero) Eval.now(n + one)
    else if (n.isZero) Eval.defer(run(m - one, one))
    else Eval.defer(run(m, n - one)).flatMap(run(m - one, _))

  def apply(m: SafeLong, n: SafeLong): SafeLong =
    run(m, n).value
}