Order of iteration

[mikeshulman]

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.

[favonia]

@mikeshulman This is a very good point and I must admit that I didn't think through this issue very carefully. The only (very weak) counterargument I could think of is that we should not change the subtle behaviors of an API. However, this could be solved by a major version jump.

[mikeshulman]

I wasn't necessarily suggesting to change it, just wanted to understand the intent. But I certainly wouldn't object if you change it.

[favonia]

@mikeshulman The original intent, I believe, was to signify that the lists are from the "right," and engineering-wise we sometimes can have tail-recursive code by following the order of elements in the underlying data structure. However, this is arguably violating the principle of "cherishing the text order." Anyway I don't feel I have thought through this carefully.

[mikeshulman]

Yes, I see the tail-recursion point for traversing right-to-left. In principle one could include both and let the user choose as appropriate; then the only question would be how to name them.

[jonsterling]

Textual vs. temporal? Spatial vs. temporal?

[mikeshulman]

I was thinking of Bwd.map and Bwd.backwards_map or something...

[favonia]

@mikeshulman @jonsterling Idea: just like fold_left and fold_right, we can have map_{left,right}, iter_{left,right}, filter_map_{left,right} to specify the order and make the current ones aliases of some of them? Are these clear and elegant enough?

[jonsterling]

@favonia My only critique is: these names are very hard on my 🧠 because "folding from the left" and "folding to the left" are equally likely interpretations to me. (This is one of the reasons I can never remember which of foldl / foldr I want when programming in functional languages.)

[favonia]

I like @jonsterling's idea (in a private channel) to highlight the difference conceptually. It's not about left v.s. right, but the textual order v.s. the underlying/physical/induction order. If we follow this approach, we can also define these for the built-in OCaml lists, just that they would agree. We can make one of them the default in Bwd, but I don't know what would be a good suffix to annotate the variants. I guess this is where native English speakers have to step in and propose something...

[favonia]

The alternative approach, which is what @mikeshulman mentioned, is to take textual as the definition, and thus "backward" means the opposite of textual.

[favonia]

Regardless of the approach we want to take, I propose the following migration plan:

• In bwd 2.4.0, deprecate map/iter/iteri/... and add variants with _suffix1 and _suffix2.
• In bwd 3.0.0, add back short names that are aliases of the variants that match the textual order.

[favonia]

@mikeshulman Hmm I'm checking the documentation of List, and found that many functions actually do not specify the exact order. Which orders did you use/assume for the bug in your code? I think for iter it makes sense, but for map it is actually unspecified as far as I can see.

[mikeshulman]

You're right that the documentation of List.map doesn't specify the order.

map f [a1; ...; an] applies function f to a1, ..., an, and builds the list [f a1; ...; f an] with the results returned by f.

In fact, I think this documentation is positively confusing, because in practice List.map does iterate from left to right, whereas [f a1; ...; f an] iterates from right to left!

# List.map print_endline ["one";"two";"three"];;
one
two
three
- : unit list = [(); (); ()]

# [print_endline "one"; print_endline "two"; print_endline "three"];;
three
two
one
- : unit list = [(); (); ()]

My bug was because I assumed that Bwd.iter or map would iterate from left to right, whereas it currently does from right to left. I think it is good to specify the order for map as well as for iter, since one of OCaml's strengths is the ability to cleanly mix a small amount of effectual code with largely functional code, so one may care about the order of execution even while also accumulating a result functionally.

[mikeshulman]

For a name, I actually kind of like map_left and map_right -- even if you already have trouble remembering which fold is which, at least this doesn't impose something new to remember but piggybacks on the old one. (I remember which fold is which by thinking about associativity, but of course that only helps if you remember which associativity is which.) The name "underlying/physical/induction" order doesn't really convey anything to my intuition.

[mikeshulman]

By the way, I recently also had reason to want a version of Bwd.nth that counts from the left rather than the right.