[erlang-questions] adding maps:merge_nested/2

[Jesper Louis Andersen]

https://gist.github.com/jlouis/525249cd5d7860d691cdd97b3a4845af

One way of implementing this is simply to convert the two maps to lists and
sort them:

-module(z).

-export([t/0, merge/3]).

merge(F, L, R) ->
    L1 = lists:sort(maps:to_list(L)),
    L2 = lists:sort(maps:to_list(R)),
    merge(F, L1, L2, []).

This sets up the body of the merger function. We know the lists are
ordered, so we can exploit this fact to scrutinize each possible variant
case and handle them. The helper function f/3 handles the computation on
the merger function F. We just have to make sure each recursive (tail) call
consumes the elements correctly.

merge(_F, [], [], Acc) -> maps:from_list(Acc);
merge(F, [{KX, VX}|Xs], [], Acc) ->
    merge(F, Xs, [], f(KX, F(KX, {left, VX}), Acc));
merge(F, [], [{KY, VY} | Ys], Acc) ->
    merge(F, [], Ys, f(KY, F(KY, {right, VY}), Acc));
merge(F, [{KX, VX}|Xs] = Left, [{KY,VY}|Ys] = Right, Acc) ->
    if
        KX < KY -> merge(F, Xs, Right, f(KX, F(KX, {left, VX}), Acc));
        KX > KY -> merge(F, Left, Ys, f(KY, F(KY, {right, VY}), Acc));
        KX =:= KY -> merge(F, Xs, Ys, f(KX, F(KX, {both, VX, VY}), Acc))
   end.

This makes f/3 easily definable by matching on the output structure of F:

f(_K, undefined, Acc) -> Acc;
f(K, {ok, R}, Acc) -> [{K, R} | Acc].

And some rudimentary test:

t() ->
    Map1 = #{ a => 1, b => 2 },
    Map2 = #{ b => 3, c => 3 },
    Fun1 = fun
       (_K, {left, V}) -> {ok, V};
       (_K, {right, V}) -> {ok, V};
       (_K, {both, V1, V2}) -> {ok, V1 + V2}
    end,
    #{ a := 1, b := 5, c := 3 } = merge(Fun1, Map1, Map2),
    Map3 = #{  a => #{ b => 2, f=> #{}}  },
    Map4 = #{ a=> #{b => 3, c => 4, d=> #{e=> 5}} },
    Fun2 = fun
       F(_K, {left, V}) -> {ok, V};
       F(_K, {right, V}) -> {ok, V};
       F(_K, {both, L, R}) when is_map(L), is_map(R) -> {ok, merge(F, L,
R)};
       F(_K, {both, L, R}) -> {ok, [L, R]} %% arbitrary choice
    end,
    #{a => #{b => [2,3],c => 4,d => #{e => 5},f => #{}}} =
      merge(Fun2, Map3, Map4).

Your answer is in Map3, Map4 and Fun2 in the above. Note that you have to
say what to do when you have the case {both, L, R} where either L or R is
not a map. I just smash them into a list in the above, but there are
probably better solutions depending on your needs.



On Tue, Nov 15, 2016 at 9:01 PM Vans S <vans_163@REDACTED> wrote:

> What would happen if we had:
>
> Map1 = #{  a => #{ b => 2, f=> #{}}  },
> Map2 = #{ a=> #{b => 3, c => 4, d=> #{e=> 5}} }
>
> Would we need to do our own calls to recurse into each nest?
>
> On Tuesday, November 15, 2016 2:34 PM, Jesper Louis Andersen <
> jesper.louis.andersen@REDACTED> wrote:
>
>
>
> Hi Vans,
>
> Suppose we have
>
> Map1 = #{ a => 1, b => 2 },
> Map2 = #{ b => 3, c => 3 },
>
> and we call maps:merge(F, Map1, Map2). F will be called 3 times with the
> following inputs:
>
> F(a, {left, 1}) %% because a is only in the left side of the map.
> F(b, {both, 2, 3}) %% since b is in both maps and the value 2 is in the
> left and 3 in the right
> F(c, {right, 3}) %% since c is only in the right map
>
> In each case, we can return a new value {ok, V} for some new value V,
> perhaps computed from the input. Or we can return undefined in the case we
> wish to have the new map ignore that key completely and omit it from the
> produced/merged map.
>
>
> On Tue, Nov 15, 2016 at 4:23 PM Vans S <vans_163@REDACTED> wrote:
>
> > fun
> >>  (K, {left, VL}) -> Res;
> >>  (K, {right, VR}) -> Res;
> >>  (K, {both, VL, VR}) -> Res
> >> end
> >
> >Some questions on what VL/VR are once inside a nest, or does that happen
> all behind the scenes (going in nests). So you only need to compare the
> current values and return what will replace them?
> >
> >It seems like this is a more common use case then I initially thought.
> Having a general way to do this in erlang/OTP would be useful.
> >
> >
> >
> >
> >On Tuesday, November 15, 2016 7:54 AM, Jesper Louis Andersen <
> jesper.louis.andersen@REDACTED> wrote:
> >
> >
> >
> >
> >
> >
> >On Mon, Nov 14, 2016 at 9:20 PM Michael Truog <mjtruog@REDACTED> wrote:
> >
> >
> >>The main merge function you are missing in the maps module, is the
> merge/3 (instead of merge/2) that is common in other modules (like the
> dict/orddict modules).  I added an implementation of merge/3 at
> https://github.com/okeuday/mapsd due to needing the dict API elsewhere.
> With the merge/3 function it should be easier to merge nested maps, in
> whatever way is required, since one size shouldn't fit all.
> >>
> >
> >In OCaml, you often have a merge-function like this one:
> >
> >
> >val merge : ('k, 'v1, 'cmp) t -> ('k, 'v2, 'cmp) t -> f:(key:'k -> [
> >| `Left of 'v1
> >| `Right of 'v2
> >| `Both of 'v1 * 'v2
> >] -> 'v3 option) -> ('k, 'v3, 'cmp) t
> >
> >
> >which means that you have to supply a function of the form
> >
> >
> >fun
> >
> >  (K, {left, VL}) -> Res;
> >
> >  (K, {right, VR}) -> Res;
> >
> >  (K, {both, VL, VR}) -> Res
> >
> >end
> >
> >
> >where Res is either undefined | {ok, Result} for some result value. The
> semantics are that left,right, and both encodes on which side the value was
> in the input maps. And the Res encodes if a new value should be produced in
> the new map.
> >
> >_______________________________________________
> >>erlang-questions mailing list
> >>erlang-questions@REDACTED
> >>http://erlang.org/mailman/listinfo/erlang-questions
> >>
> >>
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20161115/694fb6f8/attachment.htm>