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);



Ross Paterson <ross@soi.city.ac.uk>