[eeps] Maps

Raimo Niskanen <>
Mon May 13 16:15:53 CEST 2013


The EEP is now in the repository as EEP 43:

    http://www.erlang.org/eeps/eep-0043.html

    https://github.com/erlang/eep/blob/master/eeps/eep-0043.md



On Wed, May 08, 2013 at 04:18:57PM +0200, 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

> <link href="markdown2.css" rel="stylesheet"></link>
>     Author:         Bj??rn-Egil Dahlberg <egil(at)Erlang.org>
>     Status:         Draft
>     Type:           Standards Track
>     Created:        04-Apr-2013
>     Erlang-Version: R17A
>     Post-History:	
> 
> EEP XXX: Maps
> ---
> 
> 
> Abstract
> ========
> 
> 
> The journey of Maps and this EEP has been long and by no means a
> straight-forward and 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 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 a different approach than 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 inspired and influenced Maps. In many regards Maps also
> encompasses Frames but Maps tries to do more. In the end I believe they are
> two different things and have different goals.
> 
> 
> This EEP suggests a new built in data-type for Erlang, the map, 
> `#{ Key => Value }`.
> 
> 
> The new data-type shall have semantics, syntax and operations that:
> 
>  * provides an association set from key terms to value terms which can be
>    constructed, accessed and updated using language syntax
>  * can be uniquely distinguished from every other data-type in the language
>  * has no compile-time dependency for constructing, accessing or updating
>    contents of maps nor for passing maps between modules, processes or over
>    Erlang distribution
>  * can be used in matching expressions in the language
>  * has a one-to-one association between printing and parsing the data-type 
>  * has a well defined order between terms of the type and other Erlang types
>  * has at most O(log N) time complexity in insert and lookup operations, where 
>    N is the number of key-value associations.
> 
> Similar data-types exists in other languages, i.e.  [perl hashes][perl-hashes],
> [ruby hashes][ruby-hashes], [python dictionaries][python-dict], or
> [scala maps][scala-maps].
> 
> 
> Specification
> =============
> 
> A map `M` consists of a number of *associations* and keeps an association
> from key terms `K1..Kn` to value terms `V1..Vn` where no two keys are *equal*.
> Any term, compounded or otherwise, is a viable key or value. Terms of type Map
> are recognized by guard tests `erlang:is_map/1`. There are no operators
> acting on maps. Within maps there are two infix operators. An association
> operator, `=>`, pairs a key to a value and is used in creation and updates.
> A set-value operator, `:=`, is used to update a value on an already
> existing and matching key. The set-value operator is also used in matching
> to get the associated value from a key.
> 
> 
> ## Terminology ##
> 
> The *size* of a map is the number of associations in its set.
> 
> An *association* is a key-value pair of key *K* to value *V* in a Map.
> 
> Two keys, `K1` and `K2` are *equal* if, `true = K1 == K2`.
> 
> Two keys, `K1` and `K2` are *matching* if, `true = K1 =:= K2`.
> 
> Syntax
> ------
> 
> Defined syntax for declaring, updating and matching maps.
> 
> ### Construction syntax ###
> 
> Constructing a new map is done by letting an expression `K` be associated to
> another expression `V`:
> 
>     #{ K => V }
> 
> New maps may include multiple associations at construction by listing every
> association:
> 
>     #{ K1 => V1, .. Kn => Vn }
> 
> An empty map is constructed by not associating any terms with each other:
> 
>     #{}        
> 
> All keys and values in the map are terms. Any expression is first evaluated and
> then the resulting terms are used as *key* and *value* respectively.
> 
> Keys and values are separated by the `=>` arrow and associations are
> separated by `,`.
> 
> Examples:
> 
>     M0 = #{},                   % empty map
>     M1 = #{ a => <<"hello">> }, % single association with literals
>     M2 = #{ 1 => 2, b => b },   % multiple associations with literals
>     M3 = #{ A => B },           % single association with variables
>     M4 = #{ {A, B} => f() }.    % compound key associated to an evaluated expression
> 
> 
> where, `A` and `B` are any expressions and `M0` through `M4` are the resulting
> map terms.
> 
> If two equal keys are declared, the latter key will take precedent.
> 
> Example:
> 
>     1> #{ 1 => a, 1 => b }.
>     #{ 1 => b }
>     2> #{ 1.0 => a, 1 => b }.
>     #{ 1 => b }
>     
> The order in which the expressions constructing the keys and their
> associated values are evaluated is not defined. The syntactic order of
> the key-value pairs in the construction is of no relevance, except in
> the above mentioned case of two keys comparing equal.
> 
> A simple BNF grammar for the construction follows:
> 
>      <map-construct>  ::= '#{' <key-value-exprs> '}'
>     <key-value-exprs> ::= /* empty */
>                         | <key-value-list>
>      <key-value-list> ::= <key-value-assoc> 
>                         |??<key-value-assoc> ',' <key-value-list>
>     <key-value-assoc> ::= <expr> '=>' <expr>
>                <expr> ::= <Erlang-expression>
> 
> ### Update syntax ###
> 
> Updating a map has similar syntax as constructing it.
> 
> An expression defining the map to be updated is put in front of the expression
> defining the keys to be updated and their respective values.
> 
>     M#{ K => V }
> 
> where `M` is an term of type map and `K` and `V` are any expression.
> 
> If key `K` does not *equal* any existing key in the map, a new association
> will be created from key `K` to value `V`.  If key `K` is *equal* to an existing
> key in map `M` its associated value will be replaced by the new value `V` *and*
> the new key `K` will replace the old key if the key does not *match*. In both
> cases the evaluated map expression will return a new map.
> 
> If `M` is not of type map an exception of type `badmap` is thrown.
> 
> To only update an existing value, the following syntax is used,
> 
>     M#{ K := V }
> 
> where `M` is an term of type map, `V` is an expression and `K` is an expression
> which evaluates to an existing key in `M`.
> 
> If key `K` does not *match* any existing keys in map `M` an exception of type
> `badarg` will be triggered at runtime. If a *matching* key `K` is present in
> map `M` its associated value will be replaced by the new value `V` and the
> evaluated map expression returns a new map.
> 
> If `M` is not of type map an exception of type `badmap` is thrown.
> 
> Examples:
> 
>     M0 = #{},
>     M1 = M0#{ a => 0 },
>     M2 = M1#{ a => 1, b => 2 },
>     M3 = M2#{ "function" => fun() -> f() end },
>     M4 = M3#{ a := 2, b := 3 }.  % 'a' and 'b' was added in `M1` and `M2`.
> 
> where `M0` is any map. It follows that `M1 .. M4` are maps as well.
> 
> 
> More Examples:
> 
>     1> M = #{ 1 => a },
>     #{ 1 => a }
> 
>     2> M#{ 1.0 => b }.
>     #{ 1.0 => b }.
> 
>     3> M#{ 1 := b }.
>     #{ 1 => b }
> 
>     4> M#{ 1.0 := b }.
>     ** exception error: bad argument
> 
> 
> As in construction, the order in which the key and value expressions
> are evaluated are not defined. The
> syntactic order of the key-value pairs in the update is of no
> relevance, except in the case where two keys compare equal, in which
> case the latter value is used.
> 
> A simple BNF grammar for map updates follows:
> 
>      <map-construct>  ::= <map-expr> '#{' <key-value-exprs> '}'
>     <key-value-exprs> ::= /* empty */
>                         | <key-value-list>
>      <key-value-list> ::= <key-value> 
>                         |??<key-value> ',' <key-value-list>
>           <key-value> ::= <key-value-assoc>
>                         | <key-value-exact>
>     <key-value-assoc> ::= <expr> '=>' <expr>
>     <key-value-exact> ::= <expr> ':=' <expr>
>            <map-expr> ::= <Erlang expression evaluating to a term of type map>
>                <expr> ::= <Erlang expression>
> 
> 
> ### Accessing a single value ###
> 
> For accessing single values in maps, let us use an de-association:
> 
>     V = M#{ K }.
> 
> Where `M` is a Map and `K` is any term.
> 
> If key `K` is *equal* to an existing key in map `M` the associated value
> will be bound to `V`. If key `K` does not *equal* to any existing key in 
> map `M` an exception `badarg` will occur in runtime.
> 
> 
> Examples:
> 
>     M1 = #{ a => 1, c => 3 },
>     3 = M1#{ c }.
> 
>     M2 = #{ 1.0 => a },
>     a = M2#{ 1 }.
> 
> 
> 
> ### Matching syntax ###
> 
> Matching of key-value associations from maps, exemplified with the
> matching operator, is done in the following way:
> 
>     #{ K := V } = M
> 
> where `M` is any map. The key `K` has to be an expression with bound variables
> or a literals, and `V` can be any pattern with either bound or unbound variables.
> If variables in `V` are unbound, it will be bound to the value associated
> with the key `K`, which has to exist in the map `M`. If variables in `V` are
> bound, it has to match the value associated with `K` in `M`.
> 
> Example:
> 
>     M = #{ a => {1,2}},
>     #{ a := {1,B}} = M.
> 
> This will bind variable `B` to integer `2`.
> 
> 
> Similarly, multiple values from the map may be matched:
> 
>     #{ K1 := V1, .., Kn := Vn } = M
> 
> where keys `K1 .. Kn` are any expressions with literals or bound variables. If all
> keys exists in map `M` all variables in `V1 .. Vn` will be matched to the
> associated values of there respective keys.
> 
> If the matching conditions are not met, the match will fail, either with
> 
>   1. a `badmatch` exception, if used in the context of the matching operator
>      as in the example, 
>   2. or resulting in the next clause being tested in function heads and
>      case expressions.
> 
> Matching in maps only allows for `:=` as delimiters of associations.
> 
> The order in which keys are declared in matching has no relevance.
> 
> Duplicate keys are allowed in matching and will match each pattern associated
> to the keys.
> 
>     #{ K := V1, K := V2 } = M
> 
> Matching an expression against an empty map literal will match its type but
> no variables will be bound:
> 
>     #{} = Expr
> 
> This expression will match if the expression `Expr` is of type map, otherwise
> it will fail with an exception `badmatch`.
> 
> The grammar for the matching syntax is similar to that of construction.
> 
> #### Matching syntax: Example with literals in function heads ####
> 
> Matching of literals as keys are allowed in function heads.
> 
>     %% only start if not_started
>     handle_call(start, From, #{ state := not_started } = S) ->
>     ...
>         {reply, ok, S#{ state := start }};
>     
>     %% only change if started
>     handle_call(change, From, #{ state := start } = S) ->
>     ...
>         {reply, ok, S#{ state := changed }};
> 
> #### Matching syntax: Frequency example ####
> 
> More matching syntax, calculating frequency of terms in a list.
> 
>     freq(Is)                    -> freq(Is, #{}).
>     freq([I|Is], #{I := C} = M) -> freq(Is, M#{ I := C + 1});
>     freq([I|Is], M)             -> freq(Is, M#{ I => 1 });
>     freq([], M)                 -> maps:to_list(M).
> 
> Equivalent code with `gb_trees` for comparison:
> 
> 
>     freq(Is)        -> freq(Is, gb_trees:empty()).
>     freq([I|Is], T) ->
>         case gb_trees:lookup(I, T) of 
>             none       -> freq(Is, gb_trees:enter(I, 1), T);
>             {value, V} -> freq(Is, gb_trees:enter(I, V + 1, T))
>         end;
>     freq([], T) -> gb_trees:to_list(T).
> 
> #### Matching syntax: File information example ####
> 
> Old API's could be refined to use map syntax:
> 
>     1> {ok, #{ type := Type, mtime := Mtime }} = file:read_file_info(File).
>     2> io:format("type: ~p, mtime: ~p~n", [Type, Mtime]).
>     type: regular, mtime: {{2012,7,18},{19,59,18}}
>     ok
>     3>
> 
> ### Map comprehension syntax ###
> 
> Map comprehension declaration:
> 
>     M1 = #{ E0 => E1 || K := V <- M0  }
> 
> where `M0` is any Map, `E0` and `E1` are any erlang expression, `K` and `V`
> constitutes the pattern to be matched by each association in `M0`.
> 
> For each sequence in the generator an association is created from the evaluated
> expression `E0` to the evaluated expression `E1`. 
> 
> If `M0` is not a Map, then a runtime exception of type `{bad_generator, M0}`
> will be generated.
> 
> A simple BNF grammar for map comprehension follows:
> 
>           <comprehension> ::= '#{' <key-value-assoc> '||' <comprehension-exprs> '}'
>     <comprehension-exprs> ::= <comprehension-expr>
>                             | <comprehension-exprs> ',' <comprehension-expr>
>      <comprehension-expr> ::= <generator>
>                             | <filter>
>               <generator> ::= <key-value-exact> '<-' <expr>
>                  <filter> ::= <expr>
>         <key-value-assoc> ::= <expr> '=>' <expr>
>         <key-value-exact> ::= <expr> ':=' <expr>
>                    <expr> ::= <Erlang expression>
> 
> 
> Each association from all generators, which satisfies the filters, has an
> environment that consist of the initial environment and the environment
> for the association.  
> 
> Examples:
> 
>     M0 = #{ K => V*2  || K := V <- map() },
>     M1 = #{ I => f(I) || I <- list() },
>     M2 = #{ K => V    || <<L:8,K:L/binary,V/float>> <= binary() }.
> 
> Map generators may also be used in binary and list comprehensions.
> 
> Examples:
> 
>     B1 = << <<V:8>> || _ := V <- map() >>,
>     L1 = [ {K,V} || K := V <- map() ].
> 
> ### Dialyzer and Type specification ###
> 
> Keys known before hand can be specified directly and uniquely for a map.
> 
> 
>     -spec func(Opt, M) -> #{ 'status' => S, 'c' => integer() } when
>           Opt :: 'inc' | 'dec',
>             M :: #{ 'status' => S, 'c' => integer() },
>             S :: 'update' | 'keep'.
>     
>     func(inc, #{ status := update, c := C} = M) -> M#{ c := C + 1};
>     func(dec, #{ status := update, c := C} = M) -> M#{ c := C - 1};
>     func(_,   #{ status := keep } = M)          -> M.
> 
> It could also be specified by type only.
> 
>     -spec plist_to_map(Ls) -> #{ binary() => integer() } when
>           Ls :: [{binary(), integer()}].
>     
>     plist_to_map([], M) ->
>         M;
>     plist_to_map([{K,V}|Ls], M) when is_binary(K), is_integer(V) ->
>         plist_to_map(Ls, M#{ K => V });
>     plist_to_map([_|Ls], M) ->
>         plist_to_map(Ls, M).
> 
> It can similarly be specified as a type.
> 
>     -type map1() :: #{ binary() => integer() }.
>     -type map2() :: #{ <<"list1">> | <<"list2">> => [numbers()] }.
> 
> 
> Functions and Semantics
> -----------------------
> 
> *The module implementing the functions is currently named in plural, `maps` in the
> same spirit as `lists`, `gb_trees`, `sets` etc but the singular `map` is shorter
> and may be more desirable.*
> 
> 
> Functions and semantics for maps. Originally much inspiration was from
> Richard O'Keefes frames proposal.
> 
> ### Erlang module extension ###
> 
> ##### `erlang:is_map(M :: term()) -> boolean().`
> 
>   This function is a guard function.
>   
>   Syntax equivalence: `try #{} = M, true catch error:{badmatch,_} -> false end`.
>   
>   The function returns `true` if M is a map otherwise `false`.
>   
> ##### `erlang:map_size(M :: map()) -> non_neg_integer().`
> 
>   This function is a guard function.
>   
>   Syntax equivalence: *none*.
>   
>   The function returns the number of key-value pairs in the map.
>   
>   Same as, `maps:size(M)` and `length(maps:to_list(M))`.
>   
> ### maps module ###
> 
> ##### `maps:remove(K0 :: term(), M0 :: map()) -> M1 :: map().`
> 
>   Syntax equivalence: `#{ K => V || K := V <- M0, K =/= K0 }`.
>   *Only with comprehensions*
> 
>   The function removes the key `K0`, if it exists, and its associated value from
>   map `M0` and returns a new map `M1` without key `K0`.
> 
>   Same as, `maps:from_list([{K,V}||{K,V} <- maps:to_list(M0), K =/= K0])`
> 
> ##### `maps:get(K :: term(), M :: map()) -> V :: term().`
> 
>   Syntax equivalence: `M#{ K }`.
> 
>   Returns the value `V` associated with key `K` if map `M` contains a key
>   that *equals* `K`.  If no value is associated with key `K` then the call will
>   fail with an exception.
> 
>   Same as,`begin {value,{_,V}} = lists:keysearch(K, 1, maps:to_list(M)), V end`,
>   except for errors.
> 
> ##### `maps:keys(M :: map()) -> [K1, .., Kn].`
> 
>   Syntax equivalence: `[K || K := _ <- M]`.
> 
>   Returns a complete list of Keys, in sorted order, which resides within
>   map `M`.
> 
>   Same as, `[K || {K,_} <- maps:to_list(M)]`.
> 
> ##### `maps:find(K :: term(), M :: map()) -> {ok, V :: term()} | error.`
> 
>   Syntax equivalence: `try #{ K := V } = M, V catch error:{badmatch,_} -> error end`.
> 
>   Returns a tuple `{ok, V}` with value `V` associated with key `K` if map `M`
>   contains key `K`.  If no value is associated with key `K` then the function
>   will return `error`.
> 
>   Same as, `case lists:keysearch(K, 1, maps:to_list(M)) of {value,{_,V}} -> {ok,V}; false -> error end`.
> 
> ##### `maps:foldl(F :: fun((K :: term(), V :: term(), In :: term()) -> Out :: term()), A :: term(), M :: map()) -> Result :: term().`
> 
>   Syntax equivalence: *none*
> 
>   Calls `F(K, V, In)` for every key `K` to value `V` association in map `M` in
>   ascending key order. The function fun `F/3` must return a new accumulator
>   which is passed to the next successive call. `maps:foldl/3` returns the final
>   value of the accumulator. The initial accumulator value `A` is returned if
>   the map is empty.
> 
>   Same as, `lists:foldl(fun({K,V}, In) -> F(K,V,In) end, A, maps:to_list(M))`.
> 
> ##### `maps:foldr(F :: fun((K :: term(), V :: term(), In :: term()) -> Out :: term()), A :: term(), M :: map()) -> Result :: term().`
> 
>   Syntax equivalence: *none*
> 
>   Calls `F(K, V, In)` for every key `K` to value `V` association in map `M` in
>   descending key order. The function fun `F/3` must return a new accumulator
>   which is passed to the next successive call. `maps:foldr/3` returns the final
>   value of the accumulator. The initial accumulator value `A` is returned if
>   the map is empty.
> 
>   Same as, `lists:foldr(fun({K,V}, In) -> F(K,V,In) end, A, maps:to_list(M))`.
> 
> ##### `maps:from_list([{K1,V1}, .., {Kn,Vn}]) -> M :: map().`
> 
>   Syntax equivalence: `#{ K1 => V1, .., Kn => Vn }`
> 
>   The function takes a list of key-value tuples elements and builds a
>   map. The associations may be in any order and both keys and values in the
>   association may be of any term. If the same key appears more than once,
>   the latter (rightmost) value is used and the previous values are ignored.
> 
> ##### `maps:is_key(K :: term(), M :: map()) -> bool().`
> 
>   Syntax equivalence: `try #{ K := _ } = M, true catch error:{badmatch, _} -> false end`.
> 
>   Returns `true` if map `M` contains key `K`, otherwise it returns `false`.
> 
>   Same as, `lists:keymember(K, 1, maps:to_list(M))`.
> 
> ##### `maps:map(F :: function(), M0 :: map()) -> M1 :: map().`
> 
>   Syntax equivalence: `#{ K => F(K,V) || K := V <- M }`.
>   *Only with comprehensions*
> 
>   The function produces a new map `M1` by calling the function fun `F(K, V)` for
>   every key `K` to value `V` association in map `M0` in arbitrary order.
>   The function fun `F/2` must return the value to be associated with key `K` for
>   the new map `M1`.
> 
>   Same as, `maps:from_list(lists:map(fun({K,V}) -> {K, F(K,V)} end, maps:to_list(M)))`.
> 
> ##### `maps:new() -> M :: map().`
> 
>   Syntax equivalence: `#{}`.
> 
>   Returns a new empty map.
> 
>   Same as, `maps:from_list([])`.
> 
> ##### `maps:size(M :: map()) -> Size :: non_neg_integer().`
> 
>   Syntax equivalence: *none*.
> 
>   The function returns the number of key-value associations in the map.
> 
>   Same as, `erlang:map_size(M)` and `length(maps:to_list(M))`.
> 
> ##### `maps:put(K :: term(), V :: term(), M0 :: map()) -> M1 :: map().`
> 
>   Syntax equivalence: `M0#{ K => V }`.
> 
>   Associates key `K` with value `V` and inserts the association into map `M0`.
>   If a key exists that *equals* `K`, the old associated value is
>   replaced by value `V`. If key `K` does not *match* but *equals* the
>   old key is also replaced by key `K`.
>   The function returns a new map `M1` containing the new association.
> 
>   Same as, `maps:from_list(maps:to_list(M0) ++ [{K,V}])`.
> 
> ##### `maps:to_list(M :: map()) -> [{K1,V1}, ..., {Kn,Vn}].`
> 
>   Syntax equivalence: `[{K, V} || K := V <- M]`.
> 
>   Where the pairs, `[{K1,V1}, ..., {Kn,Vn}]`, are returned in a sorted order.
>   The Map ordering is described later in this document.
> 
> ##### `maps:update(K :: term(), V :: term, M0 :: map()) -> M1 :: map()`
> 
>   Syntax equivalence: `M0#{ K := V }`.
> 
>   If a key exists that *matches* `K`, the old associated value is
>   replaced by value `V`. The function returns a new map `M1` containing
>   the new associated value.
> 
>   Same as, `maps:from_list(maps:to_list(M0) ++ [{K,V}])`.
> 
> ##### `maps:values(M :: map()) -> [V1, .., Vn].`
> 
>   Syntax equivalence: `[V || _ := V <- M]`.
> 
>   Returns a complete list of values, in key sorted order, contained in map `M`.
> 
>   Same as, `[V || {_,V} <- maps:to_list(M)]`.
> 
> ##### `maps:without([K1, .., Kn] = Ks, M0 :: map()) -> M1 :: map().`
> 
>   Syntax equivalence: `#{ K => V || K := V <- M0, not lists:member(K, Ks) }`. 
>   *Only with comprehensions*
> 
>   Removes keys `K1` through `Kn`, and their associated values, from map `M0` and
>   returns a new map `M1`.
> 
>   Same as, `maps:from_list([{K,V}||{K,V} <- maps:to_list(M0), not lists:member(K, Ks)])`.
> 
> ##### `maps:merge(M0 :: map(), M1 :: map()) -> M2 :: map().`
> 
>   Syntax equivalence: *none*
> 
>   Merges two maps into a single map. If two *equal* keys exists in both maps the
>   value in map `M0` will be superseded by the value in map `M1`.
> 
>   Same as, `maps:from_list(lists:keymerge(1,maps:to_list(M0),maps:to_list(M1)))`.
> 
> 
> Equality and Ordering
> ---------------------
> 
> ### Equality ###
> 
> In the case of term `A` and term `B` both are maps,
> 
> * If `A` and `B` have different sizes, then `A` and `B` are not equal.
> * Otherwise, if all corresponding keys of `A` and `B` are pair-
>   wise equal with their corresponding values, then `A` and `B` are equal.
> * Otherwise, `A` and `B` are not equal.
> 
> It follows that two maps are equal if, and only if, they are of
> the same, *type*, *size* and all corresponding key-value associations are
> pairwise equal.
> 
> 
> ### Ordering ###
> 
> 
> The term order is defined in [Erlang specification 4.7][erlspec] and quoted
> below:
> 
> > * The terms are primarily ordered according to their type, in the following order: 
> >
> >         numbers < atoms < refs < ports < PIDs < tuples < empty list < conses < binary
> 
> The specification is incomplete here, the actual term order is:
> 
>     numbers < atoms < refs < funs < ports < pids < tuples < empty list < conses < binaries
> 	
> 
> The Maps data-type are ordered next after tuples:
> 
>     numbers < atoms < refs < funs < ports < pids < tuples < maps < empty list < conses < binaries
>                                                             ----
> 
> Maps are then ordered first by their size and then according to their
> respective keys and lastly by the associated values in Erlang term order. 
> 
> Given two maps, `M1` and `M2`, with the same size, they are compared
> so that each key, in Erlang term order of the keys, in `M1`
> is compared to the corresponding key of `M2`. All keys are
> compared first, then the values, until a difference is found. If a key
> or value differs, the order of the respective terms, in Erlang term
> order, is the order of the maps. If no key-value pairs differ, the
> maps are considered equal.
> 
> Example:
> 
>     > #{ b => 2 } > #{ a => 2 }.         % b > a
>     true
>     > #{ b => 2 } > #{ a => 1, b => 2 }. % size 1 < size 2
>     false
>     > #{ b => 1 } > #{ b => 2}.          % 1 < 2
>     false
>     > #{ b => 2, c => 3 } > #{ b => 1, d => 3}.  % c > d, compared before 2 and 1
>     false
>     > #{ b => 1 } > #{ 1 => 1}.          % b > 1
>     true
>     > #{ 1.0 => a } == #{ 1 => a }.      % 1.0 == 1
>     true
>     > #{ 1.0 => a } =:= #{ 1 => a }.     % 1.0 =:= 1
>     false
> 
> 
> Maps are printed with keys in Erlang term order.
> 
> Example:
> 
>     > #{ c => 3, b => 2, a => 1 }.
>     #{ a => 1, b => 2, c => 3 }
> 
> 
> Operator Precedence
> -------------------
> 
> Map association operator and set-value operator is ordered last,
> after match-operator and `catch`.
> 
>     :
>     #
>     Unary + - bnot not
>     / * div rem band and          Left associative
>     + - bor bxor bsl bsr or xor	  Left associative
>     ++ --                         Right associative
>     == /= =< < >= > =:= =/=
>     andalso
>     orelse
>     = !	                          Right associative
>     catch	 
>     => :=
> 
> It follows that the map expression:
> 
>     #{ key => C = 1 + 2 }
> 
> will evaluate in the following order:
> 
>     #{ key => ( C = ( 1 + 2 ) ) }
> 
> 
> Pattern matching
> ----------------
> 
> Pattern matching is very powerful Erlang tool. Maps introduces a couple of new
> features with its pattern matching. 
> 
> ### Pattern matching: Basics ###
> 
> We will exemplify using the match operator.
> 
> Pattern matching with maps is similar to records on the surface. Keys requested
> in a LHS pattern will be bound with the values which is found in the
> RHS association map.
> 
>     1> #{ a := V } = #{ a => 1 }.
>     #{ a => 1 }
>     2> 1 = V.
>     1
> 
> Keys requested in a LHS pattern which is not found in the RHS map will produce
> an exception, `exception error: no match of right hand side value ...`.
> 
>     1> #{ not_in_map := V } = #{ a => 1 }.
>     ** exception error: no match of right hand side value #{ a => 1 }
> 
> Similarly, if a value for a requested key in the LHS pattern
> is not equal to the keys associated value in the RHS map
> the match will produce an exception.
> 
>     1> #{ a := 10 } = #{ a => 1 }.
>     ** exception error: no match of right hand side value #{ a => 1 }
> 
> Only the keys requested will bind to associations. Any unrequested keys which
> resides within the map being matched will be ignored.
> 
>     1> #{ a := V1, b := V2 } = #{ a => 1, b => 2, c => 3}.
>     #{ a => 1, b => 2, c => 3 }
>     2> 1 = V1.
>     1
>     3> 2 = V2.
>     2
> 
> 
> The order of keys requested has no significance when pattern matching a map.
> 
>     1> #{ a := "1", b := "2" } = #{ a => "1", b => "2" }.
>     #{ a => "1", b => "2" }
>     2> #{ b := "2", a := "1" } = #{ a => "1", b => "2" }.
>     #{ a => "1", b => "2" }
> 
> ### Pattern matching: Continued ###
> 
> The example below is a constructed example to illustrate the power of map
> pattern matching.
> 
> A match expression is evaluated so that variables used as keys in the expression
> are bound before they are evaluated (if possible).
> 
> As an example, keys can be bound by other key-value associations.
> 
>     1> #{ K := V, id := K } = M = #{ id => b, a => 1, b => 2, c => 3}.
>     #{ id => b, a => 1, b => 2, c => 3}
>     2> b = K.
>     b
>     3> 2 = V.
>     2
> 
> In this case, the bound key `id` is evaluated first and looked up in
> M, binding the variable `K`. The `K` bound to `b` can then be used to
> bind `V` to 2.
> 
> Binding variables used as keys requires that there is a possible order of
> binding without cycles. The reordering extends to all terms in a matching
> expression, so that:
> 
>     1> { #{ X := Y }, X } = { #{ 5 => 10 }, 5 }.
> 
> with `X` and `Y` unbound, results in a successful match binding `X` to 5 and
> `Y` to 10.
> 
> This is particular useful when updating specifics in map associations:
> 
>     %% Function declared in module map_example
>     update_values([{K, V1}|Ls], #{ K := V0 } = M) -> update_values(Ls, M#{ K := V0 + V1 });
>     update_values([_|Ls], M) -> update_values(Ls, M);
>     update_values([], M)     -> M.
> 
> The first function clause is important here. Key `K` is bound in the tuple and
> will be used to request value `V0` from map `M`. The map `M` is then updated to
> associate key `K` with the new value `V0 + V1`.
> 
>     %% In the Erlang shell
>     1> M = #{ "a" => 1, "b" => 2, "c" => 3 }.
>     #{ "a" => 1, "b" => 2, "c" => 3 }
> 
>     2> map_example:update_values([{"b", 10}, {"c", 20}, {"d", 30 }], M).
>     #{ "a" => 1, "b" => 12, "c" => 23 }
> 
> Note that since key `"d"` does not reside in map `M` it fails to match the first
> clause and does not update the map with the association `"d" => 40`.
> 
> An expression where the dependencies in the LHS of the match are cyclic, like:
> 
>     1>  #{X := Y, Y := X} = #{5 => 10, 10 => 5}.
> 
> will result in an evaluator error (variable is unbound) or a compilation error.
> 
> 
> External Term Format
> --------------------
> 
> There are 255 tags that can be used to encode terms for external binary
> distribution.  All tags are defined in `external.h`. The encoding starts by a
> magic byte `131`.
> 
> The encoding tags used in R15B01 are the following:
> 
>     SMALL_INTEGER_EXT        'a'     97
>     INTEGER_EXT              'b'     98
>     FLOAT_EXT                'c'     99 
>     ATOM_EXT                 'd'    100
>     SMALL_ATOM_EXT           's'    115
>     REFERENCE_EXT            'e'    101
>     NEW_REFERENCE_EXT        'r'    114
>     PORT_EXT                 'f'    102
>     NEW_FLOAT_EXT            'F'     70
>     PID_EXT                  'g'    103
>     SMALL_TUPLE_EXT          'h'    104
>     LARGE_TUPLE_EXT          'i'    105
>     NIL_EXT                  'j'    106 
>     STRING_EXT               'k'    107
>     LIST_EXT                 'l'    108 
>     BINARY_EXT               'm'    109 
>     BIT_BINARY_EXT           'M'     77                                         
>     SMALL_BIG_EXT            'n'    110
>     LARGE_BIG_EXT            'o'    111
>     NEW_FUN_EXT              'p'    112 
>     EXPORT_EXT               'q'    113
>     FUN_EXT                  'u'    117
>                 
>     DIST_HEADER              'D'     68
>     ATOM_CACHE_REF           'R'     82
>     ATOM_INTERNAL_REF2       'I'     73
>     ATOM_INTERNAL_REF3       'K'     75
>     BINARY_INTERNAL_REF      'J'     74
>     BIT_BINARY_INTERNAL_REF  'L'     76
>     COMPRESSED               'P'     80
> 
> For Maps we define tag `MAP_EXT` to 116 (`t`).
> 
> 
> Data layout:
> 
>     MAP_EXT
>     |-----------------------------------	
>     |  1  |    4   |        |          |
>     |-----------------------------------
>     | 116 |  Size  |  Keys  |  Values  |
>     |-----------------------------------
> 
> The `Size` specifies the number of keys and values that follows the size
> descriptor.
> 
> An open questions, optimize for:
> 
>   1. encoding/decoding speed?
>   2. ease of access?
>   3. memory size?
> 
> Memory size should be a priority since we send this data over the wire. We
> should promote ease of access so other languages can integrate towards the
> format.
> 
> This leads to a flat and simple structure. It follows that encoding/decoding
> takes a performance hit.
> 
> 
> Motivation
> ==========
> 
> Why would we need maps when we have *records*, *dicts*, *gb_trees*, *ets*
> and *proplists*?
> 
> Maps are envisioned to be an easy to use, lightweight yet powerful key-value
> association store.
> 
> Maps utilizes one of Erlang's major strengths, pattern matching, to enrich user
> experience and provide a powerful tool to simplify code development. Pattern
> matching gives Maps a clear edge over dicts, gb_trees or proplists in usability.
> 
> Maps provides the possibility to associate arbitrary terms as keys, not only
> atoms, with arbitrary terms as values in a matching capable data-type.
> 
> Maps does not claim to be an replacement to records as the frames proposal does.
> Instead maps targets a larger usage domain and wishes to be a complement to
> records and supersede them where suitable.
> 
> 
> 
> ### Maps - Two approaches ###
> 
>  1. Maps as an association array with pattern matching and syntax for
>     constructing, accessing or updating them.
>  2. Maps as a record replacement.
> 
> Maps were not envisioned as a record replacement at first, it was a hopeful
> requirement added later. A record replacement approach does not necessarily
> restrain any semantics but it may put some constraint on the implementation
> and underlying structure.
> 
> ##### Records #####
> 
> Records are powerful under the right circumstances:
> 
>  * fast lookups, O(1), due to compile time indexing of keys, and fast stores for
>    small record sizes (~50 values),
>  * no memory overhead to store keys, only values and a name: 2 + N words
>    consumption,
>  * ease of use in function head matching.
> 
> However some of the drawbacks are:
> 
>  * compile-time dependency and forces header file inclusions for inter-module usage,
>  * only atoms as keys,
>  * keys are not accessible in runtime,
>  * no dynamic access of values, i.e. we cannot use variables to access values,
>  * it is not a data-type and cannot be distinguished from tuples.
> 
> When comparing maps with records the drawbacks are easily remedied by Maps,
> however the positive effects is not as easy to replicate in a built-in data-type
> where values are determined at runtime instead of at compile time.
> 
>  * Being faster than direct-indexing array, where indices and possibly the
>    resulting value are determined at compile time, is hard.
>    In fact it is impossible.
>  * A memory model for Maps where the efficiency was near that of records
>    could be achieved by essentially using two tuples, one for keys and one for
>    values as demonstrated in Frames. This would be impact performance of
>    updates on Maps with a large number of entries and thus constrain the
>    capability of a dictionary approach.
>  * Maps would be as easy, or even easier, to use with matching in function heads.
> 
> 
> ### Protocol Construction ###
> 
> Arguments for a simpler a JSON representation using frames or 
> maps has been raised. Using frames and thereby atoms for dynamic creation of keys
> would be a serious drawback.  Using maps would grant the possibility of string
> binaries to represent keys and would not put the global atom pool in disarray.
> 
> 
> #### Pattern Matching Example: The JSON Files ####
> 
> Changing json-decoding. Mochiwebs mochijson decodes Json dictionaries the as
> the following:
> 
>     {"key": "value"} -> {struct, [{"key", "value"}]}
> 
> This could instead be:
> 
>     {"key": "value"} -> #{ "key" => "value"}
> 
> Consider the following JSON examples, from [json.org][json].
> 
> 
>     {"menu": {
>       "id": "file",
>       "value": "File",
>       "popup": {
>         "menuitem": [
>           {"value": "New", "onclick": "CreateNewDoc()"},
>           {"value": "Open", "onclick": "OpenDoc()"},
>           {"value": "Close", "onclick": "CloseDoc()"}
>         ]
>       }
>     }}
> 
> `mochijson:decode/1` will currently look like:
> 
>     {struct, [
>         {"menu", {struct, [
>             {"id","file"},
>             {"value","File"},
>             {"popup", {struct, [
>                 {"menuitem", {array, [
>                     {struct, [{"value","New"},{"onclick","CreateNewDoc()"}]},
>                     {struct, [{"value","Open"},{"onclick","OpenDoc()"}]},
>                     {struct, [{"value","Close"}, {"onclick","CloseDoc()"}]}
>                 ]}}
>             ]}}
>         ]}}
>     ]}
> 
> `mochijson:decode/1` could look like:
> 
>     #{ "menu" => #{
>         "id" => "file",
>         "value" => "File",
>         "popup" => #{
>             "menuitem" => [
>               #{ "value" => "New",   "onclick" => "CreateNewDoc()"},
>               #{ "value" => "Open",  "onclick" => "OpenDoc()"},
>               #{ "value" => "Close", "onclick" => "CloseDoc()"}
>             ]
>         }
>     }}
> 
> 
> Let us find `"menu"` -> `"popup"` -> `"menuitem"`.
> 
> Traversing the first structure is a bit awkward. We would have to do
> the following:
> 
>     Decoded         = mochijson:decode(Json),
>     {struct, Menu}  = proplists:get_value("menu", Decoded),
>     {struct, PopUp} = proplists:get_value("popup", Menu),
>     {struct, Items} = proplists:get_value("menuitem", PopUp),
> 
> With maps it could look like the following:
> 
>     #{ "menu"     := Menu  } = mochijson:decode(Json),
>     #{ "popup"    := PopUp } = Menu,
>     #{ "menuitem" := Items } = PopUp,
> 
> or even:
> 
>     Decoded = mochijson:decode(Json),
>     #{ "menu" := #{ "popup" := #{ "menuitem" := Items } } } = Decoded,
>  
> With maps, and single value access, it could look really simple:
> 
>     Decoded = mochijson:decode(Json),
>     Items = Decoded#{ "menu" }#{ "popup" }#{ "menuitem "}.
> 
> 
> ### Open Questions ###
> 
> We have some usage scenarios that are still open for debate. A proposed answer
> is given for each question and stems from discussions in this proposal.
> 
>  1. What type of keys will we need to store in our Map? Will atoms suffice? 
>    *  It is the authors view that we should refrain from any key restrictions
>       unless there is overwhelmingly evidence that we can gain something from
>       such a restriction.
>    *  A non atom key restriction satisfies our goal of a powerful Map mechanism.
>    *  Proposal: *Any term as keys.*
>  2. How many key-value associations will we store in our map?
>    *  This question has less to do with syntax and semantics than it has with
>       the choice of the underlying implementation.
>    *  If we enable the user to add key-value pairs dynamically surely he will
>       use it.  Since it is a powerful mechanism not afforded to us by records
>       the usage pattern will also be different. This will in all likelihood
>       produce larger Maps than records are today. This implies that we cannot
>       compare records sizes with that of maps sizes since the usage scenario
>       would be different.
>    *  Proposal: *Arbitrary number of keys-value pairs.*
>  3. How many Map instances will we create for each Map with a specific set of keys?
>    *  This question is closely related to how we use records and if Maps should
>       emulate this behavior and this should have no impact on semantics, only
>       implementation.
>    *  The significant difference is the memory overhead in the storing structure.
>       Since memory overhead for keys and values has the same behavior as in any
>       compounded term or abstract data-type, i.e. dict or gb_trees, the main
>       difference occurs when comparing maps to records and frames. To ensure a
>       logarithmic worst-case performance in update or retrieval some sort tree
>       structure would likely be used for maps. Maps would then stores keys
>       together with its values whereas frames stores keys outside its value
>       structure and records generates key indexes at compile-time. This would
>       indicate a memory overhead for Maps over Frames and records for each
>       instance.
>    *  Proposal: *Two tier approach, similar to binaries. Use flat compact,
>       key-sharing approach for few associations (~50 associations). Use sorted
>       tree approach and store keys with values beyond first tier limit.
>       The rationale being it is more likely to have multiple instance where
>       we have few keys.*
>  4. Only allow updates of already defined keys within a Map in syntax?
>    *  The question stems from a record replacement approach and the argument for
>       it is to mitigate typos, i.e. trying to update key `behavior` where key
>       `behaviour` was actually intended. Instead of getting two different keys,
>       a runtime exception occurs at this point.
>    *  This approach will *deny* any dictionary like behavior, for instance
>       storing spawned processes as keys in the map using syntax.
>    *  Proposal: *Allow for any key to be stored by default syntax,
>       existing or not, and use a special syntax for setting of values of
>       existing keys only.*
>      
> The answers from these questions are instrumental to how we should design and
> implement Maps. What we also should keep in the back of our minds is that we
> will never get rid of records completely and some of the frames arguments might
> thus be superfluous.
> 
> Rationale
> =========
> 
> 
> What should we expect from our syntax?
> --------------------------------------
> 
> As stated earlier, the current syntax is not set in stone but what should we
> expect from it?
> 
> 1. First and foremost it has to be unambiguous, meaning the syntax must produce
>    single clearly defined behavior that cannot be misinterpreted by humans
>    nor machines.
>    
>    1.1  Here we also include the notion that similar syntax should have similar
>         behavior, or at least not completely different behavior.
> 	For example records, `#record{ key = Value }`, have O(1) performance and
> 	2 + N words memory overhead.  If we use a similar syntax,
> 	i.e. `#{ key = Value }`, we should also expect similar behavior both in
> 	regard to semantics and performance for any and all sizes of the map.
> 
> 2. The syntax must be as short as possible. It must not use more characters than
>    necessary to describe a certain behavior as long as it
>    does not violate rule 1.
> 
>    2.2  We want to avoid verbosity in the language. Verbosity pushes away
>    information from our field of vision and obfuscates it.
>    This needs to be avoided.
> 
> 
> Syntax choice for Maps
> ----------------------
> 
> *The author argues for:* `=>` *as delimiter in 'set-or-update' and*
> `:=` *in 'set-existing' and 'matching' syntax.*
> 
> In the examples below we use `#{ Key => Value }` to describe map semantics and
> use-cases, but this is only one suggestion out of many.
> 
> Several syntax proposals exists, frames proposes `<{ key ~ Value }>` syntax and
> another syntax suggestion is very similar to record syntax `#{ key = Value }`.
> 
> The current variable and atom definitions puts restrictions on what we can use
> as delimiters and leaves us `~` and `=` as the only sane *single* character
> delimiters we can use. The case is very well argued in Richard O'Keefes
> [No more need for records (fifth draft)][ROKframe].
> 
> ### Delimiter discussion ###
> 
> Arguments against a `=` delimiter are:
> 
>    * It lacks distinction from match, consider `#{ A = B = v }`,
>      does `A` match `B` or does `B` match `v`?
>      Which `=` is a match operation and which `=` delimits the key-value pair?
>    * It might be interpreted as `Key` 'equal' `Value`,
> 
> and hence `=` is in violation of rule #1 from *What do we expect from our syntax?*.
> The interpretation of this syntax is ambiguous.
> 
> Arguments against a `~` delimiter are:
> 
>    * it might be interpreted as `Key` 'NOT' `Value`
>      as `~` is the bitwise NOT operator in C,
>    * it might be interpreted as `Key` 'about equal' `Value`
>      as `~` is similar to mathematics `???`,
>    * it lacks typographical distinction,
>      i.e. it lacks distinction from `-` in certain fonts, 
>      ex. `K ~ V` might be interpreted as `K - V`, consider `#{ K - 1 ~ 2 - V }`,
> 
> and hence this is in violation of rule #1 from *What do we expect from our syntax?*.
> The interpretation of this syntax is ambiguous.
> 
> Two two-character delimiter suggestions are `#{ Key := Value }` and
> `#{ Key => Value}`, where `:=` is a common denominator for assignment and `=>`
> should be read as *maps to*. A two-character delimiter should be avoided if at
> all possible since it increases the syntax footprint of the source code.
> 
> The assignment delimiter reads well for just assignment but suffers from the
> same reversed logic flaw as records when it comes to pattern matching. The match
> `#{ key := Value } = M` reads *match M to the map pattern where Value is equal
> to key*. That does not read well unless we call the assignment delimiter `:=`
> for something that its not meant to be.
> 
> However, `:=` is also similar to `=:=` which means "is exactly equal",
> i.e. matches. This is a valuable meaning since we have a difference
> between `==` and `=:=` when dealing with numbers and thus `:=` could be a more
> correct delimiter for matching syntax.
> 
> The delimiter `->` would be suitable choice if it weren't for the fact that it
> would overload the function clause meaning.
> 
> Both `->` and `=>` might be confusing when dealing with binaries.
> Consider `#{ <<"key">> -> <<"value">> }` and `#{ <<"key">> => <<"value">> }`,
> where `=>` appears to be slightly more confusing than `->`.
> 
> Listing of delimiters from above perceived desirability: 
> 
>   1. `#{ K => V }` - No ambiguity, no overloading, reads as an association
>   2. `#{ K := V }` - No ambiguity, no overloading, reads as an assignment or exact match
>   3. `#{ K ~ V }`  - Typographical ambiguity, no overloading, no clear meaning
>   4. `#{ K -> V }` - Overloads function clause head and body separator, reads as an association
>   5. `#{ K = V }`  - Overloads match operator, reads as a match or an assignment
> 
> Using `:=` assignment for existing keys seems as a good choice. The choice for
> set-or-update is between `=>` and `~`.
> 
> 
> ### The case for two set-or-update semantics and its syntax ###
> 
> A case for two different ways to update values in a Map is proposed.
> 
> One syntax if, and only if, we want to update a value for an already *existing*
> key and another if we want to update the Map with any key.
> 
> *  Use `M#{ K => V }` to declare new key value pairs *or* update already existing keys
> *  Use `M#{ K := V }` to update already existing keys.
> *  Use ` #{ K := V } = M` to match maps.
> 
> Example 1:
> 
>     foo() ->
>         M = #{ key1 => 1, key2 => 2 }, % M is declared with keys 'key1' and 'key2'
>         bar(M).
> 
>     bar(M) ->
>         M#{
>             key1 := "1",  %% 'key1' will be set to "1"
>             key2 := "2",  %% 'key2' will be set to "2"
>             key3 := "3"   %% this causes an exception since 'key3' does not exist in M
>         }.
> 
>     > foo().
>     ** exception error: no match of 'key3' in map
> 
> Example 2:
> 
>     foo() ->
>         M = #{ key1 => 1, key2 => 2 }, % M is declared with keys 'key1' and 'key2'
>         bar(M).
> 
>     bar(M) ->
>         M#{
>             key1 => "1",  %% 'key1' will be set to "1"
>             key2 => "2",  %% 'key2' will be set to "2"
>             key3 => "3"   %% 'key3' will be set to "3"
>         }.
> 
>     > foo().
>     #{ key1 => 1, key2 => "2", key3 => "3" }
> 
> 
> Impact of syntax footprint
> --------------------------
> 
> We must lessen the syntax footprint impact on the source code and the language.
> 
> Currently the two normal ways of sending options to a functions are either via
> records or property lists. Both have some drawbacks. Records are compile time
> dependent and syntactic sugar for tuples. Property lists are generic but
> produces a lot of texts when defining them and operating on them.
> 
> Consider this example when parsing a list of arguments:
> 
>     args(Args) -> 
>          args(Args, [{analyze, false}, {suppression, false}, {target, none}]).
> 
>     args(["-r" | Args], Opts) -> 
>         args(Args, [{analyze, true}     | proplists:delete(analyze, Opts)]);
>     args(["-s="++File | Args], Opts) -> 
>         args(Args, [{suppression, File} | proplists:delete(suppression, Opts)]);
>     args([Target], Opts) -> 
>         [{target, Target} | proplists:delete(target, Opts)].
>         
> 
> The textual impact, the number of characters, is quite heavy when operating on 
> property lists.
> 
> If we instead use some kind of map with syntax, how would that look?
> 
>     args(Args) -> 
>         args(Args, #{ analyze => false, suppression => false, target => none}).
> 
>     args(["-r" | Args], Opts)        -> args(Args, Opts#{ analyze := true });
>     args(["-s="++File | Args], Opts) -> args(Args, Opts#{ suppression := File});
>     args([Target], Opts)             -> Opts#{ target := Target }.
> 
> This looks cleaner in my opinion but that is a very subjective view. To use some
> data we can count the characters, and we see that the property lists example has
> 390 characters versus the map examples 306. Property lists uses almost 30% more
> characters in this example.
> 
> Semantics and API-functions
> ---------------------------
> 
> 
> ### List conversions ###
> 
> Perhaps the most sane `maps:from_list/1` semantics would be to have the key-value
> significance order in left to right, meaning the first association is used and
> the latter values with equal keys are ignored.
> 
> This differs from the `dict:from_list/1` behavior.
> 
> Consider the following `dict` example:
> 
>     [{a,2}] = dict:to_list(dict:from_list([{a,1}, {a,2}])).
> 
> By letting the leftmost be the most significant key we could simplify conversion
> from and to lists. 
> 
> Current suggestion has the following semantics:
> 
>     Ls = [{a,old}],
>     #{ a := old } = maps:from_list([{a,new}|Ls]).
> 
> The reversal would be:
> 
>     Ls = [{a,old}],
>     #{ a := new } = maps:from_list([{a,new}|Ls]).
> 
> 
> Equality and Ordering
> ---------------------
> 
> A restriction set on the implementation by the Erlang specification is that
> order is total, i.e. satisfies *antisymmetry*, *transitivity* and *totality*.
> 
>  - If `M1 =< M2` and `M2 =< M1` then `M1 == M2`,
>  - If `M1 =< M2` and `M2 =< M3` then `M1 =< M3`,
>  - If `M1 =< M2` or `M2 =< M1` (always comparable)
>    where `M1`, `M2` and `M3` are any Map term.
> 
> This only holds true in Erlang if we treat floats and integers as union of types,
> namely numbers. In the case of a Maps, `true = #{ 1.0 => V } == #{ 1 => V}`.
> 
> 
>  - The need for order arises in a few cases.
>    - comparison, for example sorting, `lists:sort([M1, .., Mn])`
>    - introspection, for example when printed.
>  - Ordered maps impose restrictions on the underlying implementation and a
>    hashing approach will be nearly impossible.
>  - The underlying structure does not need to be sorted, an order could be
>    produced when needed,
>    - `M1` < `M2`, would result in an internal sort but would cost
>      O( *N1* * lg *N1* + *N2* * lg *N2* ), where
>      `N1 = maps:size(M1) and N2 = maps:size(M2)`
>   
> 
> The discussion and results on equality versus matching for keys stems from ets
> and ordered set.
> 
> Consider the following with ets.
> 
>     1> ets:new(foo, [named_table, ordered_set]).
>     foo
>     2> ets:insert(foo, {1,v1}).
>     true
>     3> ets:insert(foo, {1.0,v2}).
>     true
>     4> ets:lookup(foo,1).
>     [{1.0,v2}]
>     5> ets:match(foo, ets:fun2ms(fun({1,V}) -> V end)).
>     []
> 
> 
> 
> Accessing a single value
> ------------------------
> 
> Do we need to have single access or is matching sufficient?
> 
> Consider the following,
> 
>     V = M#{ K }
> 
> is shorter than
> 
>     #{ K := V } = M
> 
> It also allows for easy access of associated values in deep structures.
> 
> The syntax for single value access is the least developed (and contemplated)
> feature in this proposal and certainly could use some input.
> 
> More over, the dot syntax must be abolished. Currently it is used for records
> but it will not be used for maps. Dot represents end of expression list in last
> clause, or end of attribute.
> 
> It cannot be used to distinguish between floats or associations.
> 
> Example:
> 
>     1> M = #{ 1.1 => a, 1 => #{ 1 => b } }.
>     #{ 1 => #{ 1 => b }, 1.1 => a }.
> 
>     2> #M.1.1.
>     a | b ?
> 
> 
> 
> Backwards Compatibility
> =======================
> 
> Erlang code written with Maps will only be parseable, loadable and executable 
> on Erlang/OTP R17A and later releases of Erlang/OTP but not on previous
> releases.
> 
> Erlang code written before Erlang/OTP R17A will be perfectly compatible, i.e.
> parseable, loadable and executable with these Maps changes.
> 
> Distribution will not be backwards compatible.
> 
> 
> 
> [perl-hashes]: http://perldoc.perl.org/perldata.html
>     "perldata - perldoc.perl.org"
> [ruby-hashes]: http://ruby-doc.org/core-1.9.3/Hash.html
>     "Class: Hash (Ruby 1.9.3)"
> [python-dict]: http://docs.python.org/tutorial/datastructures.html#dictionaries
>     "5. Data Structures - Python v2.7.3 documentation"
> [scala-maps]: http://docs.scala-lang.org/overviews/collections/maps.html
>     "Collections - Maps - Scala Documentation"
> [dict-module]: http://www.Erlang.org/doc/man/dict.html
>     "Erlang -- dict"
> [ROKframe]: http://www.cs.otago.ac.nz/staffpriv/ok/frames.pdf
>     "No more need for records"
> [erlspec]: http://www.Erlang.org/download/erl_spec47.ps.gz
>     "Erlang specification 4.7"
> [json]: http://json.org/example.html
>     "JSON Example"
> 
> 
> Copyright
> =========
> 
> This document has been placed in the public domain.

> _______________________________________________
> eeps mailing list
> 
> http://erlang.org/mailman/listinfo/eeps


-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB


More information about the eeps mailing list