Is it a bug for Belt.MutableSet?

1

I write a program to generate new color between a image, then i write a test below.

module Color = {
  type t = (int, int, int, int) // r, g, b, a

  let cmp = (c1: t, c2: t) => {
    let (r1, g1, b1, _) = c1
    let (r2, g2, b2, _) = c2
    // only consider r,g,b
    r1 === r2 && g1 === g2 && b1 === b2 ? 0 : -1
  }

  let toRgba = (color: t) => {
    let (r, g, b, a) = color
    `rgba(${r->Belt.Int.toString},${g->Belt.Int.toString},${b->Belt.Int.toString},${a->Belt.Int.toString})`
  }

  let to0x = (color: t) => {
    let (r, g, b, _) = color
    lsl(r, 16)->lor(_, lsl(g, 8))->lor(_, b)
  }
}

module ColorId = Belt.Id.MakeComparable(Color)
let colorSet = Belt.MutableSet.make(~id=module(ColorId))
colorSet->Belt.MutableSet.add((0, 0, 0, 1))
colorSet->Belt.MutableSet.add((0, 0, 0, 1))
colorSet->Belt.MutableSet.add((0, 0, 0, 1))
colorSet->Belt.MutableSet.add((0, 0, 0, 2))
colorSet->Belt.MutableSet.add((0, 0, 0, 3))
colorSet->Belt.MutableSet.add((0, 0, 0, 4))
colorSet->Belt.MutableSet.add((0, 0, 0, 5))
colorSet->Belt.MutableSet.add((0, 0, 0, 6))
colorSet->Belt.MutableSet.add((0, 0, 1, 3))
Js.log2(`colorSet size: `, colorSet->Belt.MutableSet.size)
Js.log2(`colorSet to array: `, colorSet->Belt.MutableSet.toArray)

This program print:
image
The output is right, but when i add more color in colorSet, it behaves werid.

for _ in 0 to 270000 {
    if Js.Math.random() > 0.5 {
      colorSet->Belt.MutableSet.add((0, 0, 0, Js.Math.random_int(0, 256)))
    } else {
      colorSet->Belt.MutableSet.add((
        Js.Math.random_int(0, 256),
        Js.Math.random_int(0, 256),
        Js.Math.random_int(0, 256),
        Js.Math.random_int(0, 256),
      ))
    }
  }
Js.log2(`colorSet size: `, colorSet->Belt.MutableSet.size)
colorSet
  ->Belt.MutableSet.toArray
  ->Belt.Array.keep(item => {
    let (r, g, b, _) = item
    r === 0 && g === 0 && b === 0
  })
  ->Belt.Array.slice(~offset=0, ~len=10)
  ->Js.log2(`the element equal to (0, 0, 0, _) is: `, _)

The output:

image
image810Ă—233 5.37 KB

The colorSet should noly contains only one element which satisfies the condition r===0 && g===0 &&b===0. but it has a lot of element which satisfies this condition. Is it a bug, or just because i am not using Belt.MutableSet in the right way?

2

Hi @Mng12345

Since Belt.MutableSet is a sorted collection then I believe your cmp function will need to return consistent values for less than -1, equal to 0 and greater than 1.

Consider the current cmp function:

cmp((1, 2, 3, 4), (5, 6, 7, 8)) // -1
cmp((5, 6, 7, 8), (1, 2, 3, 4)) // -1

This means (1, 2, 3, 4) is less than (5, 6, 7, 8) and (5, 6, 7, 8) is less than (1, 2, 3, 4) , which will cause the sorted collection to behave unexpectedly.

Here’s an example that should produce more reliable results:

let cmp = (c1: t, c2: t) => {
  let (a1, a2, a3, _) = c1
  let (b1, b2, b3, _) = c2
  if a1 === b1 {
    if a2 === b2 {
      a3 - b3
    } else {
      a2 - b2
    }
  } else {
    a1 - b1
  }
}
2 Likes
3

@kevanstannard thank you. It works after i have changing the function cmp to this:
image

But how could i make a MutableSet if i can not giving the order of it’s element?

1 Like
4

There’s also Belt.HashSet | ReScript API that is also mutable and requires you to provide eq and hash functions.

Also, you can use Set from JavaScript Set - JavaScript | MDN, but you’ll need to write your own bindings, or find a 3rd party library that defines them.

3 Likes
5

Any set implementation requires some way to distinguish values. Belt’s MutableSet uses a comparison function. HashSet uses equality and hashing functions. JavaScript’s built-in set uses JavaScript’s physical equality (===).

The JavaScript set has this danger:

let x = new Set();
let a = [1, 2, 3, 4];
x.add(a);
x.has([1, 2, 3, 4]); // FALSE!

This is because [1, 2, 3, 4] === [1, 2, 3, 4] is false in JavaScript. A proper comparison or equality function that’s customized for your data type will not have this problem.

IMO, writing a comparison function is almost always going to be easier to implement than a hashing function, since ReScript doesn’t expose hashing utilities in a convenient way.

If you really don’t want to use any of the above options, though, you can always implement your own mutable set structure by just using ref and list and an equality function:

type t<'a> = ref<list<'a>>
let make = () => ref(list{})
let add = (t, a) => t := list{a, ...t.contents}
let remove = (t, a, eq) => t := Belt.List.keep(t.contents, b => !eq(a, b))
let has = (t, a, eq) => Belt.List.has(t.contents, a, eq)

This will be much less performant than just using the proper MutableSet, and it still requires an equality function. Since writing a comparison function is only marginally more complicated than an equality function, then I’m not sure there’s much of a benefit. However, for very small sets, it may be sufficient.

3 Likes