[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