Simplifying division of church-numbers with church-fractions.
A church number n
can be understood as the act of applying a function to a value n
times. That is:
(λ f x . (f (f (f x))))
Can be understood as the church number 3
, since it is an action that applies a function, f
, to a value, x
, 3 times. Here, I will be using "number" as a synonym for "church number" and, thus, a "natural number". Implementing addition, multiplication and exponentiation on church numbers is straightforward. Division is more awkward. Wikipedia, for instance, uses a recursive definition that doesn't have a normal form and is, thus, unsuited for strongly normalizing evaluators. This version is total, but has a huge normal form and works for integers, not naturals. There is a simpler way to define it, extending the same intuition to bu