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