Comment by vga805 | Hacker News Reader

Comment by vga805 | Hacker News Reader

Parent Full thread

Check out the explanation of church numerals and the successor function on the lambda calculus wikipedia.

Church numerals are quite beautiful. We use the symbols 1, 2, 3, 4, etc., but there's nothing intrinsic to those symbols that denotes what number they refer to.

Church numerals, on the other hand, do encode the actual numbers. A church numeral is simply a function that takes in two other functions as arguments, call them a and b, and applies a to b N number of times, where N is the numeral you're encoding.

So (using JS lambdas to demonstrate):

0 = (a, b) => b // applies a to b 0 times

1 = (a, b) => a(b) // applies a to b 1 time

2 = (a, b) => a(a(b)) // and so on...

Also checkout Scott encoding - for numerals each number is constructed by embedding it's predecessor (with 0 as per Church):

  0 = \f \x x
  N+1 = \f \x f N

To interrogate such a numeral, you supply a function that accepts the predecessor numeral, and a constant for zero. Recursion is needed to effect a fold.

On the face of it heavier than Church, but allows the recursive definition of infinity. Lists and more complex structures can be similarly defined, again with the possibility of recursively defined infinite components.

Then you can do fun stuff like 'taking' infinite elements from a (possibly infinite) list, adding infinity to any number to get infinity, multiplying likewise. Division by zero naturally returns infinity by construction, no convention necessary. 'dropping' infinity elements from an infinite list does not terminate however - you can never reach the first element of that result.

Reply on news.ycombinator.com