Lists 

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 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 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 applytoall. 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, foldleft,
applies a binary operator, f,
in a leftassociative way, to all the elements of a list L,
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, foldright, applies a binary operator, f, in a rightassociative 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 builtin, 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. 

