RE: help an o'caml beginner

[Brent Fulgham <brent.fulgham@xpsystems.com>]

> I happen to be a fan of the other camel (Perl), but I hope you don't
> hold that against me.  ;-)
>
Not at all -- I happen to be a fan of using the right tool for the job.

> I tried out the recursive fibonacci number program that's in the
> manual. 
> 
>     let rec fib n =
>         if n < 2 then 1 else fib(n-1) + fib(n-2);;
>     let main () =
>         let arg = int_of_string Sys.argv.(1) in
>         print_int(fib arg);
>         print_newline();
>         exit 0;;
>     main ();;
> 

[ ... snip C version ... ]

> What surprised the fsck out of me was how fast the O'Caml version
> was compared to the C version.  I checked the asm output of ocamlopt,
> and that was some lean code.  I was not expecting results like this,
> so I was quite pleasantly surprised.  The performance of ocamlopt is
> yet another reason I'm here.
> 
Yes -- the OCaml team has done a fantastic job of creating an efficient,
well-optimized compiler.  It's a good example that shows that functional
languages need not be slow.

[ ... snip iterative C ... ]

> 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.)
> 
The first thing you should learn about is "tail-recursion".  This is
a form of recursion that saves some state between iterations so that
you don't have to recompute values.  For example, a tail-recursive
version of the fibonacci function could be:

     let rec fib_aux n result next =
          if n = 0 then result
               else fib_aux (n-1) (result+next) result;;

     let fib n =
         if n < 2 then 1 
              else fib_aux n 1 1;;

     let main () =
         let arg = int_of_string Sys.argv.(1) in
         print_int(fib arg);
         print_newline();
         exit 0;;

     main ();;
 
This is quite a bit faster than the pure-recursive version on my
system.

Let me know if it works for you.

Thanks,

-Brent