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 (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.