search

acutmore / proposal-keyby

1 stars 1 forks source link

readme

Exploring 'KeyBy'

This is a different take on https://github.com/tc39/proposal-richer-keys, looking at the same problem of "richer keys". It also includes an alternative to https://github.com/tc39/proposal-record-tuple.

The issue

Right now Map and Set always use SameValueZero for their internal equality predicate answering "Is this value in this collection?".

new Set([42, 42]).size; // 1
new Set([{}, {}]).size; // 2;

const m = new Map();

m.set("hello", "world");
m.set({}, "object");

m.get("hello"); // "world";
m.has({});      // false

As shown above, this means that when it comes to objects, all objects are only equal to themselves. There is no capability to override this behavior and allow two different objects to be treated equal within the collection.

const position1 = Object.freeze({ x: 0, y: 0 });
const position2 = Object.freeze({ x: 0, y: 0 });

const positions = new Set([position1, position2]);
positions.size; // 2

Whereas in Python:

position1 = (0, 0)
position2 = (0, 0)

positions = set()
positions.add(position1)
positions.add(position2)

print(len(positions)) # 1

or Clojure:

(def position1 '(0 0))
(def position2 '(0 0))
(count (set [position1 position2])) ; 1

Current workaround

One way to work around this limitation in JavaScript is to construct a string representation of the value.

const positions = new Set([JSON.stringify(position1), JSON.stringify(position2)]);
positions.size; // 1

The downsides of this are:

Alternatively two collections can be used, one to track uniqueness and another to track values:

const positions = [];
const positionKeys = new Set();
function add(position) {
    const asString = JSON.stringify(position);
    if (positionKeys.has(asString)) return;
    positions.push(position);
    positionKeys.add(asString);
}

The downsides of this are:

Proposal Ideas:

There are a collection of ideas here. These can be broken down into separate but composable proposals; or delivered all together as one proposal. Listing all of them here is to set out a vision of where we could end up in the future, to check how everything fits together.

Map and Set config (phase 1)

Allow Map and Set instances to be customized with a lookup function that will produce the value that will internally represent the key's uniqueness for that collection.

const keyBySet = new Set([], { keyBy: (v) => v.uuid });
keyBySet.add({ uuid: "ABCDE", id: 1 });
keyBySet.add({ uuid: "ABCDE", id: 2 });

keyBySet.has({ uuid: "ABCDE", id: 3 }); // true
[...keyBySet];                          // [{ uuid: "ABCDE", id: 1 }]

This addresses the issue of using two separate collections to achieve these semantics.

CompositeKey (phase 1)

Introduce a CompositeKey type. This type can represent the compound equality of a sequence of values.

const key1 = new CompositeKey(0, 0);
const key2 = new CompositeKey(0, 0);
const key3 = new CompositeKey(0, 1);

key1 !== key2;                       // true (separate objects)
CompositeKey.equal(key1, key2);      // true
CompositeKey.equal(key1, key3);      // false
Reflect.ownKeys(key1);               // []   (opaque empty object from the outside)
key1 instanceof CompositeKey;        // true
Object.isFrozen(key1);               // false (the key's value is internal+private)

This pairs nicely with the Map/Set config, allowing for more interesting keys. When the keyBy function returns a CompositeKey it is not compared with other values using SameValueZero but by the equality of two CompositeKeys.

const positions = new Set([], { keyBy: ({x, y}) => new CompositeKey(x, y) });

const position1 = Object.freeze({ x: 0, y: 0 });
const position2 = Object.freeze({ x: 0, y: 0 });

positions.add(position1);
positions.add(position2);
positions.size;                     // 1
[...positions].at(0) === position1; // true

CompositeKey can be nested recursively with the resulting 'structure' participating in the equality. A CompositeTree if you will.

const key1 = new CompositeKey(1, new CompositeKey(2, 3));
const key2 = new CompositeKey(1, new CompositeKey(2, 3));

CompositeKey.equal(key1, key2); // true

const key3 = new CompositeKey(1, 2, 3);
CompositeKey.equal(key1, key3); // false (nesting keys does not flatten them)

Symbol.keyBy (follow on?)

While being able to customize the keyBy function when constructing the collection provides flexibility, it may be common that the values themselves are best placed to define how their CompositeKey should be constructed to help ensure correctness.

const positions = new Set([], { keyBy: ({x, y}) => new CompositeKey(x, y) });

positions.add({ x: 0, y: 0, z: 1 });
positions.add({ x: 0, y: 0, z: 99 }); // 'z' prop is not inspected by the keyBy function
positions.add({ x: 0, y: 1 });

positions.values().toArray(); // [{ x: 0, y: 0, z: 1 }, { x:0, y: 1 }]

Introduce a new well-known Symbol to act as a co-ordination point:

class Position {
    x;
    y;

    constructor(x, y) {
        this.x = x;
        this.y = y;
    }

    [Symbol.keyBy]() {
        return new CompositeKey(Position, this.x, this.y);
    }
}

const positions = Set.usingKeys(); // name to be bike-shedded
// ~sugar for:
const positions = new Set([], { keyBy: (v) => v[Symbol.keyBy](), });

positions.add(new Position(0, 1));
positions.add(new Position(0, 1));
positions.add(new Position(0, 2));
positions.size; // 2

There can be a CompositeKey static factory that looks up the this symbol on the arguments keeping the constructor the minimal required functionality.

CompositeKey.of(position1, position2); // name tbc

// ~sugar for:
function lookupKey(v) {
    if (Object(v) === v) {
        let keyBy = v[Symbol.keyBy];
        return typeof keyBy === "function"
            ? Reflect.apply(keyBy, v, [])
            : v; // or throw if no keyBy protocol ?
    } else {
        return v;
    }
}
new CompositeKey(lookupKey(position1), lookupKey(position2));

There could potentially be a built-in decorator to aid classes in keeping their Symbol.keyBy protocol up-to-date as new fields are added.

class Position {
    @CompositeKey.field
    x;
    @CompositeKey.field
    y;
    @CompositeKey.field
    z;

    constructor(x, y, z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    [Symbol.keyBy]() {
        return CompositeKey.keyFor(this); // no need to update as new fields are added
    }
}

Records and Tuples (follow on?)

We can also have built in immutable values that take this further by implicitly implementing the Symbol.keyBy protocol to further reduce common boilerplate and help ensure correctness.

let r1 =       #{ x: 0, y: 0, offset: #[0, 0] };
let r2 = Record({ x: 0, y: 0, offset: Tuple(0, 0) });

typeof r1;           // "object"
Object.isFrozen(r1); // true
r1.x;                // 0
r1 === r2;           // false

r1[Symbol.keyBy]() instanceof CompositeKey; // true

let s = Set.usingKeys([r1]);
s.has(r2);           // true

The built-in keyBy implementation of these types will also look up Symbol.keyBy on the values within the Record/Tuple. i.e. it is deep equality, not shallow.

Existing Types (follow on?)

Immutable values types such as those in Temporal could implement Symbol.keyBy, without requiring users to work out the best way to represent these types using a CompositeKey.

Q+A