Re: help an o'caml beginner

[Remi VANICAT <remi.vanicat@labri.u-bordeaux.fr>]

John BEPPU <beppu@lineo.com> writes:

> Hi.
> 

[...]


> This was much faster than any of the recursive versions, because it 
> doesn't have to recompute the same values over and over again.  
> 
> Next, I tried to fumble my way through making an O'Caml version of
> this iterative algorithm, but I failed due to my lack of knowledge
> about this language.  (I hesitate to print the tutorial, because
> that's a lot of paper -- I wish the tutorial were available in HTML.
> I just may have to print it, though.)
>
> 
> >>>
> If anyone out there could implement an O'Caml fibonacci number
> generator that doesn't make redundant calculations, I would really
> appreciate it.  I just need something to study.
> >>>
>

it easy : you have to use an auxiliary function :

let fib n =
  let rec aux n n1 n2 =
      if n <= 2 then (n1 + n2) 
      else aux (n - 1) (n1 + n2) n1 in
  if (n < 3) then 1 else aux (n - 1) 1 1

(an exact translation of your c function would be :
let fib n =
   if (n < 2) then n
   else 
     let rec aux i val n1 n2 =
        if i < n then val 
        else aux (i + 1) (n1 + n2) (n1 + n2) n1

the idea here is for each variable of the c function have an argument
to the recursive caml function, and, instead of changing the variable,
to call the aux function with the new value.

Then I've done some clean up and removal of unused arguments)


-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat