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.

[favonia]

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

I am also looking at related functions including find, find_opt, ...

[mikeshulman]

Amusingly, I realized recently that if one defines a version of map that acts in an arbitrary monad, then the user can use the same function for both directions of iteration by choosing a different monad. Specifically, whichever direction one uses in defining the monadic map, to get the opposite direction one can use the reverse state monad (with a state of unit, if one only cares about mapping or iterating).

(Supposedly one can implement the reverse state monad in OCaml using Lazy, but I wasn't able to get it to work. However, it's quite easy to implement reverse state as an applicative functor, which is good enough for this.)

Of course this is kind of overkill for mapping over lists, especially given how in OCaml you have to use the heavy module syntax for parametrizing something over a monad or applicative. But I've found it useful to avoid writing multiple traversal functions for more complicated data structures.

[favonia]

Thanks for the reminder that this issue has not been resolved yet...

[favonia]

@jonsterling @mikeshulman We seem to have this consensus:

1. In bwd 2.4.0, deprecate the neutral map/iter/iteri/... and add explicit variants with “_suffix1” and “_suffix2”.
2. In bwd 3.0.0, add back the neutral names that are aliases of the variants that match the textual order.

The main disagreement is what suffixes (or prefixes?) to use. Here are some proposals (including the secret ones I was trying out):

from the left (>= 2.4.0)	from the left (>= 3.0.0)	from the right	pros	cons
_left	_left and no suffix	_right	already used by fold_{left,right}	breaking @jonsterling’s mind
_fwd	_fwd and no suffix	_bwd	short and concise	introducing new words to remember
_textual	_textual and no suffix	❓	cool (?)	long, and what’s the opposite of “textual”?
l (such as mapl)	l and no suffix	r	extremely concise	confusing

Some technical details to sort out:

• For various functions that already come with suffixes, what should be the new names? For example, should it be for_all2_fwd or for_all_fwd2? How about find_mapi_fwd?

Here are the full table after 3.0.0, using _fwd and _bwd and under the assumption that the suffix will always come to the very end (so it would be for_all2_fwd). The backward incompatibility is measured as these:

backward incompatibility level	explanation
“serious”	the return value would be change, or the function is mainly for effects and the effects will change.
“mild”	the return value stays the same, but the effects could change and it’s not inconceivable to depend on them.
“minimum”	the return value stays the same; the effects could change but depending on the effects is possible but very questionable.
“none”	both the return value and effects stay the same (not listed in this table).

neutral name	from the left	from the right	backward incompatibility
nth	nth and nth_fwd	nth_bwd	serious
nth_opt	nth_opt and nth_opt_fwd	nth_opt_bwd	serious
init	init and init_fwd	init_bwd	serious
iter	iter and iter_fwd	iter_bwd	serious
iteri	iteri and iteri_fwd	iteri_bwd	serious
map	map and map_fwd	map_bwd	mild
mapi	mapi and mapi_fwd	mapi_bwd	serious
filter_map	filter_map and filter_map_fwd	filter_map_bwd	mild
iter2	iter2 and iter2_fwd	iter2_bwd	serious
map2	map2 and map2_fwd	map2_bwd	mild
for_all	for_all and for_all_fwd	for_all_bwd	minimum
exists	exists and exists_fwd	exists_bwd	minimum
for_all2	for_all2 and for_all2_fwd	for_all2_bwd	minimum
exists2	exists2 and exists2_fwd	exists2_bwd	minimum
find	find and find_fwd	find_bwd	serious
find_opt	find_opt and find_opt_fwd	find_opt_bwd	serious
find_index	find_index and find_index_fwd	find_index_bwd	serious
find_map	find_map and find_map_fwd	find_map_bwd	serious
find_mapi	find_mapi and find_mapi_fwd	find_mapi_bwd	serious
filter	filter and filter_fwd	filter_bwd	minimum
find_all	find_all and find_all_fwd	find_all_bwd	minimum
filteri	filteri and filteri_fwd	filteri_bwd	serious
partition	partition and partition_fwd	partition_bwd	minimum
partition_map	partition_map and partition_map_fwd	partition_map_bwd	mild

[mikeshulman]

Isn't calling left-to-right "textual" a bit parochial? (-: People who read right-to-left might call that order "textual". Actually one could even make the same point about "forwards".

[favonia]

@mikeshulman I thought about it and felt it might be fine; in the areas where right-to-left text is prevailing, the list will probably be written from right to left as well. Therefore, "textual" and "forward/backward" will remain consistent. The problematic ones are "left" and "right".

[mikeshulman]

Oh, interesting. I guess I could live with forward/backward then, although I still think I prefer left and right, to match the existing names of folds.

It would be nice to survey a slightly larger number of functional programmers than we have here, to see what they would find more intuitive.

[mikeshulman]

I think part of my hesitation about "forward/backward" is that if "forwards" means left-to-right and "backwards" means right-to-left (at least for those of us who read left-to-right), then it seems that a Bwd should be called a forwards list because it grows from left to right, and a List a backwards one because it grows from right to left.

[mikeshulman]

Just to throw another option out there, we could have _ltr for left-to-right and _rtl for right-to-left.

[jonsterling]

Forwards/backwards really confuses me so very deeply, for much the reasons @mikeshulman is mentioning... One could really draw almost any conclusion from the naming...

I think I really like _ltr and _rtl.

[jonsterling]

Another possibility is to use temporal intuitions to avoid confusion — "fifo" vs "lifo".

[favonia]

@jonsterling Oh, that's why you mentioned temporal v.s. spatial---I finally had some ideas. I'm not sure how they apply to functions such as map and others, though. Which one is fifo and which one is lifo?

[mikeshulman]

I presume that Bwd.map_fifo is left-to-right and Bwd.map_lifo is right-to-left, since the leftmost part of a Bwd went In First. I can see arguments for that, but the issue I see is that by the same logic List.map_fifo would be right-to-left, which seems kind of confusing. I would prefer that to_list and of_list commute with pairs of list and bwd functions that have, or could have, the same name.