Skip to content

Instantly share code, notes, and snippets.

@wmhtet
Created November 23, 2011 04:47
Show Gist options
  • Save wmhtet/1387917 to your computer and use it in GitHub Desktop.
Save wmhtet/1387917 to your computer and use it in GitHub Desktop.
Ackermann is being studied for recursion. It is quite complex to do TCO for Ackermann. However, there have been some implementation of Ackermann in Haskell with TCO
/*
http://blog.aunndroid.com/2011/11/learning-scala-recursion-and-tco-1.html
Ackermann is being studied for recursion. It is quite complex to do TCO for Ackermann.
However, there have been some implementation of Ackermann in Haskell with TCO
http://lambda-the-ultimate.org/node/2673
*/
object Ackermann {
def main(args : Array[String]) : Unit = {
println(args.toList);
if (args.isEmpty) { printUsage(); return }
val numberStrList = args.toList.foldLeft(List[String]()) {
(iList, str) =>
iList :+ str.foldLeft("") {
case (str, ch) if (ch.isDigit) => str + ch
case (str, ch) => str
}
}
val numberList = numberStrList.foldLeft(List[Int]()) {
(l, str) => l :+ str.toInt
}.take(2)
println(numberList)
if (numberList.length < 2) printUsage()
else {
val result = ackerMann(numberList.head, numberList.last)
printResult((numberList.head, numberList.last), result)
}
}
def ackerMann(m : BigInt, n : BigInt) : BigInt = {
if (m == 0) return n + 1
if (m > 0 && n == 0) return ackerMann(m - 1, 1)
ackerMann(m - 1, ackerMann(m, n - 1))
}
def printUsage() = {
val m = 3
val n = 2
println("Usage is:")
println("scala AckerMann.scala " + m + " " + n)
val result = ackerMann(m, n)
printResult((m, n), result)
}
def printResult(in : (Int, Int), r : BigInt) = {
println("Ackermann value for " + in + " is : " + r)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment