search

RedPRL / ocaml-bwd

🔙 Backward lists for OCaml
https://ocaml.org/p/bwd
Apache License 2.0
19 stars 2 forks source link

How to implement `to_seq`? #15

Closed favonia closed 10 months ago

favonia commented 1 year ago

I'm thinking about adding to_seq and of_seq, but there seem to be two possible implementations of to_seq:

  1. The creation of Seq.t takes O(n) time and then all further items take O(1) time.
  2. The creation of Seq.t takes O(1) time but the first item can take O(n) time. Further items take O(1) time.

I wonder what would be better? The concern about the second approach is that it can take O(n) time to retrieve the first item every time. One can also memoize it (maybe via lazy) but I'm not sure if it's worth it.

jonsterling commented 1 year ago

I'm not sure this is a good idea... The purpose of Seq, to my understanding, is to support compositional lazy list programming — but it seems neither (1) nor (2) benefits from this. As you say, (2) seems a little crazy without memoization, and (1) seems to offer very little benefit over List.to_seq (Bwd.to_list u).

favonia commented 1 year ago

You are right that the more reasonable option (1) is just List.to_seq (Bwd.to_list u). I think of_seq makes a bit more sense but then it's strange to have of_seq but not to_seq.