There are many useful Lambda Calculus functions that are commonly defined
on lists.
To append two lists, L1 and L2,
if L1 is empty return L2,
otherwise the result is the first element of L1 (i.e., hd L1)
followed by the result of appending the tail of L1 and all of L2
(i.e., append (tl L1) L2).
append = lambda L1. lambda L2.
if null L1 then L2
else (hd L1) :: (append (tl L1) L2)
Zip takes two lists and returns a list of pairs.
zip = lambda L1. lambda L2.
if null L1 or null L2 then nil
else (pair hd L1 hd L2)::(zip tl L1 tl L2)
This version of merge allows duplicate entries that are common to L1 and L2;
it is assumed that L1 and L2 are sorted in which case the result is sorted.
merge = lambda L1. lambda L2.
if null L1 then L2
else if null L2 then L1
else { neither L1 nor L2 is null }
if hd L1 < hd L2 then
hd L1 :: merge tl L1 L2
else { NB. duplicates allowed }
hd L2 :: merge L1 tl L2
The slow version of reverse
takes O(|L|2)-time.
This is because append L1 L2 takes O(|L1|)-time,
and reverseS calls append |L|-times.
reverseS = lambda L. { O(|L|**2)-time }
if null L then nil
else append (reverseS tl L) (hd L :: nil)
The fast version of reverse takes O(|L|)-time
by using an accumulating output parameter.
reverse = lambda L.
let rec rev = lambda inp. lambda op.
{ op is an `accumulating parameter' }
if null inp then op
else rev (tl inp) ((hd inp)::op)
{ inp shrinks op grows }
in rev L nil
Filter builds a sublist of those elements of a list, L,
that satisfy a predicate (test, truth function), p.
filter = lambda p. lambda L.
{ those elements of L that satisfy p }
if null L then nil
else let hdL = hd L in
if p hdL then hdL::(filter p tl L)
else filter p tl L
Map applies a function, f, to every element of a list L.
Map is also known as apply-to-all.
map = lambda f. lambda L.
{ [f L1, f L2, ..., f Ln] }
if null L then nil
else (f hd L)::(map f tl L)
Foldl, fold-left,
applies a binary operator, f,
in a left-associative way, to all the elements of a list L,
e.g., foldl times 1 (2::3::4::nil) = ((1×2)×3)×4.
foldl = lambda f. lambda z. lambda L.
{ f( ... (f (f z L1) L2) ...) Ln }
let rec ff = lambda inp. lambda ans.
if null inp then ans
else ff tl inp (f ans hd inp)
in ff L z
Foldr, fold-right,
applies a binary operator, f,
in a right-associative way, to all the elements of a list L.
foldr = lambda f. lambda z. lambda L.
{ f L1 (f L2 ( ... (f Ln z) ) ) }
let rec ff = lambda L.
if null L then z
else f hd L (ff tl L)
in ff L
(The list data structure is either built-in, or can be easily defined,
in most programming languages that are based on the λ-calculus.
However, lists can be defined,
from scratch, in the pure λ-calculus.)
The following form exercises the above functions;
change the final expression and experiment.