Fibonacci Numbers

First, the usual recursive version:

     dec fib : num -> num;
     --- fib 0 <= 1;
     --- fib 1 <= 1;
     --- fib(n+2) <= fib n + fib(n+1);

     fib 10;

     uses list, range;
     1..10;
     map fib (0..10);

This is notoriously inefficient. A much faster version, using infinite lists, is:

     uses lists;

     dec fibs : list num;
     --- fibs <= fs whererec fs == 1::1::map (+) (tail fs||fs);

Here || is the `zip' function. The infinite list of factorials fs is defined in terms of itself, as a circular structure (by the whererec), so that previously calculated values for smaller arguments are reused.

     front(11, fibs);