Several Different Versions of an ML Fibonnaci Function

Which, as of 10/8/96, should all load successfully

1.  The straightforward follow-the-definition as originally
explained, using the ordinary (to the instructor) ML style
Fibonnaci function:

	fun fib 1 = 1 |
            fib 2 = 1 |
            fib n = (fib (n-1)) + (fib (n-2));


2.  With a small dollop of dynamic programming (build the list
of all the fib values, then pick off the top when done):

	fun helper b 0 = b |
            helper [] n = raise Match |
            helper (a0::[]) n = raise Match |
            helper ((a0:int)::a1::b) n = helper ((a0+a1)::(a0::a1::b)) (n-1);

        (or for those who prefer destruction to pattern matching:
	fun helper b 0 = b |
            helper b n = helper ((hd(b)+hd(tl(b)) + 0)::b) (n-1);
        )

	fun fib2 1 = 1 |
            fib2 2 = 1 |
            fib2 n = hd(helper [1,1] (n-2));

3.  Same thing but with a real variable:

	val fibs = ref ([]:int list);

	fun helper3 0 = !fibs |
            helper3 n = (fibs := ((hd (!fibs)) + 
                                  (hd (tl (!fibs))))::(!fibs);
                         helper3 (n-1);
                         !fibs);

	fun fib3 1 = 1 |
            fib3 2 = 1 |
            fib3 n = (fibs := [1,1];hd(helper3 (n-2)));

4.  Now, notice that only the last two values in the list matter:

	val t1 = ref 1;
        val t2 = ref 1;
        val t3 = ref 1;

	fun fib4 1 = !t2 |
            fib4 2 = !t2 |
            fib4 n = (t3:= !t1+ !t2;t1:= !t2;t2:= !t3;fib4(n-1));

    (notice that I was a little lazy here and don't reset the values
     of the temporaries so the function can be used again.  
    Q:  Which line must be fixed to resolve this problem?)


5.  Finally get grotesquely imperative:

	val t1 = ref 1;
	val t2 = ref 1;
	val t3 = ref 1;
	val count = ref 0;

	fun fib5 n = (count := n-2;
                      while (!count>0) do (t3 := !t1+ !t2;
                                          t1 := !t2;
				          t2 := !t3;
				          count := !count -1);
                      let val x= !t2 in 
                          (t1 := 1; t2 :=1; t3 :=1;x) end);

6. The uncurried version of No. 2:

  	fun helper (b,0) = b |
            helper (((a0:int)::a1::b),n) = helper ((a0+a1)::a0::a1::b,n-1);


	fun fib2 1 = 1 |
            fib2 2 = 1 |
            fib2 n = hd(helper([1,1],(n-2)));

	note the difference in the type judgement if you actually put
	these in the system!