How can I create a type in order to accommodate the return value of my Ocaml function?

Question

I am trying to implement a lazy fibonacci generator in Ocaml as shown below:

(* fib's helper *)
let rec fibhlpr n = if n == 0 then 0 else if n == 1 then 1 else fibhlpr (n-1) + fibhlpr (n-2);;


(* lazy fib? *)
let rec fib n = ((fibhlpr n), fun() -> fib (n+1));;

I am trying to return the result of fibhlpr (an int) and a function to retrieve the next value, but am not sure how. I think I have to create a new type in order to accommodate the two items I am returning, but I don't know what type fun() -> fib (n+1) returns. When messing around with the code, I received an error which informed me that

fun() -> fib (n+1) has type: int * (unit ->'a).

I am rather new to Ocaml and functional programming in general, so I don't know what this means. I tried creating a new type as follows:

type t = int * (unit -> 'a);;

However, I received the error: "Unbound type parameter 'a".

At this point I am truly stuck: how can I returns the two items that I want (the result of fibhlpr n and a function which returns the next value in the sequence) without causing an error? Thank you for any help.

Answer 1

Try:

type 'a t = int * (unit -> 'a);

Your whole problems stems from this function:

let rec fib n = ((fibhlpr n), fun() -> fib (n+1))

I don't think the type system can define fib when it returns itself.. You need to create a new type which can construct a function to return.

I quickly tried this and it works:

type func = Func of (unit ->(int * func))

let rec fib n =
  let c = ref 0 in
  let rec f () =
    if !c < n
    then
      (
      c := !c + 1;
      ((fibhlpr !c), (Func f))
    )
    else
      failwith "Done"
  in
  f

Following octachron's lead.. Here's a solution using Seq's unfold function.

let rec fibhlpr n =
  if n == 0
  then
    0
  else if n == 1
  then
    1
  else
    fibhlpr (n-1) + fibhlpr (n-2)

type func = Func of (unit -> (int * int * func))

let rec fib n =
  (n, (fibhlpr n), Func(fun() -> fib (n+1)))

let seq =
  fun x ->
  Seq.unfold
    (
      fun e ->
        let (c, d, Func f) = e in
        if c > x
        then
          None
        else
          (
            Some((c, d), f())
          )
    ) (fib 0)

let () =
  Seq.iter
    (fun (c, d) -> Printf.printf "%d: %d\n" c d; (flush stdout)) (seq 30)

Answer 2

The correct type is

type t = int * (unit -> t)

You do not need a polymorphic 'a, because fibonacci only ever yields ints. However, when you call the next function, you need to get the next value, but also a way to get the one after it, and so on and so on. You could call the function multiple times, but then it means that the function has mutable state, the above signature doesn't require that.

Answer 3

If you want to define a lazy sequence, you can use the built-in sequence type constructor Seq.t

let rec gen_fib a b () = Seq.Cons(a, gen_fib b (a+b))
let fib () = gen_fib 0 1 ()

This implementation also has the advantage that computing the n-th term of the sequence is O(n) rather than O(2^n).

If you want to keep using an infinite lazy type, it is also possible. However, you cannot use the recursive type expression

type t = int * (unit -> t)

without the -rectypes flag. And using -rectypes is generally ill-advised for beginners because it reduces the ability of type inference to identify programming errors.

It is thus better to simply use a recursive type definition as suggested by @G4143

type 'a infinite_sequence = { x:'a; next: unit -> 'a infinite_sequence }
let rec gen_fib a b () =
  { x = a; next = gen_fib b (a+b) }
let fib = gen_fib 0 1 ()

Answer 4

You started right saying your fib function returns an integer and a function:

type t = int * (unit -> 'a);;

But as the compiler says the 'a is not bound to anything. Your function also isn't polymorphic so that is has to return a type variable. The function you return is the fib function for the next number. Which also returns an integer and a function:

type t = int * (unit -> int * (unit -> 'a));;

But that second function again is the fib function for the next number.

type t = int * (unit -> int * (unit -> int * (unit -> 'a)))

And so on to infinity. Your type definition is actually recursive. The function you return as second half has the same type as the overall return type. You might try to write this as:

# type t = int * (unit -> t);;
Error: The type abbreviation t is cyclic

Recursive types are not allowed in ocaml unless the -rectypes option is used, which has some other side effects you should read about before using it.

A different way to break the cycle is to insert a Constructor into the cyclic type by making it a variant type:

# type t = Pair of int * (unit -> t)
  let rec fibhlpr n = if n == 0 then 0 else if n == 1 then 1 else fibhlpr (n-1) + fibhlpr (n-2)
  let rec fib n = Pair ((fibhlpr n), fun() -> fib (n+1));;

type t = Pair of int * (unit -> t)
val fibhlpr : int -> int = <fun>
val fib : int -> t = <fun>

Encapsulating the type recursion into a record type also works and might be the more common solution. Something like:

type t = { value : int; next : unit -> t; }

I also think you are missing the point of the exercise. Unless I'm mistaken the point of making it a generator is so that the function can compute the next fibonacci number from the two previous numbers, which you remember, instead of computing it recursively over and over.