CODEWITHSUNDEEP
ocaml
maya
maya

Reputation: 159

Build a sequence from a function

I wrote these function to build a sequence from a function i am having a stack overflow error while testing it

let rec from_fun f ()=
  match f () with
  | None -> Nil
  | Some e -> Cons(e, from_fun f)
from_fun (fun () -> let x = 0 in if x<10 then Some (x+1) else None)

thanks

Upvotes: 2

Views: 158

Answers (3)

coredump
coredump

Reputation: 38924

Here is an example of a generator:

let range_generator from below step =
  let counter = ref from
  in fun () ->
       if (!counter < below)
       then (let result = (Some !counter) in
             counter := !counter + step;
             result)
       else None

For example, a call to range_generator 0 10 2 returns a closure over an internal counter mutable variable which generates all natural even numbers below 10:

# let gen = range_generator 0 10 2;;
val gen : unit -> int option = <fun>

Each call to gen possibly mutates the internal counter:

# gen();;
- : int option = Some 0
# gen();;
- : int option = Some 2
# gen();;
- : int option = Some 4
# gen();;
- : int option = Some 6
# gen();;
- : int option = Some 8
# gen();;
- : int option = None
# gen();;
- : int option = None

With your function:

# from_fun (range_generator 0 5 1);;
- : int list = [0; 1; 2; 3; 4]

Upvotes: 2

Daiwen
Daiwen

Reputation: 727

The variable x you are using is local to the anonymous function you are using. As a result the function always return Some 1. What you probably wanted to do is for the function to take an argument:

let rec from_fun f n =
    match f n with
    | None -> Nil
    | Some e -> Cons(e, from_fun f e)

let seq = from_fun (fun x -> if x<10 then Some (x+1) else None) 0

EDIT: Here is a solution with the appropriate type signature:

let rec from_fun f () =
    match f () with
    | None -> Nil
    | Some e -> Cons(e, from_fun f ())

let x = ref 0

let seq = from_fun
    (fun () ->
        let v = !x in
        if v < 10
        then begin
            x := v + 1;
            Some v
        end
        else None)
    ()

It is worth noting that because of the side effects, you would have to reinitialise x before building a new sequence. The unit argument passed in parameter to from_fun is unnecessary, you could remove it.

Upvotes: 1

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66823

Your function always returns Some 1. It never returns None. So the sequence is infinitely long and the stack overflows while building it.

If you want a function to return different values when you call it, you can do two things. First, you can pass it different parameters. This isn't possible for your design of from_fun--the parameter to the function is always (). Second, your function can be impure. I.e., the function can maintain some mutable state.

Upvotes: 4

Related Questions