Define specification for map

[jariji]

The properties:

• If keys(x) exists then map must preserve it: keys(map(f, x)) == keys(x).
• If iteration order is guaranteed by xs (isequal(xs, ys) implies all(isequal(x,y) for (x,y) in zip(x,y))) then map(f, xs) must preserve that order.
• If length(x) exists then map must preserve it: length(map(f, x)) == length(x).
• isequal(map(f ∘ g, x), map(f, map(g, x))). This disallows, for example, a stateful x that counts how many times map is called.

Therefore

• map(f, x::String)::String is disallowed since it fails to preserve keys(x) for multi-unit code points.
• map(f, ::Set)::Vector is allowed, since Set has length but no keys and no iteration order. map(f, ::Set)::Set would not be allowed, since it fails to preserve length for non-injective f.
• map(f, (;v)::Some) = Some(f(v)) is allowed, since it has none of keys, iterate, or length but still obeys the composition property.

Optional, to discuss, an extra property:

• isequal(map(identity, x), x) would disallow Set -> Vector and Generator -> Vector implementations. Tuple -> Tuple would still be ok.

---

Ref #57071, #51703

[vtjnash]

Thanks for writing this up. However, map is allowed to consume stateful iterators (eg eachline), so any property that rejects that isn't valid (eg the two claims on isequal outputs)

[LilithHafner]

Another (perhaps obvious) property we should have:

• map(f, x) calls f on every element of x and produces a collection containing the result of all of those calls with each result appearing exactly once.

This property is necessary to make map(f, x) = x and invalid implementation. This property could be relaxed to allow Set -> Set.

[aplavin]

map(f, x) calls f on every element of x

It's already not true for sparse arrays AFAIK.
And for a typical usecase of map with pure functions it's great to have the optimization opportunity, to only call f for unique elements when it makes sense.