redprl/ocaml-bwd

🔙 Backward lists for OCaml

ocaml-bwd's Issues

Consider adding back `concat` (`flatten`) and `concat_map`

Previously we decided to deprecate concat, but it seems useful to collapse 'a bwd bwd to 'a bwd when backward lists are used as accumulators.

✂️ Make `partition` and `partition_map` tail-recursive

I wonder why split was not made tail-recursive while these two functions were? But anyway, it's not difficult to mimic the standard library.

🗞️ Unrolling?

I'm not sure if this is worth it, but I'll document it here anyways. The standard library is currently 2-unrolling a few functions, which means it fuses two recursive calls into one. The main reason is to match the performance, thanks to the careful benchmarking of @nojb. The relevant functions are:

• init
• map
• mapi
• map2

I haven't done the unrolling because the potential 20% slow-down on short lists hasn't become a bottleneck yet, but maybe we should do it when more people are using this library.

Test the library against OCaml 5.0.0 final version

Change BwdNotation to Bwd.Infix?

Naming the submodule Notation (for infix notations) as Infix seems to be the convention used in several packages (e.g., containers). Concretely, the plan is to...

1. Banish the top-level alias BwdNotation and
2. Rename Bwd.Notation to Bwd.Infix and also BwdLabels.Notation to BwdLabels.Infix

Version 2.1.0 can be released first to deprecate the old modules.

@jonsterling @TOTBWF Thoughts?

Precedence of infix notation

Why did you choose an infix notation whose precedence is higher than function application? It's contrary to all my intuitions for f x #< y to mean f (x #< y).

Order of iteration

I am curious why the decision was made for Bwd.map, Bwd.iter, and so on to operate from right to left rather than from left to right. This is counterintuitive to me (and has led to at least one bug in my code so far). To me, the order in which the elements of a list are visited goes naturally with the textual order, since we read (in English) from left to right.

Moreover, I feel like in practice one of the reasons I care about having things in an order at all is so that I can iterate over them in that order, and the order in which I want to maintain things may be independent from which end of the order I most frequently want to add and remove elements from. In fact I might argue that for adding things, at least, the more common situation is to want to add things at the "end" of the order in which I want to iterate over them.

How to implement `to_seq`?

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.

📁 Make `fold_right_map` tail-recursive

fold_left_map in the standard library is tail-recursive.

Mirror new functions from OCaml 5.1: `is_empty`, `find_mapi`, `find_index`