- 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,
- [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] &
- [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