(* fibSlow n = m

   Invariant: 
   If  n>=0  then  m = F(n)   (the nth Fibonacci number)
*)

fun fibSlow 0 = 1
  | fibSlow 1 = 1
  | fibSlow n = fibSlow (n-1) + fibSlow (n-2)



(* fibFast n = (a, b)

   Invariant: 
   Let us define F(-1) = 0 
   If  n>=0  then  a = F(n) and b = F (n-1)
*)

fun fibFast 0 = (1, 0)
  | fibFast n = 
    let 
      val (a, b) = fibFast (n-1)
    in 
      (a+b, a)
    end

(* fiblist n = L

   Invariant: 
   If  n>=0  then  L = [F(n), F (n-1) ....  F(0)]
*)

fun fibList 0 = [1]
  | fibList 1 = [1,1]
  | fibList n = 
    let 
      val (x::y::L) = fibList (n-1)
    in 
      (x+y) :: x :: y :: L
    end