Skip to content

Instantly share code, notes, and snippets.

@wmhtet
Created November 23, 2011 04:47
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
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