Skip to content

Instantly share code, notes, and snippets.

@folone

folone/gist:6258410

Last active Apr 27, 2018
Embed
What would you like to do?
Ackermann function
def ackermann(m: Int, n: Int): Int = {
(m, n) match {
case (0, _) n + 1
case (m, 0) if m > 0 ackermann(m - 1, 1)
case (m, n) if m > 0 && n > 0 ackermann(m - 1, ackermann(m, n - 1))
}
}
import scalaz._, Scalaz._, Free.{suspend _, _}, Trampoline._
def ackermannTramp(m: Int, n: Int): Trampoline[Int] = {
(m, n) match {
case (0, _) done(n + 1)
case (m, 0) if m > 0 suspend(ackermannTramp(m - 1, 1))
case (m, n) if m > 0 && n > 0 for {
internalRec suspend(ackermannTramp(m, n - 1))
result suspend(ackermannTramp(m - 1, internalRec))
} yield result
}
}
scala> ackermann(4, 1)
java.lang.StackOverflowError
at .ackermann(<console>:23)
at .ackermann(<console>:23)
at .ackermann(<console>:23)
...
scala> ackermannTramp(4,1).run
res2: Int = 65533
@8bitreid

This comment has been minimized.

Copy link

@8bitreid 8bitreid commented Apr 27, 2018

LOVE this! thank you so much for posting. I am now taking a deep dive into scalaz!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment