Fibonacci Numbers

Another circular program - the list nums is defined in terms of itself:

let rec
   first = lambda n. lambda L.
      if n = 0 then nil
      else (hd L)::(first (n-1) tl L),

   nums = 1::(1::(F nums)),

   F = lambda L. (hd L + hd tl L)::(F tl L)

in first 5 nums

{\fB Fibonacci List \fP}

F adds the first two numbers on its input L to form the first element of its output, which in turn becomes part of the input. Note that first and F are quite ordinary functions and could be applied to many other lists.