OCaml creating a list of Fibonacci numbers

3
votes

I have a function that generates Fibonacci numbers:

let rec fib n =
    match n with
    | (0 | 1) -> 1
    | x when x > 0 -> (fib (x-2) + fib (x-1))
    | _ -> raise (Invalid_argument "Negative value supplied to fib");;

but what I really want is for it to return a list of said numbers. I tried this:

let rec fib n list =
    match n with
    | (0 | 1) -> 1 :: []
    | x when x > 0 -> (fib (x-2) list + fib (x-1) list) :: list
    | _ -> raise (Invalid_argument "Negative value supplied to fib");;

But ocamlc says

File "main.ml", line 2, characters 4-174: Error: This expression has type int list but an expression was expected of type int

(Line 2 characters 4-174 corresponds to the match block). I want this to return type "int list", why is it inferring type int?

2
ocamlfibonacci

2 Answers

4
votes

The expression fib (x - 2) list + fib (x - 1) list requires fib to return int, because (+) takes int as parameters.

1
votes

If anyone looking for a solution to get the list of fibonacci numbers here is my solution. This works until certain value (max fib 91).

let fib n =
  let rec aux acc n2 n1 = function
  | 1 -> acc
  | c -> aux ((n2 + n1) :: acc) n1 (n2 + n1) (c - 1)
  in
  List.rev(aux [1; 0] 0 1 (n - 1))
;;