From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA08203 for caml-red; Thu, 27 Jul 2000 23:30:03 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA05771 for <caml-list@pauillac.inria.fr>; Thu, 27 Jul 2000 20:57:44 +0200 (MET DST)
Received: from batman.labri.u-bordeaux.fr (batman.labri.u-bordeaux.fr [147.210.8.5])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6RIvh521415
	for <caml-list@inria.fr>; Thu, 27 Jul 2000 20:57:43 +0200 (MET DST)
Received: from serveur1-1.labri.u-bordeaux.fr (root@serveur1-1 [147.210.8.170])
	by batman.labri.u-bordeaux.fr (8.8.7/8.8.7) with ESMTP id VAA27189
	for <caml-list@inria.fr>; Thu, 27 Jul 2000 21:00:07 +0200 (MET DST)
Received: (from vanicat@localhost)
	by serveur1-1.labri.u-bordeaux.fr (8.9.3/8.8.8/Debian/GNU) id UAA11050;
	Thu, 27 Jul 2000 20:57:41 +0200
X-Authentication-Warning: serveur1-1.labri.u-bordeaux.fr: vanicat set sender to vanicat@labri.u-bordeaux.fr using -f
To: caml-list@inria.fr
Subject: Re: help an o'caml beginner
References: <20000726115152.A6102@yukari.lineo.com>
From: Remi VANICAT <remi.vanicat@labri.u-bordeaux.fr>
In-Reply-To: John BEPPU's message of "Wed, 26 Jul 2000 11:51:52 -0600"
Date: 27 Jul 2000 20:57:41 +0200
Message-ID: <ya3n1j3jt96.dlv@serveur1-1.labri.u-bordeaux.fr>
User-Agent: Gnus/5.0807 (Gnus v5.8.7) Emacs/20.7
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: quoted-printable
Sender: weis@pauillac.inria.fr

John BEPPU <beppu@lineo.com> writes:

> Hi.
>=20

[...]


> This was much faster than any of the recursive versions, because it=20
> doesn't have to recompute the same values over and over again.=20=20
>=20
> 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.)
>
>=20
> >>>
> 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 =3D
  let rec aux n n1 n2 =3D
      if n <=3D 2 then (n1 + n2)=20
      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 =3D
   if (n < 2) then n
   else=20
     let rec aux i val n1 n2 =3D
        if i < n then val=20
        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)


--=20
R=E9mi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat