== operator on Belt.Set does not check if sets have same contents

I was surprised to see that using the == operator on two Belt.Set does not do comparison as I’d expect. Shouldn’t it check to see if the sets have the same contents? I know there is an eq operator, but I would expect == to perform the same function or generate an error saying it isn’t supported. Now I’m not sure when I can expect == to ever do the right thing with records of maps and set etc.

open Jest

type color = White | Black | Green

module Cmp = Id.MakeComparable({
  type t = color
  let cmp = (a, b) => a < b ? -1 : a > b ? 1 : 0
})

// fails
test("color set equality A", () => {
  let x = [White, Black, Green]->Set.fromArray(~id=module(Cmp))
  let y = [Green, White, Black]->Set.fromArray(~id=module(Cmp))
  let result = x == y
  result->expect->toEqual(true)
})

// passes
test("color set equality B", () => {
  let x = [White, Black, Green]->Set.fromArray(~id=module(Cmp))
  let y = [Green, White, Black]->Set.fromArray(~id=module(Cmp))
  let result = x->Set.eq(y)
  result->expect->toEqual(true)
})

// passes
test("color set equality C", () => {
  let x = [White, Black, Green]->Set.fromArray(~id=module(Cmp))
  let y = [White, Black, Green]->Set.fromArray(~id=module(Cmp))
  let result = x == y
  result->expect->toEqual(true)
})

// passes
test("lists are equal", () => {
  let x = list{1, 2, 3, 4, 5, 6}
  let y = list{1, 2, 3, 4, 5, 6}
  let result = x == y
  result->expect->toEqual(true)
})

Set (and Map, and similar containers) can construct its internal data slightly differently depending on the order that values are added to or removed from it. The issue here is that the == function and Set.eq function have different ideas of what a set’s “values” are. Internally, a set isn’t made of only its values–it’s an AVL tree of nested records. The == function is polymorphic and will attempt to compare data exactly as it’s laid out in memory. The Set.eq function knows how to navigate its internal tree structure and only compare the actual values.

This is correct. == is unsafe to use for those kinds of types, partially for this exact reason. In fact, I recommend enabling warning 102 so the compiler will warn you any time you use it unsafely like this. It’s always best to use a specialized equality function (i.e. Set.eq) for most types.

If you really want to use == to compare a set’s contents, then you can always use Set.toArray first which should always produce identical arrays (since it sorts the values).

2 Likes

I’ve heard an expression about dating - “chip, crack, crumble”. At first you think the person is amazing, and then you see little flaws and problems, and eventually you realize the person is completely not for you. I really hope your answer here is not the definitive one. I’ve been using ReScript for a few weeks now and think it is amazing. Haven’t seen any real problems yet. But this issue is definitely a crack and maybe even a crumble. If you can’t count on == doing something reasonable in a functional language, then I think this is a fundamental flaw. Suddenly you have no confidence comparing records that contain opaque data types that might have Sets or Maps in them. You lose confidence in the ability to compare values (values, not classes) for equality. You need to build eq functions around many of your data types (and all their wrappers) because you can’t trust == to do the right thing.

In this case, I don’t think using == should compile at all regardless of warnings or errors. The function has no real predictable meaning. === makes sense but == does not. In fact my tests worked just fine when sets of 2 items but failed with sets of 3; wasted a lot of time on that.

I really hope there is some plan for improving this on the roadmap. F# compares Sets and Maps as you’d expect without any surprises. When you define custom classes you can create custom hash and equality functions. If all your data structures are built using ReScript I would hope no special code would be needed.

I can’t figure out how to get the warning/error to appear. I put this in my bsconfig.json but it doesn’t seem to do anything.

  "warnings": {
    "number": "-102",
    "error": "+102"
  }

Try this config:

  "warnings": {
    "number": "+102",
    "error": "+102"
  }

That should configure polymorphic comparison as an error so the compiler fails if it’s used.

I agree (and I think many other people do too) that the current behavior of == is not ideal. Unfortunately, it’s something ReScript has inherited for historical reasons. But, fortunately, it’s easy to avoid as long as you have the warning/error enabled.

2 Likes

