Yomguithereal / baobab

JavaScript & TypeScript persistent and optionally immutable data tree with cursors.
MIT License
3.15k stars 115 forks source link

Support structural equality for keys #510

Open pbadenski opened 3 years ago

pbadenski commented 3 years ago

Would it be possible, similar to Immutable.JS (or Java..), have support for keys based on structural equality (ie. hashCode, equals)?

Yomguithereal commented 3 years ago

Hello @pbadenski. Do you have a code example of what this would entail or describe a use case you would have for it? The tree does not compute hash codes for the stored information for performance reasons but there may be some tricks regarding the tree transactions in some configurations.

pbadenski commented 3 years ago

I realised that this might require massive changes to baobab... possibly integrating it more closely with immutablejs as no builtin JS structures support structural equality for keys. Use case - we currently use rxjs to react to changes of entries in large collections & I was thinking if I could use baobab instead as a more lightweight (& potentially more efficient) solution. We use ImmutableJS collections which support structural equality and that allow us to use composite object keys.

Here's a rough example:

var Baobab = require("baobab")

class CompositeKey {
    hashCode() { ... }
    equals(o) { ... }
}

var tree = new Baobab({
  data: {  }
});
tree.set(['data', new CompositeKey("a", "b", "c")], 1)
tree.set(['data', new CompositeKey("a", "b", "c")], 5)
tree.set(['data', new CompositeKey("x", "y", "z")], 0)
tree.get() // => { 'data': Map(CompositeKey("a", "b", "c"): 5, CompositeKey("x", "y", "z"): 0) }
Yomguithereal commented 3 years ago

I am not sure I fully understand your use case here @pbadenski. But a decent workaround for composite key has always been scalar coercion. Like ["a", "b", "c"].join('§') for instance (or use the hash code itself as a key while relying on an external store to retrieve attached data maybe). I agree that modifying the library to check whether the traversed/compared objects have a hashCode or equals function seems to require much change as well as chosing a convention which feels quite arbitrary. I guess another way to handle this precise case would be to have a setting letting you give a function tasked with equality checks for every purity comparison in the library but this would probably have an impact on the overall perfomance. On a side note I was wondering whether to edit a new version of the library more closely related to functional lenses that could enable you to declare arbitrary setters/getters/traversers etc. Maybe this is parallel to what you need in a sense?

pbadenski commented 3 years ago

Thanks, we've actually been using scalar coercion, but changed it a while back because of the complexity and performance costs. Still - I like your use of § :D We've been using ~ ;)

I've actually found that immutablejs does something similar with https://github.com/redbadger/immutable-cursor - however only allows to register watchers at creation - which is not ideal...

I'm not sure about the application functional lenses approach in terms of my suggestion. I suppose - in theoretical sense - if it allowed to store arbitrary data structures & allow implementing a baobab compatible interface? So say - if I want to store Immutable.JS Map in baobab - how would that work? How would that be compatible with watchers?

Yomguithereal commented 3 years ago

I suppose - in theoretical sense - if it allowed to store arbitrary data structures & allow implementing a baobab compatible interface?

Yes it would be a little like this.

So say - if I want to store Immutable.JS Map in baobab - how would that work

For this to work I would need you to tell my utilities how to get/traverse and set at a given path. Which you can easily specify through functions and interfacing with ImmutableJS in this way for instance wouldn't be too complicated to write.

How would that be compatible with watchers?

My watchers, and this is as much a boon as a curse performance-wise, never rely on equality but only on path comparison and matching. Which make this compatible with any system such as Immutable for instance, as soon as you guarantee you will only be using baobab setters/getters and such. If you don't, I cannot make my watchers etc. work of course but this is already the case in the current state of the library and this is why I tell users not to mutate the tree by themselves to avoid this.

pbadenski commented 3 years ago

Looks like it could be really interesting and powerful 😄 I'm excited!

Yomguithereal commented 3 years ago

And did you take a look at recoiljs? In a way it has a similar approach to what I describe here (apart from the annoying fact that you cannot act on its atoms outside of a react component).

pbadenski commented 3 years ago

I haven't yet, I might for inspiration - I need this functionality outside of React :)