[erlang-questions] [eeps] Maps

[Michael Truog]

I haven't seen it mentioned yet, so I thought I would mention it... sorry if this repeats what others have suggested:

It would help if we had a way to walk the tree representation of the Map.  I know it might be an uncommon use-case, but it probably would provide support for deep-updates and complex path usage (JSONPath, JSONQuery, or JSONSelect type of stuff, http://stackoverflow.com/a/8481733).  Walking the tree, could be emulated even if the data structure is not tree shaped due to a small size.

The particular use case I am thinking of, is for doing matching on the key value.  I have some trie source code here: https://github.com/okeuday/trie with a trie:find_match/2 function, which takes an exact string (list of integers) value and attempts to match it to stored key string patterns that possibly contain 1 or more "*" wildcard character (strings containing "**" do not exist, since the occurrence is considered an invalid entry).  A "*" wildcard character matches one or more characters in the exact string value provided as a trie:find_match/2 function argument.  The match could be ambiguous, except that it always finds the most exact match, going as deep into the tree as possible, and then iterating in alphabetical order (i.e., as exact as possible, based on the prefix).  The opposite functionality (pattern matching exact string keys stored) is provided by trie:fold_match/4.  This type of functionality should require an incomplete traversal of the tree structure (a set
of functions that provide iterator behavior).

Thanks,
Michael

