EEP 58: Map comprehensions #

Abstract #

This EEP proposes syntax and semantics for map comprehensions and generators, similar to list and binary comprehensions and generators, but operating on maps and map iterators.

Copyright #

This document is placed in the public domain or under the CC0-1.0-Universal license, whichever is more permissive.

Specification #

Maps and the initial map comprehension syntax and semantics were proposed in EEP-43. List and binary comprehensions were specified post-fact in EEP-12. This EEP is based on those two EEPs.

The syntax construct commonly referred as a “comprehension” is, in fact, composed of 3 semi-independent parts:

• the “generator” - is the expression that iterates over the container, matches each element of the container over a pattern and binds the variables which can be used in the “comprehensions” and the “filters”.
• the “comprehension” - is the expression that is executed for each element produced by the generator that successfully matched the pattern and passed the “filter” check. The value produced by this expression is appended to the resulting generated container.
• the “filter” - is the expression that is evaluated for each element produced by the generator that matched the pattern and returns a boolean result: when it returns false, the current element is skipped from being passed to the “comprehension”; when it results in true, the element is passed to the “comprehension”.

So, in this document we are going to keep this separation, but sometimes will refer to the whole combination of the comprehension, the filter and the generator as a “comprehension”, because the generator syntax is not used outside of the comprehension context.

Syntax #

The proposed syntax for the map comprehension part is

'#{' KeyExpr '=>' ValueExpr '||' GeneratorsFilters '}'

Where GeneratorsFilters are one or more list/map/binary generators and/or filters, separated by a comma.

The proposed syntax for the map generator part is

KeyPattern ':=' ValuePattern '<-' MapOrIteratorExpr

Example combination of map comprehension and map generator

#{Key => Value || Key := Value <- MapOrIterator}

Map comprehension may be combined with list or binary generator and vice-versa

[{Key, Value} || Key := Value <- MapOrIterator]
#{K => K || K <- List}
#{K => V || <<K, V>> <= Binary}

MapOrIterator is any Erlang expression that evaluates to map() or maps:iterator() datatype.

Semantics #

Map comprehension should be semantically equivalent to the maps:from_list/1 call over a list comprehension producing a list of 2-tuples:

#{K => V || ...}

is equivalent to

maps:from_list([{K, V} || ...])

Map generator should be semantically equivalent to the list generator running over the result of maps:to_list/1, when the input is a map datatype:

#{ ... || K := V <- Map}

is equivalent to

#{ ... || {K, V} <- maps:to_list(Map)}

And for maps:iterator() as input - it can’t be easily expressed as equivalent list generator. But the idea is that it’s equivalent to the consumption of the iterator by repetitive calls to maps:next/1 and matching Key and Value over key and value patterns accordingly on each iteration loop.

Map generator should raise error({bad_generator, ExprResult}) if the MapOrIterator expression evaluation produced anything but map or map iterator.

Key pattern is allowed to be anonymous variable _ / contain unbound variables (which is not allowed in other map pattern-matching contexts).

Variable binding and shadowing rules should be the same as for list and binary comprehensions (which follows from the equivalence rules described above).

Rationale #

Syntax for arrow, generator pattern and comprehension key-value pair #

We decided to go with the syntax proposed in EEP-43.

#{ .. } were chosen for the outer tokens of map comprehension because the same are used when constructing a new map - rule similar to list and binary comprehensions.

K := V <- is not ambiguous for the parser, so unlike binary generator, there is no need for a new arrow. <- was chosen over <= because the latter is less visually distinguishable when it is placed relatively close to the => and := tokens:

#{K => V || K := V <= Map}.
% vs
#{K => V || K := V <- Map}.

KeyPattern := ValuePattern is the same syntax that is used in map pattern-matching. However, in map generators KeyPattern is also allowed to be an anonymous or unbound variable.

KeyExpr => ValueExpr is the same syntax that is used for the new map construction.

Order in which map generator yields key-value pairs #

Since maps do not have any order specified, the order in which the generator would yield key-value pairs should not be guaranteed (same way as the ordering of the list, resulting from maps:to_list/1 is not guaranteed).

Behavior when comprehension produced duplicate keys #

Same as maps:from_list/1: the latest (last generated) value is used and the previous values are ignored. It might be less predictable when a map comprehension is used in combination with a map generator, because the map generator order is not defined. Eg

#{ V => K || K := V <- #{a => x, b => x} }

could produce both #{x => a} and #{x => b}.

But it becomes important when a map comprehension is used with a list or a binary generator. Eg

#{ V => K || {K, V} <- [{a, x}, {b, x}] }

would always produce #{x => b}.

Whether to allow map iterator as input for map generator #

Map iterators are allowed in maps:filter/2, maps:fold/3 and maps:map/2. Since comprehensions are often used in the same contexts as those functions, it makes sense to allow map iterators so comprehensions could be used as a drop-in replacement for the aforementioned functions.

Map updates via map comprehension #

Should map updates be allowed with map-comprehensions? That is should this be valid syntax:

MapToUpdate#{ K => V*2 || K := V <- MapToUpdateWith}

or this

MapToUpdate#{ K := V*2 || K := V <- MapToUpdateWith}

There is no final decision about how useful might it be.

More-or-less the same result may be achieved using maps:merge/2 function (with less room for optimization).

One (probably minor) argument against it is the fact that the “map update” syntax is a common reason for very confusing errors programmers make when they forget to add a comma between two maps:

> [#{a => b}
   #{a => d}].
[#{a => d}]

Here the “map update” syntax has been accidentally created instead of the intended “list of two maps”.

There exists some risk that similar issue might happen with “update via comprehension”:

my_fun(Map) ->
    Options = #{a => b}
    #{ K => V || K := V <- smth(Map, Options) }.

However probability is lower, since mistake usually happens in literal definitions, but programmers rarely use comprehensions in literal definitions.

Motivation #

Having comprehensions and generators for lists and binaries, it seems logical that there should be a generator for maps as well. For example, Python language has versions of comprehensions for both lists and dicts (but also generators in comprehensions work for any iterable). Another factor is that it’s a quite common practice in the code seen in the wild to use combinations of maps:from_list/1, maps:to_list/1 with list comprehensions and list high-order functions in a situations when high-order functions from maps module are not flexible enough (eg, we want to convert map not to another map, but to some different structure, or to modify both key and value). But use of maps:from/to_list might be a problem for the performance since it is eager and creates garbage on heap.

Backwards Compatibility #

None of the existing Erlang code will be affected, since the syntax extensions we are proposing in this EEP are not valid syntax in Erlang right now. Erlang code written with map comprehensions would be non-parseable by the older Erlang compiler. Some of the tools working with intermediate Erlang forms (eg, AST) have to be updated (eg, parse-transforms). However, we expect core-erlang form to not be affected - similar to list and binary comprehensions.

Reference Implementation #

The reference implementation is provided in a form of pull-request on GitHub

https://github.com/erlang/otp/pull/4856