Lambda Calculus Examples
- Constants and their operators such as ints 0, 1,2, ..., +, -, ..., Booleans true, false, and, or, not, ..., Lists, nil, cons, hd, tl, null, etc., can all be defined in λ calculus,
- [Integers]
- [Booleans]
- [Lists],
- [arithmetic], more of it
- so it is (convenient but) not necessary to "build them in."
- Recursion (equivalently iteration) can be effected in the pure λ calculus by using the fixed-point operator, Y,
- [Y (lazy)].
- The lazy version will not work in a strict language; in that case...
- [Y (strict)].
- Standard operations can be defined on
- [Lists] &
- [Trees]
- [Primes] sieve of Eratosthenese
- [Fibonacci] numbers (1)
- Circular programs give recursive definitions of data-structures
- [Unique], nub
- [Hamming numbers]
- [Fibonacci] numbers (2), circular program
- [Thue] "good" sequences
- [Composite & prime] numbers
- The Edit distance problem admits an interesting functional programming dynamic programming solution:
- [edit distance] × 3.
- The examples can be run interactively using the FORM below