Maps have a defined order independent of implementation.
The changed ordering in OTP 26 of atom keys in maps is a totally internal affair. The only visible effect is the undefined traversal order exposed by io:format, maps:iterator and the external format.
4 Likes
We can’t, not without a breaking change. Honestly… maybe something we have to accept, maybe by raising or warning on it. At some point, it is ok to say that old code needs work to compile on modern OTP. We broke old rebar forcing a lot of people to port it to rebar3 a few years ago after all.
To go back to the original question: Map key order, BIF, no new operators, and yes, please break or yell on comparing floats and integers. Erlang is strongly typed, and this particular behavior with floats have been a source of bugs multiple time for me.
1 Like
I’m a little concerned about the phrasing of things here, which may confuse things more than they should have to. The order defined by the operators <, =<, >, >=, ==, and /= is an arithmetic term order (== being arithmetic equality), and it is a total order, precisely because it does not separate integers from floats and considers the integer and float forms of the same number to be the same object. This is great for how humans work with numbers and orderings; both individual numbers as well as tuples of numbers or lists of numbers get the order you expect, and it’s total. Nothing peculiar at all about it.
Only when doing computery things is this often not what you want. In data structures we want fast comparisons on keys, and not have to consider whether we should promote an int to a float just for comparing. We probably do not care about the order between floats and ints, since ints are common as keys, while using floats as keys is rarely a good idea except for things like memoizing, and we typically want to have separate entries for 3 and 3.0. The built-in pattern matching behaves like this, using the exact equality operators =:= and =/=.
It is when we combine < and ´>´ with =:= that we don’t get a total order:
case X of
Y -> equal; # uses =:=
_ when X > Y -> greater;
_ when X < Y -> less
end
if X is 3 and Y is 3.0, none of the clauses match, because we have a mix of operators. What we need is an alternative total order, so we don’t end up with this mix, with the new operators :< and >:. Using these in the above code, one clause would always match, since we’d have integer() < float() (in the map key ordering).
I don’t think the “glitch at zero” solution is something to be sad about. I have seen other functional languages do the exact same thing in order to get a total order on floats. I also think that the maps ordering on keys is quite perfect as it is, and that there is nothing weird in saying that one map is less than some other map, any more than saying one tuple {2, 1} is less than another tuple {2, 2}, given that there is an ordering on the keys.
I think that the candidate named “the exact term order” in the proposal, which would consider an integer to be infinitesimally greater than the corresponding float, would cause too many problems. For one thing, you’d get the unwanted result that converting maps into lists of keys/value pairs would produce a different order than when comparing them as maps. And for several “computery” applications, you’d want integers and floats grouped separately by a sort, so you’d have to implement yet another order anyway on top of this.
5 Likes
Precisely. If the =:= and =/= operators had not been introduced, it would have been “impossible” (we would have to be without is_float() and is_integer() too, and match them as equal) to distinguish between a float == an integer. And now when we have them there is no total order they (and pattern matching) are part of.
I think it is less obvious since a tuple has got a very natural element order numbered 1…N, so defining a sort order is easy. For a data structure intended for lookup access, key order as well as sort order is uninteresting. A sort order has to be constructed/forced, and there are multiple ways with different trade-offs.
If that had been the case, the map key order would have been a stronger contestant for me. But now to sort maps by converting them to simpler terms, since they are sorted on size first then keys before values, I suppose you would have to use something like:
MX =
lists:unzip(
lists:sort(
fun (KV1, KV2) -> element(1, KV1) =:< element(1, KV2) end,
maps:to_list(M)),
{list_to_tuple(element(1, MX), list_to_tuple(element(2, MX))
and then compare these terms according to the maps key order.
That conversion is unfortunately not as useful as maps:to_list(M).
1 Like
It is important to have comparison operations that behave themselves sensibly
for numbers.
It is useful to have a total order on terms.
But what are the fundamental requirements for ordering?
(1) X =< X
(2) X =< Y and Y =< Z implies X =< Z
(3) X =< Y and Y =< X implies X equals Z
(4) X =< Y or Y =< X
(5) X equals X
(6) X equals Y and Y equals Z implies X equals Z.
Modulo some rather desperate hand-waving over “equals”,
this is true of the arithmetic order. The equivalence
induced by =< in Erlang puts {0,-0.0,0.0} in the same
equivalence class, but that’s OK.
When one of X,Y is exact (an integer, say) and the
other is inexact (a float, say), it is important to
compare them by converting the inexact number to an
exact one rather than the other way around. Otherwise
you can easily break (6).
But we’re not talking about total orders in general
at this point, but an ARITHMETIC total order. And for
those we have expectations like
(7) X - Y equals 0 implies X equals Y.
And here, I’m afraid, Erlang’s arithmetic order fails.
Consider X = 255 + 1, Y = 2.055.
Then X-Y == 0 but it is not true that X == Y.
Ada and Haskell forbid mixing integers and floats
without explicit conversions. It’s a very good idea,
even for dynamic programming languages.
The problem comes when we confuse arithmetic equality
with identity. We expect that for any pure F,
(8) X equals Y implies F(X) equals F(Y)
and that just isn’t true in Erlang for several
built-in F when equals is taken to be == .
We are driven to the conclusion that
the arithmetic ordering in Erlang
IS a total order
but is NOT an arithmetic total order.
due in large part to mashing up integers and floats.
As for the term order, the only thing that really really matters
is that ALL uses of it be CONSISTENT with the rules and with each
other.
It is important to compare ex
1 Like
Curse this formatted mail nonsense!
Consider X = 255 + 1, Y = 2.055.
Was, of course, X = 2 “raised to the power” 55 + 1,
Y = 2.0 “raised to the power” 55.
1 Like
I confirm the behaviour:
1> X = 1 bsl 53.
9007199254740992
2> Y = float(X).
9.007199254740992e15
3> Z = X + 1.
9007199254740993
4> X - Y == 0.
true
5> X == Y.
true
6> Z - Y == 0.
true
7> Z == Y.
false
I would say that
is an assumption about arithmetic operations that we cannot expect to hold for the arithmetic model that we have.
Floating point values are exact, but floating point operations may be inexact.
Even a simple operation like Z - Y may cause rounding that produces exactly 0.0, while the values of Z and Y do not compare equal. In this case it is the implicit conversion from integer to float of Z that rounds off one bit.
The floating point value 2.0^53 (math:pow(2.0, 53)) has got an exact value that is equal to the integer 1 bsl 53 and should not be equal to any other integer. Therefore the floating point value is converted to an exact integer representation when being compared to an integer, if possible, to not break your (6), as you say.
I would say that the arithmetic ordering in Erlang IS an arithmetic total order, but floating point operations such as automatic conversion from integer to float may cause rounding errors.
1 Like