<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Mon, May 9, 2016 at 2:02 PM,  <span dir="ltr"><<a href="mailto:ok@cs.otago.ac.nz" target="_blank">ok@cs.otago.ac.nz</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div><div>> On Mon, May 9, 2016 at 2:01 AM, Richard A. O'Keefe <<a href="mailto:ok@cs.otago.ac.nz" target="_blank">ok@cs.otago.ac.nz</a>><br>
> wrote:<br>
><br>
>> I thought maps were *not* intrinsically ordered.<br>
>><br>
><br>
> They aren't.<br>
><br>
> You don't need a defined order in order to iterate using first and next,<br>
> see for example how ets:first/ets:next work on a set.<br>
<br>
</div></div>You *do* need a defined order for iteration to *make sense*.<br></blockquote><div><br></div><div>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.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
If the value of maps:first_key(Map) and maps:next_key(Map, Key)<br>
is not *determined* by the *value* of Map (without reference to<br>
the history of how the Map was built or any other inscrutable<br>
properties such as where it happens to be stored), then these<br>
things just aren't functions.<br></blockquote><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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.</div></div></div></div>