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 XAA08236 for caml-red; Thu, 27 Jul 2000 23:29:11 +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 UAA05708 for <caml-list@pauillac.inria.fr>; Thu, 27 Jul 2000 20:47:53 +0200 (MET DST)
Received: from nef.ens.fr (nef.ens.fr [129.199.96.32])
	by concorde.inria.fr (8.10.0/8.10.0) with ESMTP id e6RIlq521206
	for <caml-list@inria.fr>; Thu, 27 Jul 2000 20:47:52 +0200 (MET DST)
Received: from clipper.ens.fr (clipper-gw.ens.fr [129.199.1.22])
          by nef.ens.fr (8.10.1/1.01.28121999) with ESMTP id e6RIlkT81883
          ; Thu, 27 Jul 2000 20:47:46 +0200 (CEST)
Received: from localhost (frisch@localhost) by clipper.ens.fr (8.9.2/jb-1.1)
	id UAA04923 ; Thu, 27 Jul 2000 20:47:46 +0200 (MET DST)
Date: Thu, 27 Jul 2000 20:47:46 +0200 (MET DST)
From: Alain Frisch <frisch@clipper.ens.fr>
To: John BEPPU <beppu@lineo.com>
cc: caml-list@inria.fr
Subject: Re: help an o'caml beginner
In-Reply-To: <20000726115152.A6102@yukari.lineo.com>
Message-ID: <Pine.GSO.4.04.10007272037290.1683-100000@clipper.ens.fr>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: weis@pauillac.inria.fr

On Wed, 26 Jul 2000, John BEPPU wrote:

> >>>
> 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.
> >>>

(I guess there will be many answers ..)

Here is a solution:

let fibo n =
  let rec aux last x i =    (* x is u_i; last is u_{i-1} *)
     if (i = n) then x
     else aux x (x + last) (i + 1)
  in
  if (n = 0) then 1 else
  aux 1 1 1


> I wrote a recursive Perl version that doesn't make redundant
> calculations, and I'd be interested to see how different in
> structure an O'Caml version would be.
> 
>     sub fib_pair {
>         my $n = shift;
>         my @seq;
>         if ($n < 2) {
>             @seq = (1, 1);
>         } else {
>             @seq = fib_pair($n - 1);
>             @seq = ($seq[1], $seq[0] + $seq[1]);
>         }
>         return @seq;
>     }

Well, this function is not tail-recursive (the recursive call
can't be implemented as a jump). I didn't try it, but I am pretty sure
the OCaml version will be more efficient.

-- 
Alain Frisch