how to check list equality in Typescript Set data structure?

user_8378312 0
Viewed 490

Consider the following Typescript code

const s = new Set<number[]>()
s.add([1, 2])
s.add([3, 4])
s.add([1, 2])
for (let t of s) {
  console.log(t)
} // prints [1, 2], [3, 4], [1, 2], but i would like the set not to have the [1, 2] duplicate
console.log(s.has([1, 2])) // prints false, i don't why it return false but I would like to return true

In python, having tuple automatically works

s = set()
s.add((1, 2)
s.add((1, 2)) # duplicate will not added
print((1, 2) in s) # True

How do I rewrite the Typescript code so set behaves in Python code? TIA

typescript
4 Answers

In python, sets rely on correct __hash__ and __eq__ implementations on items so that it can both

  • avoid holding duplicate values
  • check for membership of a value

However, in javascript, Set is comparatively less fully featured. Item membership is approximately based on whatever === does (with the caveat that NaN is considered the same as NaN, see MDN for details). This means that for objects and arrays, it is using reference equality.

So, in your example, if we wanted to get behavior similar to the python example, we would need to be using the same references like so.

const s = new Set<number[]>();
const oneTwo = [1,2];
const threeFour = [3,4];
s.add(oneTwo);
s.add(threeFour);
s.add(oneTwo);

now, the set s only has two items (as expected), and s.has(oneTwo) is true.

However, it is probably inconvenient for you to use the same references everywhere.

--

One workaround to this issue is to just JSON.stringify and JSON.parse everything that goes in/out of the Set. That way, it will check if the strings are equal (by value instead of by reference).

Another workaround to this issue is to just give up on JS sets altogether, and define some functions to operate on an array as if it were a set like so:

const areArraysEqual = (arrayA: number[], arrayB: number[]): boolean => {
    return arrayA.every((val, i) => val === arrayB[i]);
}

const insertIntoSet = (set: Array<number[]>, value: number[]): void => {
    const alreadyInSet = set.some((entry) => areArraysEqual(entry, value));
    if (!alreadyInSet) {
        set.push(value);
    }
}
user_134038450

s.has([1, 2]) returns false because of how JavaScript work.

console.log([] === []);

will return false because it's not the same object.

My preferred way is to create CustomSet class that extends Array<number[]>, then implement your own .add() and .has()

class CustomSet extends Array<number[]> {
  add(arr: number[]) {
    if (!this.has(arr)) this.push(arr);
  }

  has(arr: number[]) {
    for (let i = 0; i < this.length; i++) {
      if (this[i].every((v, j) => v === arr[j])) return true;
    }       
    return false;
  }
}

const s = new CustomSet()
s.add([1, 2])
s.add([3, 4])
s.add([1, 2])

console.log(t); // [[1, 2], [3, 4]] 
console.log(s.has([1, 2])); // true
console.log(s.has([1, 3])); // false

TS Playground

user_123972500

I don't think it's doable as the identical arrays would be pointing to different instances. If you try this:

class FooSet<P> {
  public s = new Set<P>();

  public has(foo: P): boolean {
    for (let item of this.s.values()) {
      // Hacky way to check equality between arrays
      // Do not do this
      if (JSON.stringify(item) === JSON.stringify(foo)) {
        return true;
      }
    }

    return false;
  }

  public add(foo: P) {
    let elementExists = this.has(foo);

    if (!elementExists) {
      this.s.add(foo);
    }
  }
}

const s = new FooSet<number[]>();

s.add([1, 2]);
s.add([2, 3]);
s.add([1, 2]);

for (let t of s.s) {
  console.log(t);
}

console.log(s.has([1, 2]));

you'd see how set behaves and how it asserts uniqueness. So to support your usecase you'd need to build some custom function wrapping the set

user_106008710

You have already received some explanation about Set's.

I'd like to stick with pure types.

First of all, TS does not play well with mutable values. It just does not track mutations.

Second, please keep in mind that my FIRST example is not super useful in practice. I just want to give you more overview how TS works.

My second example is much useful and I believe you can use it, however I have never extended any built- in classes in practice. I believe @T.J.Crowder can give some advise.

In order to force TS do some checking, we should create simple wrapper for our add logic.

const add = (set, value) => set.add(value)

Let's add some types:


type Value = [number, number];

In order to allow TS track our add operations, let's add some cache.

function add<S extends Set<Value> & { __cache?: any }, Vals extends Value>
    (set: S, value: [...Vals]) {
    return set.add(value)
}

Every time when add will be called, I will update { __cache?: any }.

{ __cache?: any } --> { __cache?: [] } --> { __cache?: [1,2] } --> { __cache?: [1,2] | [3,4] } etc ....

Here is our main logic:

type UpdateProp<T, Value> =
    T extends { __cache?: any[] }
    ? Set<Value> & Partial<Record<'__cache', T['__cache'] | Value>>
    : T & Partial<Record<'__cache', Value>>

type Check<T, Value> = T extends { __cache?: infer R } ? Value extends R ? 1 : 2 : 3

function add<
    S extends Set<Value> | Set<Value> & { __cache?: Value },
    Vals extends Value
>(set: S, value: [...Vals], ...flag: Check<S, Vals> extends 1 ? [never] : []): UpdateProp<S, Vals>

  1. I expect that first argument will be always a Set<Value> (without cache) or Set<Value> & { __cache?: Value } with cache.

  2. Vals extends Value infers our array of two numbers

  3. UpdateProp<S, Vals> smth similar to

const updateProp=(obj,value)=>{
    return {
        ...obj,
        ['__cache']:value
    }
}
  1. ...flag: Check<S, Vals> extends 1 ? [never] : [] - small validation trick. Here, in my blog you can find full explanation

So, every time, when smbd call add(set, [2,3]) __cache property will be updated/unionized.

Please keep in mind, __cache is optional, so don't worry, TS will not allow smth like that:set.__cache.

Full code:

type Value = [number, number]


type UpdateProp<T, Value> =
    T extends { __cache?: any[] }
    ? Set<Value> & Partial<Record<'__cache', T['__cache'] | Value>>
    : T & Partial<Record<'__cache', Value>>


type Check<T, Value> = T extends { __cache?: infer R } ? Value extends R ? 1 : 2 : 3

function add<
    S extends Set<Value> | Set<Value> & { __cache?: Value },
    Vals extends Value
>(set: S, value: [...Vals], ...flag: Check<S, Vals> extends 1 ? [never] : []): UpdateProp<S, Vals>

function add<S extends Set<Value> & { __cache?: any }, Vals extends Value>
    (set: S, value: [...Vals]) {
    return set.add(value)
}

const result = add(new Set<Value>(), [1, 2]) // ok

const result2 = add(result, [3,4]) // ok

const result3 = add(result2, [3,4]) // expected error

const result4 = add(result2, [4,3]) // ok

Playground

If you still want to use Set in normal way, like all people ))

you can extend Set class:

class MySet<T extends [number, number]> extends Set<T>{
    override add(val: T) {
        const [x, y] = val
        const keys = [...this.keys()];
        const exists = keys.findIndex(([a, b]) => a === x && b === y)
        if (exists === -1) {
            return this
        }

        super.add(val)
        return this
    }
}

I have used override keyword which is new in TS 4.3. Feel free to get rid of it if you have lower version of TS

Playground 2

user_84952540
Related