Diff of a Map

[slimshader]

Hi,

I am trying to implement efficient way to update the UI based in changes in Map<>. The idea is to use a diff() call on previous and current Map instances and process the Edits. The things is diff() takes 2 IEnumerable basically "flattening" the inputs.

Is there a way to get the Edits specifically for key-based data structures? If not, is the order of items in "flatted" IEnumerable view of a Map guaranteed to be stable to have reliable index-based Edits from the call to a diff()?

Or maybe other approach should be taken entirely?

[TysonMN]

I would not expect Map to be stable across changes, but I don't know for sure.

I know the problem of detecting and copying changes from one list to another by the name "merge".

I implemented merge in Elmish.WPF by seeing how Elm does it and copying them. See PR elmish/Elmish.WPF#214.

[louthy]

There's nothing in Map that gets 'edits', as it's simply an AVL tree structure. You can use:

    var map1 = Map((1, "One"), (2, "Two"));
    var map2 = Map((1, "One"), (2, "Two"), (3, "Three"));

   var additions = map2 - map1;

To find the additions, and:

    var map1 = Map((1, "One"), (2, "Two"));
    var map2 = Map((1, "One"));

   var removed = map1 - map2;

To find what's removed.

Then this will find the updates and create a new map with only the updated items in them:

    var map1 = Map((1, "One"), (2, "Two"));
    var map2 = Map((1, "One More"), (2, "Two More"));

   var changes = map1.Intersect(map2, Merge: (key, value1, value2) => new Change(value1, value2));

The Change type is obviously an implementation detail. So it's up to you to decide how to implement that.

You will be scanning the whole map three times and it's likely it won't handle changes in the hierarchy as elegantly as you would like, but I'm unclear exactly what solution you're building, so this might be enough.

The other approach, although not key/value-based, is to use the built-in differencing data-structures and algorithm. It works with lists, and has the capability of git-like branches, merging, and differencing:

    var docA = List("Hello", "World", "Again");
    var docB = List("Hello", "World");

    var patch = diff<EqString, string>(docA, docB);

    var docC = apply(patch, docA);

    Assert.True(docB == docC);

The above code works out a 'Patch' which could be applied to docA to make it match docB. Patches are made up of a set of Edit values (Insert, Delete, and Replace) which can be applied to another document to transform it.

• Here's the source for the patching system
• And the unit tests that show it in action

It seems a bit odd to me that you're using Map for a UI though. Surely it'd be something more akin to:

    public class Element
    {
        public readonly Seq<Attrs> Attributes;
        public readonly Seq<Element> Children;
    }

In which case you may find a combination of the two solutions useful.

[slimshader]

elmish/Elmish.WPF#214

Thanks for your answer, looking at the PR you linked will be especially interesting to me as I am also working on XAML/WPF-like solution for Unity game engine.

[slimshader]

There's nothing in Map that gets 'edits', as it's simply an AVL tree structure. You can use:

    var map1 = Map((1, "One"), (2, "Two"));
    var map2 = Map((1, "One"), (2, "Two"), (3, "Three"));

   var additions = map2 - map1;

To find the additions, and:

    var map1 = Map((1, "One"), (2, "Two"));
    var map2 = Map((1, "One"));

   var removed = map1 - map2;

To find what's removed.

Then this will find the updates and create a new map with only the updated items in them:

    var map1 = Map((1, "One"), (2, "Two"));
    var map2 = Map((1, "One More"), (2, "Two More"));

   var changes = map1.Intersect(map2, Merge: (key, value1, value2) => new Change(value1, value2));

The Change type is obviously an implementation detail. So it's up to you to decide how to implement that.

You will be scanning the whole map three times and it's likely it won't handle changes in the hierarchy as elegantly as you would like, but I'm unclear exactly what solution you're building, so this might be enough.

The other approach, although not key/value-based, is to use the built-in differencing data-structures and algorithm. It works with lists, and has the capability of git-like branches, merging, and differencing:

    var docA = List("Hello", "World", "Again");
    var docB = List("Hello", "World");

    var patch = diff<EqString, string>(docA, docB);

    var docC = apply(patch, docA);

    Assert.True(docB == docC);

The above code works out a 'Patch' which could be applied to docA to make it match docB. Patches are made up of a set of Edit values (Insert, Delete, and Replace) which can be applied to another document to transform it.

• Here's the source for the patching system
• And the unit tests that show it in action

It seems a bit odd to me that you're using Map for a UI though. Surely it'd be something more akin to:

    public class Element
    {
        public readonly Seq<Attrs> Attributes;
        public readonly Seq<Element> Children;
    }

In which case you may find a combination of the two solutions useful.

Thanks a lot! I was aware of diff()/Patch/Edits for sequential structures already available in Lang-Ext, I probably wasn't clear enough to explain that I was also looking for something specifically tailored for key-based containers.

My actual problem is this:

I have a set of domain objects in immutable DS, those domain objects are keyed by (x, y) pairs, currently stored in something akin to: IObservable<Map<Vec2i, SomeObject>>. There is also view layer that is observing this Map and keeps (mutable) Dictionary<Vec2i, SomeObjectView>>. Now the thing is the view really does not want to re-create this Dictionary every time the Map changes but would rather work with changes so that it could be more efficiently updated.

Now this got me thinking that maybe that my design is all wrong and the IObservable<> should not be of the Map<> type at all but rather if the "edits" of the domain?

[TysonMN]

Now this got me thinking that maybe that my design is all wrong and the IObservable<> should not be of the Map<> type at all but rather if the "edits" of the domain?

I don't think so. On the one hand, you are just moving the problem of computing the edits somewhere else. One way to do that is to precisely capture each edit as it is made, but that isn't always possible. Which is why, on the other hand, that implementations the MVU architecture (like Elmish.WPF) can (conceptually) take any Map<Vec2i, SomeObject> and compare it with a long-lasting mutable Dictionary<Vec2i, SomeObjectView>> so the differences, if any, can be efficiently displayed in the UI.

elmish/Elmish.WPF#214

Thanks for your answer, looking at the PR you linked will be especially interesting to me as I am also working on XAML/WPF-like solution for Unity game engine.

It sounds to me like you have the exact problem solved in that PR.