The lists:key* functions (keyfind/3, keytake/3, keyreplace/4,
and so on) make it convenient to work with lists of tuples keyed on a
tuple position.
This EEP proposes a small, orthogonal set of additions that gives the
same convenience for lists with other elements such as maps: four
first-match higher-order functions in the lists module (take/2,
remove/2, replace/3, and store/3). These additions compose with
the existing higher-order functions (lists:any/2, search/2,
sort/2, merge/3, …) so that every lists:key* operation has a
generic equivalent that works on elements any type.
To make these function convenient to use, we suggest adding the
predicates maps:has/3 and maps:is_ordered/3. Equivalent
predicates for native records, gb_trees, and other containers are
left to follow-up proposals (see Rationale).
Erlang code frequently stores collections as a list of elements each
carrying a key. When the elements are tuples, the lists:key* family
provides a suitable API:
lists:keyfind(mike, 2, People) %% find by tuple position 2
lists:keydelete(mike, 2, People) %% delete first by position 2
lists:keyreplace(mike, 2, People, New)
lists:keysort(2, People)
Maps are sometimes a better choice than tuples for structured data.
Lists of maps are common and for them the lists:key* family is
unusable. A developer with a list of maps must hand-write a fun
(closure) for every operation, for example:
lists:search(fun(M) -> maps:get(id, M, undefined) =:= 42 end, MapList)
This is verbose, easy to get subtly wrong, and has no counterpart for
operations such as keydelete, keytake, and keyreplace.
The same gap applies to native records (introduced in OTP 29, a
distinct data type with named-field access) and to other keyed
containers such as gb_trees. Those raise additional design questions
and are addressed by follow-up proposals; this EEP focuses on lists
and maps.
A survey of the Erlang/OTP sources (production code, test suites
excluded) shows how much the key* operations are used, and therefore
how much a generic equivalent is needed:
| Function | Calls | Generic equivalent | Exists before this EEP |
|---|---|---|---|
lists:keyfind/3 |
530 | lists:search/2 |
yes |
lists:keysearch/3 |
467 | lists:search/2 |
yes |
lists:keysort/2 |
170 | lists:sort/2 |
yes |
lists:keydelete/3 |
162 | lists:remove/2 |
no |
lists:keymember/3 |
143 | lists:any/2 |
yes |
lists:keyreplace/4 |
102 | lists:replace/3 |
no |
lists:keytake/3 |
28 | lists:take/2 |
no |
lists:keystore/4 |
21 | lists:store/3 |
no |
lists:ukeysort/2 |
13 | lists:usort/2 |
yes |
lists:ukeymerge/3 |
7 | lists:umerge/3 |
yes |
lists:keymerge/3 |
2 | lists:merge/3 |
yes |
lists:keymap/3 |
1 | lists:map/2 |
yes |
The additions fall into two groups:
(a) New high order functions lists:remove/2, replace/3, take/2,
and `store/3`, which have no generic form today. They are the
generic equivalents of `keydelete/3`, `keyreplace/4`, `keytake/3`,
and `keystore/4`.
(b) maps predicates that can be used in the list functions:
`maps:has/3` for list functions that do not sort; and
`maps:is_ordered/3` for the sort/merge family. Without these, the
find and sort cases work but every call site must use a dedicated fun.
lists functions #
Each high-order function takes a predicate fun((Elem) -> boolean())
and operates on the first element for which the predicate returns
true.
-spec lists:take(Pred, List) -> {Elem, NewList} | false when
Pred :: fun((Elem) -> boolean()),
List :: [Elem], NewList :: [Elem], Elem :: term().
-spec lists:remove(Pred, List) -> NewList when
Pred :: fun((Elem) -> boolean()),
List :: [Elem], NewList :: [Elem], Elem :: term().
-spec lists:replace(Pred, New, List) -> NewList when
Pred :: fun((Elem) -> boolean()),
New :: Elem, List :: [Elem], NewList :: [Elem], Elem :: term().
-spec lists:store(Pred, New, List) -> NewList when
Pred :: fun((Elem) -> boolean()),
New :: Elem, List :: [Elem], NewList :: [Elem], Elem :: term().
Descriptions:
take(Pred, List) returns {Elem, NewList}, where Elem is the first
element satisfying Pred and NewList is List with that element
removed, preserving order. Returns false if no element matches.
This is the predicate-based generalization of keytake/3. Unlike
keytake/3, the result is a plain 2-tuple without a {value, ...}
wrapper, mirroring maps:take/2.
remove(Pred, List) return NewList, which is List with the
first matching element removed, preserving order. Returns List
unchanged if no element matches. This is the generalization of
keydelete/3. The name remove is used because lists:delete/2
already exists with different behavior; remove also aligns
with maps:remove/2.
replace(Pred, New, List) returns NewList, which is List with
the first matching element replaced by New, preserving
order. Returns List unchanged if no element matches. This is
the generalization of keyreplace/4.
store(Pred, New, List) behaves like replace/3, except that if no
element matches, New is appended to the end of the list. This is
the generalization of keystore/4.
Pred must be a fun of arity 1; otherwise the call fails with a
function_clause error, consistent with the other predicate-taking
functions in lists (filter/2, search/2, …).
Two maps helpers are added: a boolean membership predicate and a
keyed ordering function.
-spec maps:has(Key, Value, Map) -> boolean() when
Key :: term(), Value :: term(), Map :: map().
-spec maps:is_ordered(Key, MapA, MapB) -> boolean() when
Key :: term(), MapA :: map(), MapB :: map().
Descriptions:
maps:has(Key, Value, Map) returns true if Map associates Key
with Value (exact =:= comparison), otherwise false. Fails with
{badmap, Map} if Map is not a map, consistent with the rest of
the maps module.
maps:is_ordered(Key, MapA, MapB) returns true if maps:get(Key,
MapA) =< maps:get(Key, MapB), otherwise false. It is an ordering
function
keyed on Key. This gives the generic equivalent of the key-sorting
operations (keysort/2, the third most used key* function). Fails
with {badmap, Map} for a non-map argument and {badkey, Key} if
Key is missing.
Similar functions can be added for native records, gb_trees, and
other data structures, but for native records other issues
need to be taken into consideration, so they are not included in
this EEP and will be handled separately.
With these additions, every lists:key* operation has a generic
equivalent that works on both tuples and maps. Assume a list of maps
People, each shaped #{name => atom(), age => integer()}.
%% find
lists:keysearch(50, 3, People)
≡ lists:search(fun(M) -> maps:has(age, 50, M) end, People)
%% delete first
lists:keydelete(mike, 2, People)
≡ lists:remove(fun(M) -> maps:has(name, mike, M) end, People)
%% replace first
lists:keyreplace(mike, 2, People, New)
≡ lists:replace(fun(M) -> maps:has(name, mike, M) end, New, People)
%% store (replace first match, otherwise append)
lists:keystore(mike, 2, People, New)
≡ lists:store(fun(M) -> maps:has(name, mike, M) end, New, People)
%% sort by key
lists:keysort(3, People)
≡ lists:sort(fun(A, B) -> maps:is_ordered(age, A, B) end, People)
A lists:key* function bundles two orthogonal concerns: a key
accessor (“the key is element N of the tuple”) and a list operation
(find, delete, replace, sort, …). Generalizing to arbitrary element
types means separating the two: the list operation becomes a generic
higher-order function taking a predicate or comparator, and the key
accessor becomes that predicate, built from a small per-data-type
helper. Most list operations already have a generic higher-order form
(any/2, search/2, sort/2, merge/3, umerge/3, map/2,
and uniq/2); this EEP supplies the missing ones.
has/3? #
Without has/3 one must use one clause to match the value and
another to handle that the absence of the key. That is:
lists:search(fun(#{age := 50}) -> true;
(#{}) -> false
end, People)
With has/3 this becomes the shorter and more readable:
lists:search(fun(M) -> maps:has(age, 50, M) end, People)
If partially-applied functions are adopted as suggested in EEP 81 this becomes even cleaner:
lists:search(fun maps:has(age, 50, _), People)
is_ordered/3? #
lists:keysort/3 is frequently used. Furthermore, it is easy to
create an incorrect ordering predicate.
lists:remove/2 rather than lists:delete/2 because delete/2
already exists. remove matches maps:remove/2.
has/3 rather than is_member/3 or matches/3: no existing OTP
collection bundles key+value into one predicate, so there is no exact
precedent. has reads well with partial application
(fun maps:has(k, v, _)) and extends naturally from the presence
predicate maps:is_key/2.
is_ordered/3 rather than order/3, compare/3, or an le/lteq
name: it returns a boolean, so the is_ prefix matches OTP’s
convention (is_key/2, is_element/2) and reads as a predicate
such as has/3 (order/3 reads as a verb/command, inconsistent
with a boolean result). compare/3 would suggest a three-way
lt|eq|gt result (as in logger:compare_levels/2), which this is
not. The le/lte spellings have essentially no public precedent
in OTP (logger_filters uses lteq), and name the operator rather
than the role; is_ordered names the role — an ordering function
for lists:sort/2 and friends.
records, gb_trees, and other containers #
The same has/3 predicate is desirable for native records
(records:has(Field, Value, Record)), gb_trees
(gb_trees:has(Key, Value, Tree)), and other keyed containers. These
are deliberately left out of this EEP:
Native records raise their own design questions — these are being worked out separately.
sets needs no addition: a set is its values, so
sets:is_element/2 already is the membership predicate.
Keeping this EEP limited to lists and maps lets the broadly useful
and uncontroversial part proceed while the container-specific questions
are settled in follow-up proposals.
Add map/record variants of every lists:key* function (e.g.
lists:mapkeyfind/3). Rejected: it multiplies the API surface by the
number of container types and does not compose. The generic
predicate approach adds a handful of functions that cover all types.
lists:key* functions to also accept maps
(e.g. let lists:keyfind(Key, Field, List) treat Field as a map
key when the elements are maps, or accept a predicate in place of the
position). Rejected for several reasons:
N argument of keyfind/3 is a
pos_integer() tuple position; a map key can also be an integer,
so lists:keyfind(V, 2, L) could not reliably distinguish “tuple
position 2” from “map key 2”. Any disambiguation rule would be
surprising.gb_trees, or user-defined keys
without yet more overloading.any/2, search/2), so overloading keymember/keyfind would
duplicate them. Adding the few missing first-match HOFs plus a
has/3 predicate is smaller, unambiguous, and type-friendly.keydelete/keytake/keyreplace,
about 290 production calls) with no concise, correct generic form,
and keeps every call site verbose.No existing code is affected by this addition, because only new functions are added.
This document is placed in the public domain or under the CC0-1.0-Universal license, whichever is more permissive.