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
Please turn Javascript on.