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|²)-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.

let pair = lambda x. lambda y. x :: y :: nil, {std fns} fst = lambda xy. hd xy, snd = lambda xy. hd tl xy, plus = lambda x. lambda y. x+y, {ops as fns} minus = lambda x. lambda y. x-y, times = lambda x. lambda y. x*y, over = lambda x. lambda y. x/y, lt = lambda x. lambda y. x < y, le = lambda x. lambda y. x <= y, gt = lambda x. lambda y. x > y, ge = lambda x. lambda y. x >= y, eq = lambda x. lambda y. x = y, ne = lambda x. lambda y. x <> y, even = lambda n. (n/2)*2=n, odd = lambda n. not(even n), compose = lambda p. lambda q. lambda x. p(q x) { i.e. p o q } , cons = lambda H. lambda T. H::T {constructor fn} in let rec take = lambda n. lambda L. if n < 1 then nil else if null L then nil else hd L :: take (n-1) tl L , append = lambda L1. lambda L2. if null L1 then L2 else (hd L1) :: (append (tl L1) L2) , zip = lambda L1. lambda L2. if null L1 or null L2 then nil else (pair hd L1 hd L2)::(zip tl L1 tl L2) , 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 , reverseS = lambda L. { O(|L|**2)-time } if null L then nil else append (reverseS tl L) (hd L :: nil) , 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 , 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 = 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 = 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 in let rec L1 = append (1::3::5::nil) (7::9::11::nil), L2 = reverseS L1, L3 = reverse L2, L4 = zip L1 L3, L5 = map fst L4, L6 = merge L5 (2::4::6::8::10::nil) in L6

output area