CODEWITHSUNDEEP
functional-programmingocamllazy-evaluation
stht55
stht55

Reputation: 410

Why is this lazy evaluation function not working in OCaml

I made this example up to better understand how lazy evaluation works in OCaml - using thonks.

let rec imp n = fun () -> imp(n*n);;

My understanding of lazy evaluation / thonks is that impl will square an initial number as often as I'm calling imp ().

However this function imp raises the following error:

---
let rec imp n acc = fun()->(***imp (n\*acc)***);;

This expression has type int -> unit -> 'a
but an expression was expected of type 'a
The type variable 'a occurs inside int -> unit -> 'a
---

Upvotes: 1

Views: 174

Answers (2)

G4143
G4143

Reputation: 2829

I would investigate the Seq module and use that.

Here's an example that demonstrates what you are trying to accomplish:

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

let rec incr_by_2 x =
  let ans = x + 2 in
  (ans, Func(fun () -> incr_by_2 ans))

let ans = incr_by_2 10

let () =
  match ans with
  | (d, Func f) -> print_endline(string_of_int d);
    match f() with
    | (d, Func f) -> print_endline(string_of_int d);
      match f() with
      | (d, _) -> print_endline(string_of_int d);

Please note the type constructor Func which is used to resolve the type problem in the function incr_by_2.

Here's an example using the Seq module's unfold function.

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

let rec incr_by_2 x =
  let ans = x + 2 in
  (ans, Func(fun () -> incr_by_2 ans))

let seq x =
  Seq.unfold
    (
      fun (d, Func f) ->
        if d < x
        then
          Some(d, f())
        else
          None
    )
    (incr_by_2 10)

let () =
  (seq 100) |> Seq.iter (Printf.printf "%d\n"); print_newline()

Upvotes: 3

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66803

The compiler is telling you that your function has a recursive type. You can work with recursive types if you supply -rectypes when you run ocaml:

$ ocaml -rectypes
    OCaml version 4.10.0

# let rec imp n = fun () -> imp(n*n);;
val imp : int -> (unit -> 'a as 'a) = <fun>

On the other hand I don't think your function works like you think. Or at least I don't see any way to find out what number it has recently calculated. You'll have to take it on faith that it is calculating larger and larger numbers, I guess.

Upvotes: 6

Related Questions