[erlang-questions] map elements in defined order

Richard Carlsson carlsson.richard@REDACTED
Fri Oct 27 10:49:43 CEST 2017


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


More information about the erlang-questions mailing list