Document/decide ordering guarantees for map

[gbaraldi]

Unlike reduce where we explicitly don't give any ordering guarantees, we don't say anything for map.

IMO we shouldn't give guarantees for map and add the equivalent to foldl as a function that does have the guarantees. The goal being that map should be able to be parallelized/SIMD

[CameronBieganek]

On a closely related note, it would be nice if the docs did provide some kind of guarantee on the order of the output. I struggle to find the right language to describe the criterion, but, for example, map(f, [x₁, x₂, ..., xₙ] should be equal to [f(x₁), f(x₂), ..., f(xₙ)]. The docstring should make it clear that [3, 2] is an invalid output from map(sqrt, [4, 9]).

In fact, I opened an issue about this a while ago: #50857.

[jariji]

foreach needs order documentation, too.

[mikmoore]

I think it's worth keeping in mind that access order and output order are different things.

map's documented use it to Transform collection c by applying f to each element. It would take a rather liberal reading (and I don't think anyone is suggesting) to permit map(identity,[1,2]) == [2,1]. As an elementwise operation, there should not be explicit interactions between elements and one is only required to extend (perhaps our language should be more clear?) this non-interactivity to the output container to prohibit such shenanigans. But it wouldn't necessarily have to be evaluated in the same order it outputs. Output ordered-ness would not apply when used on unordered containers (like Set/Dict), but map is already explicitly undefined for such (for now).

I'm actually a little torn here, because I wouldn't hate if something stateful could be evaluated predictably (i.e., with a defined order). I don't often use it with map, but sometimes I use a mutable-state function with its cousin ntuple and depend on this. Of course, when the compiler can prove statelessness it can transform the operation to SIMD anyway. That aside, there's a narrow regime that satisfies both "too complicated to prove statelessness" and "would benefit from SIMD", I think. So guaranteeing forward-order evaluation has merits in the face of probably-unlikely costs.

The explicitly-documented relationship between foreach and map does indicate that we should strongly consider giving them the same evaluation order semantics, but the fact that foreach is exclusively useful for side effects suggests it should have a definite forward ordering on ordered arguments. It's worth at least thinking about evaluation semantics with broadcast, as well, although broadcast is not commonly used with stateful functions (except rand and friends) so perhaps it doesn't need to be unified.

[tpapp]

I would be fine with either saying that

1. map does not guarantee evaluation order, so don't depend on it, which allows potential optimizations (maybe?), but at the same time have a deterministic in-order version, either in Base or (less ideally) a package,
2. make map guarantee evaluation order, and if future optimizations require out-of-order semantics, name that something else.

But not saying anything about this means that map is practically deterministic, but one cannot rely on it for future code.

Maybe triage could consider a statement about this?

[nsajko]

IMO we shouldn't give guarantees for map and add the equivalent to foldl as a function that does have the guarantees.

• Instead of adding another function similar to map, an additional argument (of singleton type, I guess) could be introduced that would specify/request certain ordering guarantees. C++ seems to have something similar in the spec: https://en.cppreference.com/w/cpp/algorithm/execution_policy_tag_t

  • This could apply to both map and foreach, maybe elsewhere, too.

• IMO parallelization/unordered execution should not be allowed by default, as that seems like it'd be more disruptive.

[jariji]

#43910 is Takafumi's PR to make map parallel when it 1) can be proved safe and 2) will likely be faster.