Functional Fibonacci in OCaml

Question

I'm very new to OCaml, and as an exercise I decided to implement the nth Fibonacci algorithm (return a specific Fibonacci number, given an index) in different ways, using what I've learned so far.

I also want to start practicing test-driven development in OCaml, so I also included some basic tests using assertions.

Here is the code:

(** Get the nth fibonacci number using lambda expression and if-then-else. *)
let rec fibo_lamb = fun n ->
 if n < 3 then 1 else fibo_lamb (n - 1) + fibo_lamb (n - 2)
(** Get the nth fibonacci number using if-then-else. *)
let rec fibo_if n =
 if n < 3
 then 1
 else fibo_if (n - 1) + fibo_if (n - 2)
(** Get the nth fibonacci number using pattern matching long form. *)
let rec fibo_mtch n = match n with
 | 1 | 2 -> 1
 | n -> fibo_mtch (n - 1) + fibo_mtch (n - 2)
(** Get the nth fibonacci number using pattern matching short form. *)
let rec fibo_ptrn = function
 | 1 | 2 -> 1
 | n -> fibo_ptrn (n - 1) + fibo_ptrn (n - 2)
(** Get the nth fibonacci number using tail recursion. *)
let fibo_tail n =
 let rec loop n last now =
 if n < 3
 then now
 else loop (n - 1) (now) (last + now)
 in loop n 1 1
(** Get the nth fibonacci number using lists and tail recursion. *)
let fibo_list n =
 let rec loop n xs =
 if n < 3
 then List.nth xs 1
 else loop (n - 1) [List.nth xs 1; List.hd xs + List.nth xs 1]
 in loop n [1; 1]
(** Unit test a fibo function. *)
let test_fibo_fun f id =
 assert (f 1 == 1);
 assert (f 2 == 1);
 assert (f 3 == 2);
 assert (f 4 == 3);
 assert (f 5 == 5);
 assert (f 6 == 8);
 id ^ " passed all tests!" |> print_endline
(** Perform all unit tests for fibo functions. *)
let run_fibo_tests () =
 test_fibo_fun fibo_lamb "fibo_lamb";
 test_fibo_fun fibo_if "fibo_if";
 test_fibo_fun fibo_mtch "fibo_mtch";
 test_fibo_fun fibo_ptrn "fibo_ptrn";
 test_fibo_fun fibo_tail "fibo_tail";
 test_fibo_fun fibo_list "fibo_list";
 "all fibo unit tests passed!" |> print_endline
let () = run_fibo_tests ()

Answer 1

Clearly as I'm sure you're aware, all of your non-tail-recursive solutions have pretty horrendous performance characteristics. But I want to look at one of your tail-recursive solutions.

(** Get the nth fibonacci number using lists and tail recursion. *)
let fibo_list n =
 let rec loop n xs =
 if n < 3
 then List.nth xs 1
 else loop (n - 1) [List.nth xs 1; List.hd xs + List.nth xs 1]
 in loop n [1; 1]

A list is a data structure that by its very nature has any number of elements. The lists you use always have two elements. This is a much better place to use a tuple.

let fibo_tuple n =
 let rec loop n (a, b) =
 if n < 3 then b
 else loop (n - 1) (b, a + b)
 in loop n (1, 1)

If you're going to use a list, you can still clean it up with pattern-matching, rather than calling List.hd and List.nth.

let fibo_list n =
 let rec loop n [a; b] =
 if n < 3 then b
 else loop (n - 1) [b; a + b]
 in loop n [1; 1]

You will be warned about non-exhaustive pattern-matching because again, lists are the wrong data structure to use here, but your code never creates a list with anything other than two elements.