[erlang-questions] Proposed addition to gb_trees

Richard A. O'Keefe ok@REDACTED
Fri Nov 27 06:14:49 CET 2015


I would like to propose adding the following function
to gb_trees, and similar functions to other dictionary-like
things that don't have one.

-spec updatef(term(), fun((term()) -> term()), gb_tree()) -> gb_tree().

updatef(Key, Fun, {S, T}) ->
    T1 = updatef_1(Key, Fun, T),
    {S, T1}.

updatef_1(Key, Fun, {Key1, V, Smaller, Bigger}) when Key < Key1 ->
    {Key1, V, updatef_1(Key, Fun, Smaller), Bigger};
updatef_1(Key, Fun, {Key1, V, Smaller, Bigger}) when Key > Key1 ->
    {Key1, V, Smaller, updatef_1(Key, Fun, Bigger)};
updatef_1(Key, Fun, {_, V, Smaller, Bigger}) ->
    {Key, Fun(V), Smaller, Bigger}.


The idea is that

    updatef(Key, Fun, Tree) =
        update(Key, Fun(get(Key, Tree)), Tree)

except that it makes a single pass through the tree,
not two passes.

There are two questions about this, which is why I haven't
submitted patches.

(1) What's a good name for the function?  Update really is
    the right name for it, but the existing 'replace'
    function is called 'update'.

(2) What should happen if the key is not present in the
    tree?  gb_trees as its stands has an interface I
    find complex because practically everything occurs
    in two or three copies: assume key present, assume key
    absent, allow for either possibility.  Assuming it's
    absent doesn't make sense here, because there'd be
    nothing to pass to Fun.  But that leaves two copies,
    one which would err if the key was absent and the other
    which would just not change the tree.






More information about the erlang-questions mailing list