Custom equality semantics for Immutable.js data structures

Question

I would like Sanctuary to provide Fantasy Land -compatible Map and Set types with value-based equality semantics. Ideally these values would be immutable, though this is not critical since Sanctuary would provide pure functions for merging and otherwise manipulating these values.

I would love to leverage the good work done by the Immutable.js team; I imagine implementing persistent data structures takes considerable effort!

The API provided by Immutable.js is of little importance since Sanctuary would expose functions for interacting with these values. The equality semantics of these types, though, are crucial.

This is unacceptable for my use case:

> Map([[[1, 2, 3], 'foo'], [[1, 2, 3], 'bar']])
Map { [1,2,3]: "foo", [1,2,3]: "bar" }

[1, 2, 3] is the same value as [1, 2, 3]. It should not be possible to have two map entries with the same key.

The handling of -0 is also problematic:

> Immutable.is(Map([[0, 0]]), Map([[-0, -0]]))
true

I realize it's possible to define the equality semantics of one's own types by defining equals methods, but I wish to redefine the equality semantics of native types such as Array and Number. Is this possible? The relevant file appears to be is.js, but I see no hooks for customization.

It's possible that Sanctuary's Map type could wrap the Immutable.js Map type. This would provide:

• a way to handle -0;
• an opportunity to perform value-based equality checks before performing an assoc operation which would normally result in a duplicate key; and
• a place to define the various fantasy-land/ methods.

Perhaps:

Map k v = { negativeZero :: Maybe v
          , value :: ImmutableMap k v
          , fantasy-land/equals :: Map k v ~> Map k v -> Boolean
          , fantasy-land/map :: Map k v ~> (k -> a) -> Map a v
          , fantasy-land/bimap :: Map k v ~> (k -> a, v -> b) -> Map a b
          , ...
          }

I'd like to be sure there's no other way to attain the desired equality semantics before creating wrappers such as the above. facebook/immutable-js#519 isn't promising.

Adhesive

The following is only my personal opinion. Instead of introducing a new abstract data type I'd solve this problem programmatically by defining a separate function/constructor that takes care of the value equality check while adding entries/constructing the Map. I always tend to accept the limitations of JS. Moreover I doubt that objects used as keys in Maps really benefit from persistent data structures, since they ought to be rather small, like value objects. Immutable.js seems to be more suitable for huge data structures like a redux store. – Latria

Thanks for the feedback, @ftor. You say that the objects used as keys won't benefit from being persistent data structures, but isn't the pertinent question whether the data structure itself—not its keys—benefits from being persistent? Since wrapping appears to be necessary, I now wonder whether we should wrap the native Map type instead and avoid a dependency: sanctuary-js/sanctuary#233. – Adhesive

Maybe try to use newtype-like wrappers around Array and Number? Modifying such a crucial property of builtins could be devastating. – Freehearted

I think not the ability to use reference types as keys but the reliable order and the strict separation of program and data level are the key benefits of the native Map type. Anyway, I'm curious how you solve this problem, since I experience a similar one with implementing monoidal Numbers, Arrays etc. for a more generic fold. – Latria

"Modifying such a crucial property of builtins could be devastating." What do you mean by this, @Bergi? I'm not suggesting modifying any existing behaviour. Are you suggesting that associating [1, 2, 3]–'baz' with an existing map would be very slow because we'd first need to see whether any of the keys is equal to [1, 2, 3]? That's a problem, certainly. What do you have in mind for the newtype-like wrappers? Could they solve this problem? – Adhesive

@Adhesive I mean that modifying global builtins that could be used by others (e.g. libraries you want to use, future versions of libraries your are using etc) is a bad idea, because it might break that other code. The hack is fine when you known and control your environment, but as a library you should not do it. – Freehearted

@Adhesive You know newtype in Haskell? E.g you could use a List (with sensible equality) instead of an array, and a MyNumber that distinguishes zeroes instead of a plain number. – Freehearted

"I mean that modifying global builtins that could be used by others […] is a bad idea". I completely agree, @Bergi. I'm not suggesting this. I'm suggesting defining a "newtype" wrapper for either Immutable.Map or the native Map. Users wouldn't need to know that the newtype makes use of some other Map type internally, nor would other users of that other Map type be affected in any way. – Adhesive

Oops, I misunderstood "redefine the equality semantics of native types such as Array and Number". Good you don't want to make a global modification :-) It sounded like defining Array.prototype.equals and Number.prototype.equals would solve the problem. – Freehearted

What I mean is that you should use a newtype wrapper around Array and Number which defines your custom .equals method, and then to instantiate the wrapper implicitly for all arrays and numbers that are passed into your wrapped Map. – Freehearted

That clarifies things. Thanks. I see now that "redefine" was a poor word choice. – Adhesive

I have two answers which may be valuable to you: 1) we create a custom type Dict which is capable of associating values to compound data keys, here and 2) a generic object equality function, here – Celiotomy

Didn't realize how old this question was, sorry – Celiotomy

Answer 1

Although this was asked long ago I don't see a reference to this simple solution:

const {Map, fromJS} = Immutable

// instead of this:
console.log(
  Map([[[1, 2, 3], 'foo'], [[1, 2, 3], 'bar']]).toString(),
)

// do this:
console.log(
  Map(fromJS([[[1, 2, 3], 'foo'], [[1, 2, 3], 'bar']])).toString()
)

<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/4.0.0-rc.12/immutable.min.js"></script>

By deeply converting the objects using fromJS you get the value equality

Brahmaputra

This approach doesn't support fantasy-land/equals, but it works well for values of built-in types. – Adhesive