[erlang-questions] How to return first {Key, Value} from Map where Predicate is true
ok@REDACTED
ok@REDACTED
Fri Jan 9 02:12:57 CET 2015
> The more formal definition of problem is
>
> Write a function map_search_pred(Map, Pred) that returns the first element
> {Key,Value} in the map for which Pred(Key, Value) is true.
Can we start right at the beginning?
Looking at "maps" through the lens of hashed collections in a
range of other languages, what does "FIRST" *mean* for a hash?
(In Smalltalk, for example, #findFirst: is defined on sequences,
but *not* on dictionaries.)
Basically, what I'm getting at here is "do you REALLY mean
'FIRST' or do you actually mean 'ANY ONE'?"
>From the on-line documentation,
"The fuction (sic.) [to_list/2] returns a list of pairs
representing the key-value associations of Map, where
the pairs, [{K1,V1}, ..., {Kn,Vn}],
>>>> are returned in arbitrary order."
That is, the "FIRST" as returned by maps:to_list/2 is *NOT*
the first in any *semantic* order relevant to your program.
Since to_list/2 takes O(|Map|) time and space, it might be
better to do
map_search_pred(Map, Pred) ->
Filter = fun (K, V, {}) ->
case Pred(K, V)
of true -> {K,V}
; false -> {}
end
; (_, _, State) ->
State
end,
maps:fold(Filter, {}, Map).
This will take O(|Map|) time, but after Pred
returns true, it will not call Pred again.
(I do hope maps:fold/3 does not call maps:to_list/1
behind the scenes...)
Although the on-line documentation fails to say one way or
the other, the order in which key/value pairs are passed
to the filter is probably just as arbitary as the order of
to_list/1, so "FIRST" is just as dodgy a concept here as in
the other approach.
If "first" is important to you, I can't help wondering why
you are not using a data structure for which "first" is
well defined.
More information about the erlang-questions
mailing list