On 05/13/2013 11:27 AM, Björn-Egil Dahlberg wrote:
> Hi!
>
> Thank you all who have contributed in this discussion!
>
> Instead of replying to every mail I will try to address and correct some misconceptions.
>
> - As stated earlier by several people. Maps are *not* Frames.
>
> - There are several semantic and syntax differences. Most notably arbitrary terms as keys.
>
> - The implementation of Maps will have Frame like characteristics for "simple" Maps, i.e. small number of associations (at most ~30 - 40 entries) and immediates as keys. Granted, the type information will not be there at compile-time, and Maps will not have literals as keys (as proposed in Frames), but should otherwise be comparable in performance with Frames for those cases. I also believe this would cover most of the use-cases as a record-replacement.
>
> The internal structure in the "simple" case would best be described with two tuples (but it would not have some other header and might have additionally meta-data in the header if necessary):
>
>     { {K1, ...,Kn}, V1, ..., Vn}
>
> This structure will also allow key-sharing between Maps of the same "type", i.e. Maps with identical keys.
>
> When the Map no longer satisfies this "simple" arrangement it will transform into a tree and loose the previous characteristics and gain the characteristics of a tree.
>
>
> - Maps are of type ordered set and follows term order. This has several implications.
>   - Term order does not distinguish between types float and integer.
>   - If data is stored in a tree where we search entries based on keys and we do so by term order. Since term order does not distinguish between float and integer, floats and integers which are equal occupy the same place.
>   - When iterating over keys in a Map it is done so in Term order, or reversed Term order, meaning it is expected that floats and integer are mixed, ex. 1 < 2.0 < 3 < 4.0 < 5 < 6.0. If we distinguish between floats and integers in Maps, let's say integer < doubles, the previous order would be, ex: 1 < 3 < 5 < 2.0 < 4.0 < 6.0. We would no longer iterate in Term order and this would not be consistent with the rest of Erlang, hence unacceptable.
>
> Maps emulates the behaviour of ETS ordered set in this sense.
>
> I think we can all agree that this is an unfortunate feature of Erlangs term order. I also agree that it would be best to have *matching* only, and not *equals* but I don't see how this could be achieved easily. At least not in an acceptable way. For example, we cannot achieve this by specifying our own Term order since that would violate iteration order, printing order, etc, or at least expected order.
>
> As noted previously, if we had Maps of type set we would not have this problem. However, since Maps needs to fit into Erlangs term order, Maps needs to be ordered (unless we could somehow abandon this strict rule).
>
>
> - Deep updates of Maps are not covered by this EEP. We would welcome suggestions on this.
>
> Thank you!
>
> Regards,
> Björn-Egil
>
> On 2013-05-08 16:18, Björn-Egil Dahlberg wrote:
>> Hi everyone!
>>
>> We finally have a Maps EEP for you. This will get you an idea on what we are working on. Some of the ideas presented here was presented at Erlang Factory SF Bay Area 2013.
>>
>> I am sure that there will be some discussions about the contents of this EEP and I hope the discussions will be both fruitful and civilized.
>>
>> The journey of Maps and this EEP has been long and by no means a straight-forward or continuous one. I had a crystal clear picture of what I wanted Maps to be when we first started discussing it within OTP about two-three years ago. This EEP resembles that vision but it has had a lot of contributions of other ideas from both within and outside of OTP.
>>
>> The idea was a functional data-type, a syntax aware mapping of key-value associations with pattern matching. A syntax similar to records but without the hazzle 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 not an approach to replace records. It was meant to replace records where suitable and in other regards not be a replacement but its own thing.
>>
>> From the community there has been many wishes of a Map like data-type and a few suggestions.  The one suggestion that stands out is of course the Frames proposal from Richard O'Keefe. It is the most complete proposal I've seen and is very well thought out. Its goal is to be a record replacement and the proposal satisfies this goal very well.
>>
>> - If Frames are that good, why a separate EEP?
>> - It boils down to goals and constraints.
>>
>> A record replacement is just that, a replacement.
>> It's like asking the question, "What do we have?" instead of "What can we get?"
>> The instant rebuttal would be "What do we need?" I say Maps.
>>
>> Frames has certainly influenced Maps. In many regards Maps also encompasses Frames but Maps tries to do more. I think the most significant difference would be, arbitrary terms as keys and how many different keys we would have in a Map. In the end I believe they are two different things and have different goals.
>>
>> Some Notes and Disclaimers:
>>
>> Later iterations of Maps has gone through some changes, most significantly,
>>
>>   * From a set of key-values to a ordered set of key-value associations
>>
>> I was originally against this change since it forces restrictions on the implementation and it illuminates the lack of distinction between arithmetic order and term order, i.e. the problem of mixing integer and float types as keys in a tree. However, I was later persuaded that key ordering is necessary. We have to respect the totalitarian order of terms.
>>
>> Considerations has been made on how to, if at all possible, apply Frames characteristics to Maps. Most significantly memory space and key-sharing characteristics. This is not detailed in the EEP though, just mentioned.
>>
>> The function interface has had many revisions as well. At some stage the API was considered to be a drop-in-replacement for `dict` and thus would have the same function-names. This goal/constraint was dropped by Technical Board decision recently.
>>
>> From the very beginning Maps was envisioned to have the ability to bind variables derived from the environment. Like this:
>>
>>     function(K1, #{ K1 := K2, K2 := V }) -> V.
>>
>> This feature is a beast. Powerful and scary. It is not confined to only Maps but should also be applicable to other types as well:
>>
>>     function(Skip, <<_:Skip/binary, Value:Size, _/bits>>, Size) -> Value.
>>
>> It is uncertain how effective such an implementation would be and in the end we might not want this feature at all.
>>
>> In this EEP we will describe syntax and semantics of Maps but very little is disclosed of its actual implementation. Current prototypes stems from using sparse tuples in a HAMT-like data structure and tuple-like data structures. The HAMT-like data structure is discontinued and will be replaced by some ordered tree.
>>
>> The proposal is included as an attachment but can also be viewed at this git-repository:
>> https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md
>>
>>
>> Regards,
>> Björn-Egil Dahlberg
>> Erlang/OTP
>>
>>
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>
>
>
> _______________________________________________
> eeps mailing list
> eeps@REDACTED
> http://erlang.org/mailman/listinfo/eeps

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130514/ffae02a4/attachment.htm>