<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">I haven't seen it mentioned yet, so I
thought I would mention it... sorry if this repeats what others
have suggested:<br>
<br>
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,
<a class="moz-txt-link-freetext" href="http://stackoverflow.com/a/8481733">http://stackoverflow.com/a/8481733</a>). Walking the tree, could be
emulated even if the data structure is not tree shaped due to a
small size.<br>
<br>
The particular use case I am thinking of, is for doing matching on
the key value. I have some trie source code here:
<a class="moz-txt-link-freetext" href="https://github.com/okeuday/trie">https://github.com/okeuday/trie</a> 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:<span class="c">fold_match/4</span>.
This type of functionality should require an incomplete traversal
of the tree structure (a set of functions that provide iterator
behavior).<br>
<br>
Thanks,<br>
Michael<br>
<br>
On 05/13/2013 11:27 AM, Björn-Egil Dahlberg wrote:<br>
</div>
<blockquote cite="mid:519130AC.8090303@erlang.org" type="cite">
<meta http-equiv="Context-Type" content="text/html;
charset=ISO-8859-1">
<div class="moz-cite-prefix">Hi!<br>
<br>
Thank you all who have contributed in this discussion!<br>
<br>
Instead of replying to every mail I will try to address and
correct some misconceptions. <br>
<br>
- As stated earlier by several people. Maps are <b>not</b>
Frames.<br>
<br>
- There are several semantic and syntax differences. Most
notably arbitrary terms as keys.<br>
<br>
- 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.<br>
<br>
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):<br>
<br>
{ {K1, ...,Kn}, V1, ..., Vn}<br>
<br>
This structure will also allow key-sharing between Maps of the
same "type", i.e. Maps with identical keys. <br>
<br>
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.<br>
<br>
<br>
- Maps are of type ordered set and follows term order. This has
several implications.<br>
- Term order does not distinguish between types float and
integer. <br>
- 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.<br>
- 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.<br>
<br>
Maps emulates the behaviour of ETS ordered set in this sense.<br>
<br>
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.<br>
<br>
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).<br>
<br>
<br>
- Deep updates of Maps are not covered by this EEP. We would
welcome suggestions on this.<br>
<br>
Thank you! <br>
<br>
Regards,<br>
Björn-Egil<br>
<br>
On 2013-05-08 16:18, Björn-Egil Dahlberg wrote:<br>
</div>
<blockquote cite="mid:518A5ED1.2030507@erlang.org" type="cite"> Hi
everyone! <br>
<br>
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.<br>
<br>
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. <br>
<br>
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. <br>
<br>
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 <b
class="moz-txt-star"><span class="moz-txt-tag"></span></b><span
class="moz-txt-star">thing</span><b class="moz-txt-star"><span
class="moz-txt-tag"></span></b>. <br>
<br>
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. <br>
<br>
- If Frames are that good, why a separate EEP? <br>
- It boils down to goals and constraints. <br>
<br>
A record replacement is just that, a replacement. <br>
It's like asking the question, "What do we have?" instead of
"What can we get?"<br>
The instant rebuttal would be "What do we need?" I say Maps. <br>
<br>
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. <br>
<br>
Some Notes and Disclaimers: <br>
<br>
Later iterations of Maps has gone through some changes, most
significantly, <br>
<br>
* From a set of key-values to a ordered set of key-value
associations <br>
<br>
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. <br>
<br>
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.<br>
<br>
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.<br>
<br>
From the very beginning Maps was envisioned to have the ability
to bind variables derived from the environment. Like this: <br>
<br>
function(K1, #{ K1 := K2, K2 := V }) -> V. <br>
<br>
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: <br>
<br>
function(Skip, <<_:Skip/binary, Value:Size,
_/bits>>, Size) -> Value. <br>
<br>
It is uncertain how effective such an implementation would be
and in the end we might not want this feature at all.<br>
<br>
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.<br>
<br>
The proposal is included as an attachment but can also be viewed
at this git-repository:<br>
<a moz-do-not-send="true" class="moz-txt-link-freetext"
href="https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md">https://github.com/psyeugenic/eep/blob/egil/maps/eeps/eep-0043.md</a><br>
<br>
<br>
Regards, <br>
Björn-Egil Dahlberg <br>
Erlang/OTP <br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
erlang-questions mailing list
<a moz-do-not-send="true" class="moz-txt-link-abbreviated" href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a>
<a moz-do-not-send="true" class="moz-txt-link-freetext" href="http://erlang.org/mailman/listinfo/erlang-questions">http://erlang.org/mailman/listinfo/erlang-questions</a>
</pre>
</blockquote>
<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
eeps mailing list
<a class="moz-txt-link-abbreviated" href="mailto:eeps@erlang.org">eeps@erlang.org</a>
<a class="moz-txt-link-freetext" href="http://erlang.org/mailman/listinfo/eeps">http://erlang.org/mailman/listinfo/eeps</a>
</pre>
</blockquote>
<br>
</body>
</html>