crumble. That turns on errors and warnings for nearly every equality comparison. Can’t compare records, variants, etc. This code below fails to compile. If you do it only as a warning how can you know the serious problems, like comparing Set, to the situations where it actually works? When can you safely use ==? I thought I could use it everywhere and now wonder if I can’t use it anywhere. I don’t see how this problem is easy to avoid. How can you know when it is safe to use == especially if using code from other people or using opaque types? It can’t be avoided if you want to do == since you need to write wrapper eq methods for everything. Seriously, how do people practically deal with this limitation? Super disappointed. Are we really stuck with this problem or are there plans to fix it?

type person = {name: string, age: int}
let a: person = {name: "justin", age: 3}
let b: person = {name: "justin", age: 3}
let areSame = a == b

It’s a known issue :slight_smile: Basically–don’t use == for functions and abstract types. For other types, it’s fine. There are workarounds, e.g. put a cmp function and a == overload in modules for custom data types. E.g.,

module Num: {
  type t

  let zero: t
  let cmp: (t, t) => int
  let \"==": (t, t) => bool
} = {
  type t = int

  let zero = 0
  let cmp = compare // Taking a shortcut here because I know it's int
  let \"==" = \"==" // Another shortcut here 
}

Now, your module can be used for Belt sets, maps, etc. and conveniently with == after opening in the right place:

let isZero = num => {
  open Num
  num == zero
}
1 Like

Didn’t know I could overload the == operator. So which of these work with ==? None of these look like functions or abstract
types to me.

Array
Record
Variant
Variant with payloads
Tuple

They all work, provided they contain non-abstract and non-function types. The rule propagates recursively. So array<int> is fine, array<t> is not fine (assuming t is an abstract type).

You can overload all the built-in operators, btw … +, -, etc. Use the power wisely and carefully.

Ok. Still wish there was a plan to improve this situation. How about a decorator @equals on a compare-like function and then the compiler just substitutes that function whenever == is used? And can’t the compiler warnings be smarter to only warn when doing == with those problematic situations? With 102 it warns comparing simple records. And doesn’t the compiler know what is behind those abstract types?

I’m not a ReScript developer, but it sounds to me like a special @equals decorator would introduce new complexity and also be only a partial solution. The rest of the comparison functions are also polymorphic like ==, so then we’d want special decorators for those, right? What about if multiple places define @equals for the type, which one is used? And so on.

Re: the warning for only dangerous comparison, that’s an interesting idea. I think it’s worthwhile exploring that. EDIT: a library-level solution that’s done in a popular OCaml standard library alternative, is to deliberately make == and friends work for int only and define scoped operators like I mentioned above for other types.

The compiler deliberately doesn’t ‘know’ what’s behind abstract types. That’s how it’s able to enforce that they can’t be mixed up with other types.

Thanks last question I hope. If I know what is behind my own abstract types and there is nothing fancy there can I safely use == as if they weren’t abstract? I’m considering making all my abstract types that I’ve defined non-abstract so I can use the == operator.

I’d recommend providing overloads of == and other comparison operators that you want to use, in the module where you define your abstract type. I showed an example above. Your future self will thank you because the code will be more refactorable.

You can define a functor to automatically overload a bunch of operators given just a comparison function, e.g. playground.

I just avoid == completely, as I do in JS. It just never seems worth it.

So it seems like there is no good solution here.

I tried turning on the compiler warning 102 but it essential gives a warning almost every time you use the == operator. Warnings on records of primitives, variants with payloads of primitives, tuples of primitives, simple wrapped primitives like type personId = PersonId(int), abstract types that are backed by primitives, arrays and lists of primitives, and options of primitives. This warning is essential saying “don’t use the == operator.” I don’t understand why the warning can’t only happen when dealing with abstract types and functions; that would make it useful.

I know of no way to get the warning to go away (not using polymorphic comparison) for records or variants with payloads or tuples without writing a lot of extremely tedious field-by-field comparison logic. C# recently added a much requested feature - records - which are like records in ReScript with structural equality checking. They added this because developers hated writing the boring, repetitive, error-prone equality and hash code logic that the compiler can do automatically. No chance I am going to write == functions for all my types.

I couldn’t get using the custom == operator to work. And even if it did, I’d still have to open it. And I’m not sure it will work if doing == with other object types in the same chunk of code.

