## Lambda Calculus Examples

 LA home Computing FP  λ-calculus   Intro.   Examples   Syntax   Interp.(L)   Interp.(S)   Examples Also see   Prolog
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