[erlang-questions] map elements in defined order

[Ulf Wiger]

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>:

> 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>:
>
>> 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>:
>>
>>> 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
>>> 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/f04b2706/attachment.htm>