The good news is most of the time == seems to work (from my very limited experiments) unless the underlying object is a Map or Set or something like that. So for me I think it is best to NOT use warning 102. And then keep using == and be careful not to embed a Map or Set or any structure in something that is likely to be compared using ==. If I’m using someone else’s code, I’m out of luck and won’t use ==.

Not almost - it should be every time. The polymorphic comparison operator should be avoided. The compiler manages to optimise simple cases, as you mentioned, but it should do that for === as well. When it has to fall back to poly equal the runtime code is pretty bad - it’s basically _.deepEqual with some ReScript salt.

1 Like

Probably the most dramatic statement I’ve seen around here, lol.

No plans for that on the roadmap.

3 Likes

You wouldn’t have to for all your types, only the abstract ones.

I couldn’t get using the custom == operator to work.

Could you elaborate on that? Why didn’t it work?

And even if it did, I’d still have to open it.

Yeah, it is slightly clunky but it’s pretty doable. I believe there’s also an issue to make the syntax a bit more compact, e.g. Num.(n1 == n2). It’s pretty standard practice in other libraries.

And I’m not sure it will work if doing == with other object types in the same chunk of code.

It will work if you manage the opens carefully. If there is a mistake, you’ll get a type error.

So for me I think it is best to NOT use warning 102.

That is a reasonable conclusion.

EDIT: comparison/equality ops are a basic and important language feature. Perhaps we should think about doing something similar in Belt to what Jane Street Core does i.e. putting the polymorphic functions in a separate module and in Belt overriding them to work on int only. Users would need to open Belt to opt in to this.

About can’t get custom == operator to work. This code generates error unused open Num. Don’t know why your code sample works but mine doesn’t.

module Num: {
  type t
  let zero: t
  let \"==": (t, t) => bool
} = {
  type t = int
  let zero = 0
  let \"==" = (a: t, b: t) => a != b // wrong for testing purposes
}

test("custom equality operator", () => {
  open Num
  let x = Num.zero
  let y = Num.zero
  let areEqual = x == y
  areEqual->expect->toEqual(false)
})

My original problem was I was wrapping a Set in an abstract type and got bitten when == didn’t work. Implementing a custom == doesn’t really help unless the compiler automatically uses it. If I’m comparing two of the type directly I can purposely open the module to ensure the right == operator is used. But then I might as well name the method eq and just use it like any other function. If my type is wrapped in a larger record I have to define == or eq all the way up.

I thought I could get help by turning on the compiler 102 warning. That would warn me about comparing sets. But unfortunately that warns you with almost every usage of == so that is no help at all. To get that warning message to go away you have to replace every usage of == with a custom eq operator, and no way am I going to write custom eq operators for every record, tuple, etc. especially when the polymorphic comparison works 99% of the time. My own abstract types usually work with the ==.

I get the sense there are limited resources developing and designing this language. And from reading the Jane Street stuff and googling “polymorphic compare” it seems like this is a very long standing and complicated issue. There also seems to be a goal to make ReScript a much better javascript, perhaps with some warts, and not necessarily a perfectly designed and complete language. It would be great if there were some quick and dirty ways to improve the situation.

First, help developers not fall into the problem I did. One possibility are decorators @nocomparison and @noequality. If these are on any type the compiler could prevent you from using == and the comparison operators on these types directly or on types that contain them. F# does this. Then put these decorators on the Belt Set and Map.

Second is providing a way to implement custom == operators that get used whenever the == is used without having to open a special module. Probably much harder to solve. Perhaps put a decorator on a named type indicating which function to use whenever the == appears.

module IntSet = {
  @equality(sameContents)
  type t=Items(array<int>)

  let sameContents = (a:t,b:t)=>...
}

I just double-checked. It seems that ReScript isn’t using the overloaded operator when used in infix position, only when used as a normal function call. E.g.,

// Generates: var test = Caml_obj.caml_equal;
let test = (n1, n2) => {
  open! Num
  n1 == n2
}

// Generates: var test = $eq$eq;
let test = (n1, n2) => {
  open! Num
  \"=="(n1, n2)
}

Of course I am expecting var test = $eq$eq for both. Looks like a bug to me. Somewhere between the parser and the compiler perhaps. I’ll check if there’s an issue and file one otherwise. EDIT: https://github.com/rescript-lang/rescript-compiler/issues/5302

I answered your questions here: https://github.com/rescript-lang/rescript-compiler/issues/5302#issuecomment-925457743