[erlang-questions] map elements in defined order
Sverker Eriksson
sverker.eriksson@REDACTED
Fri Oct 27 15:26:22 CEST 2017
Yes. All Erlang terms, including maps, have a globally defined,
implementation independent, total order.
The reason, for this "surprising" order of maps, is the alternative of
using the normal arithmetic order for keys is much worse.
If we want 1 and 1.0 to be different keys (which we do as we use
matching (=:=) to lookup keys)
then we need to order 1 and 1.0, and normal arithmetic term ordering
does not (1 == 1.0).
It has been discussed (more and less serious) to expose this
"map-key-order" with operators like :<, :>, =:<, >:=.
/Sverker
On 10/27/2017 03:13 PM, Ulf Wiger wrote:
> Actually, that's roughly what I started out assuming too, but it's not
> sufficient. Consider:
>
> 1> lists:sort([#{[-1.0] => 0}, #{[1] => 0}]).
> [#{[1] => 0},#{[-1.0] => 0}]
>
> You must dig into each structure and find occurrences of floats to
> determine whether they affect the ordering.
>
> But yes, the documented sort order should be stable across versions.
> This means, in practice, that it's safe to rely on the sorting
> properties of maps.
>
> BR,
> Ulf
>
> 2017-10-27 10:49 GMT+02:00 Richard Carlsson
> <carlsson.richard@REDACTED <mailto:carlsson.richard@REDACTED>>:
>
> My interpretation of the reference manual is that maps compare to
> each other like the tuples created by this transformation:
>
> t(Map) ->
> {Ks,Vs} = lists:unzip(lists:keysort(1, [{{if is_integer(K) ->
> 0; is_float(K) -> 1; true -> 2 end, K}, V} || {K,V} <-
> maps:to_list(M)])),
> list_to_tuple(Ks ++ Vs).
>
> For example:
>
> t(#{65 => "A", 2.71 => e, 1.0e308 => alot, pi => 3.14, [] => 0})
>
> yields
>
> {{0,65}, {1,2.71}, {1,1.0e308}, {2,pi}, {2,[]},
> "A", e, alot, 3.14, 0}
>
> Which:
> 1) should be independent of the underlying implementation and
> choice of hash function, and thus stable across future versions of
> Erlang;
> 2) is cumbersome to express using the normal term order over the
> basic data types, since float keys always sort higher than
> integers (not really following the rule of least surprise).
>
>
>
>
>
> /Richard
>
> 2017-10-27 9:25 GMT+02:00 Ulf Wiger <ulf@REDACTED
> <mailto:ulf@REDACTED>>:
>
> Actually, they ARE, in some ways.
>
> I should have been clearer. I was, of course, referring to the
> uses of records where they were never optimal in the first
> place, but were tolerated e.g. because of the great
> convenience of referencing elements by name in pattern-matching.
>
> Quoted from EEP-0043:
>
> «The idea was a data-type, a syntax-aware mapping of key-value
> associations with pattern matching. A syntax similar to
> records but without the hassle of compile-time dependency and
> with arbitrary terms as keys. Order was not important and it
> could be implemented with a Hash-Array-Mapped-Trie with good
> performance and memory trade-offs. This was a different
> approach than to replace records. It was meant to replace
> records where suitable and in other regards not be a
> replacement but its own _thing_.»
>
> Further, relevant to this discussion:
>
> «A restriction set on the implementation by the Erlang
> specification is that order is total, i.e. satisfies
> _antisymmetry, transitivity and totality_.
> ...
> - Ordered maps impose restrictions on the underlying
> implementation and a hashing approach will be nearly impossible.
> - The underlying structure does not need to be sorted, an
> order could be produced when needed,»
>
> The thing I tried to highlight was that "an order could be
> produced when needed" is actually a bit more involved than
> you'd think, given that no API function does it for you. At
> least if you want to reflect the internal sort order - given
> that the actual implementation is NOT as described in the EEP:
> "If a key or value differs, the order of the respective terms,
> in Erlang term order".
>
> You'd have to write your own sort function, in which you visit
> all elements of complex structures, finding all instances of
> floats and ensuring that they get the right priority.
>
> Or... you simply do this:
>
> lists:sort(fun(A, B) -> #{A => 0} =< #{B => 0} end,
> maps:to_list(Map))
>
>
> As evidenced e.g. by Benoit's comment above, I believe lots of
> people already rely on the order of map elements being IN SOME
> WAY stable. This is likely a brittle assumption, but one that
> may - in time - trap the OTP team into having to preserve the
> current APPARENT order.
>
> And the apparent order does appear to be sorted, as long as
> only maps of size =< 32 ("flatmaps") are inspected. For larger
> maps ("hashmaps"), the order of elements returned by
> maps:to_list/1 indeed appears arbitrary.
>
> BR,
> Ulf W
>
> 2017-10-27 6:01 GMT+02:00 zxq9 <zxq9@REDACTED
> <mailto:zxq9@REDACTED>>:
>
> On 2017年10月26日 木曜日 21:13:07 Ulf Wiger wrote:
> > ... to use as a replacement for records.
>
> But they are IN NO WAY a replacement for records.
>
> -Craig
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> <mailto:erlang-questions@REDACTED>
> http://erlang.org/mailman/listinfo/erlang-questions
> <http://erlang.org/mailman/listinfo/erlang-questions>
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED <mailto:erlang-questions@REDACTED>
> http://erlang.org/mailman/listinfo/erlang-questions
> <http://erlang.org/mailman/listinfo/erlang-questions>
>
>
>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20171027/5b7036d1/attachment.htm>
More information about the erlang-questions
mailing list