How is Seq unfold implemented

Question

I have a question about how Seq's unfold function is implemented.

I tried creating my own Seq module(My_Seq) to see if I understood how that functionality worked and I can't get my unfold to behave like Seq's unfold function.

Here's my attempt(My_Seq, note I removed all but the necessary functionality)

module type My_Seq_Sig =
sig
  type 'a t

  val empty: 'a t
  val iter: ('a -> unit) -> 'a t -> unit
  val unfold : ('b -> ('a * 'b) option) -> 'b -> 'a t
end

module My_Seq:My_Seq_Sig =
struct
  type 'a t = unit -> 'a node
  and
    'a node =
    | Nil
    | Cons of 'a * 'a t

  let empty = fun () -> Nil

  let rec iter f s =
    match s() with
    | Nil -> ()
    | Cons (e, next) -> f e; iter f next

  let rec unfold f e =
    match (f e) with
    | None -> empty
    | Some (e, next) -> fun () -> Cons (e, unfold f next)
end

Here's how I'm calling my module My_Seq:

let seq =
  let line = ref 0 in
  let filename = print_string "Enter filename: "; read_line() in
  My_Seq.unfold
    (
      fun e ->
        try
          line := !line + 1;
          Some(((string_of_int !line) ^ ": " ^ (input_line e)), e)
        with
        End_of_file
        | _ ->
        print_endline("---Read->" ^ string_of_int (!line - 1) ^ "<-Line(s)---");
        close_in e;
        None
    )
    (open_in filename)

let () =
  seq |> My_Seq.iter print_endline

Here's the output from my attempt:

Enter filename: datafile
1: This is the first
2: This is the second
3: This is the third
4: This is the fourth
---Read->5<-Line(s)---
5: This is the fifth

Now if I use Seq's unfold function:

let seq2 =
  let line = ref 0 in
  let filename = print_string "Enter filename: "; read_line() in
  Seq.unfold
    (
      fun e ->
        try
          line := !line + 1;
          Some(((string_of_int !line) ^ ": " ^ (input_line e)), e)
        with
        End_of_file
        | _ ->
        print_endline("---Read->" ^ string_of_int (!line - 1) ^ "<-Line(s)---");
        close_in e;
        None
    )
    (open_in filename)

let () =
  seq2 |> Seq.iter print_endline

Here's the output from using Seq's unfold function:

Enter filename: datafile
1: This is the first
2: This is the second
3: This is the third
4: This is the fourth
5: This is the fifth
---Read->5<-Line(s)---

datafile contents:

This is the first
This is the second
This is the third
This is the fourth
This is the fifth

You'll note that the outputs differ and I have no idea why. Maybe someone can shed some light on this.

That did it Guest0x0

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

user_13248143 · Answer

The difference lies in when the last element is computed. In your unfold, the last element is computed (in f e) when the element before it is fetched (via feeding a unit argument somewhere), while the Stdlib version computes the last element only when that element itself is fetched.

To make your unfold behaves like the Stdlib one, notice that both branches of your unfold returns a function taking unit as argument. By lifting this argument outside the whole pattern matching, the actual computation of f e will then get delayed, leading to the Stdlib behavior

How is Seq unfold implemented

1 Answers