Should be seq, right?

Would be simpler to use Buffer, since geometric resizing is used anyway. (But good you avoid double iteration, since we don't know the complexity of traversing the input.)

Yes, relying on Buffer would be more convenient, but it would create circular dependencies since Buffer already depends on Bytes.

Of course. Your partial reimplementation is quite lean anyway.

Search & replace error in heading?

val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t for consistency with add and to make the partial application composable.

Indeed, will do.

add_seq : elt Seq.t -> t -> t, cf comment on Map.add_seq.

fixed in last commit

This can be improved later, but this function might deserve a more efficient implementation which does not build the intermediate list at least for small enough arrays (e.g. keeping the first N values on the stack using a non-tail rec loop and creating the array while unwinding the recursion). Even for larger arrays, it might be more efficient to keep the intermediate values directly in arrays (either a resizing buffer, or a list of chunks). To be checked.

Why not, will consider it indeed.

Because of Buffer.{clear, reset, truncate}, you should probably test for i >= b.position instead. (Even if mutation during iteration is specified as being undefined...)

will do.

Same as above.

You should specify that mutation during iteration is not specified (as you did for Buffer). Or, alternatively specify the behavior as you did for Bytes.

No reason for these whitespace changes (and the recommended style would rather be the one without the whitespace).

Why do we need this distinction between S and FULL?

that was because of the sharing of S with some ephemeron table, but I removed the sharing, so this has no reason to exist anymore indeed.

@c-cube Can you address this point?

Typo? (also in the doc strings below)

I'm not very fond of the name. to_seq_starting_from or to_seq_from, perhaps?

I agree to_seq_from is more descriptive than to_seq_at. But we could also incorporate more general slicing in the main sequence extractor,

val to_seq : ?first: (key -> bool) -> ?last: (key -> bool) -> 'a t -> (key * 'a) Seq.t

borrowing the semantics of find_first and find_last. While the end-of-sequence can be adjusted with a sequence combinator, direct support for it has the advantage of only holding on to the part of the container it needs plus O(log(n). Corr.: There is no such guarantee on space complexity here, since the sequence may contain a single element greater than the top-level node. The should be a gain in expected complexity for small sequence lengths.

What about providing a function that memoize the iteration?

That is something non-trivial to do efficiently, in my experience. Using lazy is relatively slow, so I have something better (a kind of append-only buffer) in the gen library that could be used as a building block for memoize. However, this is imho the kind of function that might be more suited to a 3rd party library on opam (which could provide many more combinators and evolve faster than the stdlib).

Fair enough. It might be worth adding a note to seq.mli stating that the generator must be prepared to be used in a non-linear way, so that people don't expose an overly naive generator iterating over lines of a text file.

The inclusion of Hashtbl.S was not used just for avoiding a copy, it was also a way to force people to keep the interface of ephemerons synchronized with the one of hashtables. Could you try to add the functions to the ephemerons?

I'm not even sure what it means to iterate on a weak hashtable… I will certainly not do that before #1010 is merged, my quota of motivation is running dry right now.

@bobot Do you agree with delaying the addition of Seq-related functions to ephemerons?

I think the work just amount to copy the version of hashtbl and apply the same modification than for iter. Lets see, I take the code of this PR, I compare Hashtbl.iter and Ephemerons.MakeSeeded.iter, and ... code written but not typed or tested:

let to_seq tbl =
  (* capture current array, so that even if the table is resized we
     keep iterating on the same array *)
  let tbl_data = tbl.data in
  (* state: index * next bucket to traverse *)
  let rec aux i buck () = match buck with
    | Empty ->
        if i = Array.length tbl_data
        then Seq.Nil
        else aux(i+1) tbl_data.(i) ()
    | Cons (_, c, next) ->
            begin match H.get_key c, H.get_data c with
            | None, _ | _, None -> ()
            | Some key, Some data ->
                 Seq.Cons ((key, data), aux i next)
            end; do_bucket rest in
        
  in
  aux 0 Empty

So I prefer if @c-cube could take this code, in his MR. I would prefer that the signature of ephemerons stay the same than the one of hashtbl.

should we also have a >>=?

Wouldn't that be the same as flat_map found below?

Should we have an imperative yield function?

let yield (x:' a Seq.t) : ('a option * 'a Sequence.t) = 
  let open Seq in match x () with 
  | Nil -> (None, empty)
  | Cons (a, r) -> (Some a, r)

you mean a memoizing peek or something like that? I don't really get what yield would be used for.

besides, until this has chances of being merged (i.e. #1010 merged?) I won't spend any more time on that PR.

Hi, sorry for the late reply, it is more like next in Core.Sequence. But we can wait until this PR is merged and then consider this function as a useful extension. I personally used it a lot. Not sure how others feel.

@c-cube Ok, my bad I put () in my comment (here Seq.Nil) but it should be aux i next, even if the binding is not there anymore we still need to look at the other bindings.