[erlang-questions] Wanted additions to the maps module?

Lukas Larsson garazdawi@REDACTED
Mon May 9 15:05:04 CEST 2016


On Mon, May 9, 2016 at 2:02 PM, <ok@REDACTED> wrote:

> > On Mon, May 9, 2016 at 2:01 AM, Richard A. O'Keefe <ok@REDACTED>
> > wrote:
> >
> >> I thought maps were *not* intrinsically ordered.
> >>
> >
> > They aren't.
> >
> > You don't need a defined order in order to iterate using first and next,
> > see for example how ets:first/ets:next work on a set.
>
> You *do* need a defined order for iteration to *make sense*.
>

I don't really like dealing in absolutes. I can see scenarios where it
would be useful to have that and scenarios where I'd rather get the lookup
speed that not having it gives. One idea could be to have both so that the
user could pick and choose, i.e. ofirst/onext and ufirst/unext. However the
iterator without the ordering guarantee will always be as fast or faster
then the iterator with the ordering guarantee. If I've done my thinking
correctly, the complexity of the iterator would be something like O(n/2)
for ordered and O(log(n)) for unordered iterators.


> If the value of maps:first_key(Map) and maps:next_key(Map, Key)
> is not *determined* by the *value* of Map (without reference to
> the history of how the Map was built or any other inscrutable
> properties such as where it happens to be stored), then these
> things just aren't functions.
>

Seems kind of harsh to disqualify them from the entire set of functions,
just because they aren't pure and/or the construction of the term doesn't
influence it's final state.

What we are leaning towards right now is to define that two maps that have
the same keys also have the same iteration order, no matter how the maps
have been created. So map "A = #{ a => a }, B = A#{ b => b }." and "C = #{
b => a }, D = A#{ a => b }." would be guaranteed to iterate in the same
order. So "{K,V} = maps:first(B) = maps:first(D).", but we don't guarantee
which key K was bound to. So I guess in part we agree with you, it is just
a matter of deciding how much we have to/should guarantee about the order
of the iterators.

Btw, feels like we have had exactly this discussion when looking at maps a
couple of years ago, but I can't find any references to it. To order or not
to order, that is the question.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20160509/bf7e43be/attachment.htm>


More information about the erlang-questions mailing list