Seq_of_iter: a contained use-case for effects

Learning
1

Sometimes you get an iter function over something, but you want to plug it into some other interface.

It used to be impossible to convert an iterator into a sequence without putting every element in a datastructure. Now that effects are released it is.

I wrote this a while back, I thought it was fun and maybe useful.

let seq_of_iter : type a. ((a -> unit) -> unit) -> a Seq.t =
 fun iter ->
  let module E = struct
    type _ Effect.t += Yield : a -> unit Effect.t
  end in
  let open Effect in
  let open Effect.Deep in
  let continue : a continue ref =
    ref
      (C
         (fun () ->
           try_with
             (fun () ->
               iter (fun v -> Effect.perform (E.Yield v));
               None)
             ()
             {
               effc =
                 (fun (type a) (eff : a t) ->
                   match eff with
                   | E.Yield v ->
                       Some
                         (fun (k : (a, _) continuation) ->
                           let continue = C (fun () -> continue k ()) in
                           Some (v, continue))
                   | _ -> None);
             }))
  in
  Seq.of_dispenser (fun () ->
      let (C continue_func) = !continue in
      match continue_func () with
      | None -> None
      | Some (v, new_continue) ->
          continue := new_continue;
          Some v)
2 Likes
2

Re-reading this code, this is probably wrong :

match eff with
 | E.Yield v ->
     Some
       (fun (k : (a, _) continuation) ->
         let continue = C (fun () -> continue k ()) in
         Some (v, continue))
 | _ -> None

I think it should be:

match eff with
 | E.Yield v ->
     Some
       (fun (k : (a, _) continuation) ->
         let continue = C (fun () -> continue k ()) in
         Some (v, continue))
 | e -> Effect.perfom e

When I tested this there was no effect leaked from the iter function.

3

For what it’s worth, the OCaml manual has its own version of this function as an example of effects:

Implementing control inversion.

let invert (type a) ~(iter : (a -> unit) -> unit) : a Seq.t =
  let module M = struct
    type _ Effect.t += Yield : a -> unit t
  end in
  let yield v = perform (M.Yield v) in
  fun () -> match iter yield with
  | () -> Seq.Nil
  | effect M.Yield v, k -> Seq.Cons (v, continue k)
5 Likes
4

Nice. Its also much simpler. Converting to a dispenser first was the wrong way to go.

5

I wonder if we could have let type += in the same way that we have let exception, so that we could write:

let invert (type a) ~(iter : (a -> unit) -> unit) : a Seq.t =
  let type _ Effect.t += Yield : a -> unit t in
  let yield v = perform (M.Yield v) in
  fun () -> match iter yield with
  | () -> Seq.Nil
  | effect M.Yield v, k -> Seq.Cons (v, continue k)
2 Likes
6

I think I remember discussions about this. Not just for new constructors, but for any type definition. It would definitely feel natural in my opinion.

7

I have an old patch doing this collecting dust somewhere. I will try to dust it off and submit it upstream.

Cheers,
Nicolas

2 Likes
8

Reminds me of Standard ML :wink:

9

Indeed. One difference is that Standard ML implementations tend to allow references to new types that go out of scope, like this:

let datatype t = T in T end

or this

local
   datatype t = T
in
   val x = T
end

whereas similar programs in OCaml are rejected; e.g.:

let module M = struct type t = T end in M.T (* invalid *)

or

include struct
   open struct type t = T end
   let x = T
end (* invalid *)

One nice thing about the restricted let type += over the more general let type construct is that it doesn’t introduce any more of these kinds of scoping issues because it doesn’t create fresh type constructors. It’s just a new way of allocating new data constructors that can’t be named outside the scope, i.e. of generating shared secrets.

3 Likes
10

This is what I came up with: Allow local form of arbitrary structure items by nojb · Pull Request #13835 · ocaml/ocaml · GitHub.

Cheers,
Nicolas

2 Likes