# Functional Fibonacci in OCaml

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 ()



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.