# Maps:to_list/1 element order. Classic List Threaded 7 messages Open this post in threaded view
|

## Maps:to_list/1 element order.

Hi

Even though documentation indicates that:

to_list(Map) -> [{Key, Value}]

### Types

Map = map()
Key = Value = term()

Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
I did some testing using a bit modified example offered in documentation:

(x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{1,"Last entered"},
{42,value_three},
{1337,"value two"},
{"a",1}]

When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:

(x@MacBook-Pro)48>
(x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{-1337,"value two"},
{1,"Last entered"},
{42,value_three},
{"a",1}]

Could one relay on this always being the case?
A I need this list to be sorted, I would hate to attempt sorting the already sorted list.

V/

Open this post in threaded view
|

## Re: Maps:to_list/1 element order.

No, and it is subtle:

L1 = [{X, X} || X <- lists:seq(1,32)].
L1 == maps:to_list(maps:from_list(L1)).
true

L2 = [{X, X} || X <- lists:seq(1,33)].
L2 == maps:to_list(maps:from_list(L2)).
false

At 32+ elements, Maps change their representation order to a hash array mapped trie. These are not generally ordered, but provide very fast lookups. In practice you are O(1) bound with a couple of memory reads. In theory you are O(lg n) bound width a branch factor of 32.

If you need the order, you need to use a representation which maintains the order.

On Fri, Feb 28, 2020 at 10:45 AM Valentin Micic <[hidden email]> wrote:
Hi

Even though documentation indicates that:

to_list(Map) -> [{Key, Value}]

### Types

Map = map()
Key = Value = term()

Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
I did some testing using a bit modified example offered in documentation:

(x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{1,"Last entered"},
{42,value_three},
{1337,"value two"},
{"a",1}]

When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:

(x@MacBook-Pro)48>
(x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{-1337,"value two"},
{1,"Last entered"},
{42,value_three},
{"a",1}]

Could one relay on this always being the case?
A I need this list to be sorted, I would hate to attempt sorting the already sorted list.

V/

--
J.
Open this post in threaded view
|

## Re: Maps:to_list/1 element order.

 In reply to this post by Valentin Micic-6 This was discussed at length in a previous thread: http://erlang.org/pipermail/erlang-questions/2017-October/093981.htmlThe short answer is "no", you can't rely on the order, and this should perhaps be more clearly documented. In the future, it might be nice with some 'canonical' option to e.g. term_to_binary/2, to ensure that encoding is consistent. This would of course come at a cost. BR, Ulf W Den fre 28 feb. 2020 kl 10:45 skrev Valentin Micic <[hidden email]>: > > Hi > > Even though documentation indicates that: > > to_list(Map) -> [{Key, Value}] > > Types > > Map = map() > Key = Value = term() > > > Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order. > > It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting. > I did some testing using a bit modified example offered in documentation: > > > (x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map). > [{1,"Last entered"}, >  {42,value_three}, >  {1337,"value two"}, >  {"a",1}] > > > > When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted: > > > (x@MacBook-Pro)48> > (x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map). > [{-1337,"value two"}, >  {1,"Last entered"}, >  {42,value_three}, >  {"a",1}] > > > Could one relay on this always being the case? > A I need this list to be sorted, I would hate to attempt sorting the already sorted list. > > Thanks in advance > > V/ >
Open this post in threaded view
|

## Re: Maps:to_list/1 element order.

 I should perhaps clarify that the cost of 'canonical' (in this case, sorting) would of course still be lower than calling lists:sort/1 to get what you need. Presumably, if you actually need the elements ordered, there will always be a cost. BR, Ulf W Den fre 28 feb. 2020 kl 10:58 skrev Ulf Wiger <[hidden email]>: > > This was discussed at length in a previous thread: > > http://erlang.org/pipermail/erlang-questions/2017-October/093981.html> > The short answer is "no", you can't rely on the order, and this should > perhaps be more clearly documented. In the future, it might be nice > with some 'canonical' option to e.g. term_to_binary/2, to ensure that > encoding is consistent. This would of course come at a cost. > > BR, > Ulf W > > Den fre 28 feb. 2020 kl 10:45 skrev Valentin Micic <[hidden email]>: > > > > Hi > > > > Even though documentation indicates that: > > > > to_list(Map) -> [{Key, Value}] > > > > Types > > > > Map = map() > > Key = Value = term() > > > > > > Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order. > > > > It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting. > > I did some testing using a bit modified example offered in documentation: > > > > > > (x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map). > > [{1,"Last entered"}, > >  {42,value_three}, > >  {1337,"value two"}, > >  {"a",1}] > > > > > > > > When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted: > > > > > > (x@MacBook-Pro)48> > > (x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map). > > [{-1337,"value two"}, > >  {1,"Last entered"}, > >  {42,value_three}, > >  {"a",1}] > > > > > > Could one relay on this always being the case? > > A I need this list to be sorted, I would hate to attempt sorting the already sorted list. > > > > Thanks in advance > > > > V/ > >
Open this post in threaded view
|

## Re: Maps:to_list/1 element order.

In reply to this post by Jesper Louis Andersen-2
Thanks, this clarifies it.
Much obliged.

V/

On 28 Feb 2020, at 11:56, Jesper Louis Andersen <[hidden email]> wrote:

No, and it is subtle:

L1 = [{X, X} || X <- lists:seq(1,32)].
L1 == maps:to_list(maps:from_list(L1)).
true

L2 = [{X, X} || X <- lists:seq(1,33)].
L2 == maps:to_list(maps:from_list(L2)).
false

At 32+ elements, Maps change their representation order to a hash array mapped trie. These are not generally ordered, but provide very fast lookups. In practice you are O(1) bound with a couple of memory reads. In theory you are O(lg n) bound width a branch factor of 32.

If you need the order, you need to use a representation which maintains the order.

On Fri, Feb 28, 2020 at 10:45 AM Valentin Micic <[hidden email]> wrote:
Hi

Even though documentation indicates that:

to_list(Map) -> [{Key, Value}]

### Types

Map = map()
Key = Value = term()

Returns a list of pairs representing the key-value associations of Map, where the pairs [{K1,V1}, ..., {Kn,Vn}] are returned in arbitrary order.

It appears that the list returned has been sorted in ascending order, using value of the key as a criterion for sorting.
I did some testing using a bit modified example offered in documentation:

(x@MacBook-Pro)47> f(Map), Map = #{42 => value_three,1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{1,"Last entered"},
{42,value_three},
{1337,"value two"},
{"a",1}]

When I changed 1337 to -1337, I get the result that indicates that the list of pairs is *not* returned in arbitrary order, but actually sorted:

(x@MacBook-Pro)48>
(x@MacBook-Pro)48> f(Map), Map = #{42 => value_three, -1337 => "value two","a" => 1, 1 => "Last entered"},maps:to_list(Map).
[{-1337,"value two"},
{1,"Last entered"},
{42,value_three},
{"a",1}]

Could one relay on this always being the case?
A I need this list to be sorted, I would hate to attempt sorting the already sorted list.

V/

--
J.