Lists

There are useful λ-calculus functions that are commonly defined on lists, e.g.,: append L1 L2 — if list 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),; foldL f z L — f(...(f (f z L₁) L₂)... L_n,; foldR f z L — f L₁ (d L₂ (... (f L_n z)...)),; map f L — apply function f to each element of list L, returning a new list,; merge L1 L2 — merge two sorted lists,; reverse L — return a reversed version of a list,; take n L — return the first n elements of the list L,; zip L1 L2 — takes a pair of lists and returns a list of pairs,
and many more.

let
pair = lambda x. lambda y. x :: y :: nil, {std fns}
fst  = lambda xy. hd xy,
snd  = lambda xy. hd tl xy,

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 in this merge}
    hd L2 :: merge L1 tl L2,

reverseS = lambda L.  {slow O(|L|**2)-time}
  if null L then nil
  else append (reverseS tl L) (hd L :: nil),

reverse = lambda L.  {fast, O(|L|)-time}
  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

There are more λ-calculus examples here.