1
\$\begingroup\$

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

\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.