Skip to content

Instantly share code, notes, and snippets.

@Gabriella439
Last active April 26, 2020 00:00
Show Gist options
  • Save Gabriella439/77f715350ecc0443eed5fa613ac6b78e to your computer and use it in GitHub Desktop.
Save Gabriella439/77f715350ecc0443eed5fa613ac6b78e to your computer and use it in GitHub Desktop.
Ackermann function in Dhall
-- Credit to: https://news.ycombinator.com/item?id=15186988
let iterate
: (Natural → Natural) → Natural → Natural
= λ(f : Natural → Natural)
→ λ(n : Natural)
→ Natural/fold (n + 1) Natural f 1
let increment : Natural → Natural = λ(n : Natural) → n + 1
let ackermann
: Natural → Natural → Natural
= λ(m : Natural) → Natural/fold m (Natural → Natural) iterate increment
in ackermann
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment