Semantics of Belt Id cmp

#1

Hi all!

I’m working with a Belt Map that uses a custom datastructure as it’s key. To do so there was a need to implement a comparable module.

Unfortunately I can’t find out exactly what the expected return values are for cmp.

https://rescript-lang.org/docs/manual/latest/api/belt/id#cmp

In particular, I would like to know how I can implement a partial order with only equivalence relations?

My assumption is that when the two arguments are equivalent, then cmp should return 0.
Do the return values -1, and 1 encode smaller than and bigger than relations?

If so, how would I denote the absence of a relation? Or does Comparable only allow for input spaces with a total order?

#2

The following is the code that I’m currently working with (it’s still an early draft :sweat_smile:).

type testIdentifier = {
        title: string,
        fullTitle: option<string>,
        file: option<string>
    }

module TestCmp = Belt.Id.MakeComparable({
    let matchFromEnd = (a, b) => switch (a, b) {
            | (Some(one), Some(other)) => Js.String.endsWith(one, other) || Js.String.endsWith(other, one)
            | (None, None) => true
            | _ => false
        }


  type t = testIdentifier
  let cmp = (a, b) => switch (Pervasives.compare(a.title, b.title), matchFromEnd(a.file, b.file)) {
          | (0, true) => 0
          | _ => 1
      }
})
#3

I would like to know how I can implement a partial order with only equivalence relations?

I could be wrong, but I think in mathematical terms, it’s technically possible to have a partial order with only equivalence relations, but it would be the trivial case where “partial ordering” means “no particular ordering.” A partial ordering is only really useful when a < b || b > a is true for at least some elements of the set.

That said, it appears you are comparing a string type, which has a total ordering defined for it, unless you have some other abstract notion of comparison that you care about. As you figured out, the Pervasives.compare function implements this total ordering.

However, you might want to use Belt.Map.String, which is specialized for when your keys are string types. It should not require a Comparable instance.

Hope that helps. Let me know if this doesn’t adequately answer your question.

2 Likes
#4

I think it does. In the case of Belt.Map specifically, what does a map supposed to do when two of its keys are unrelated? For instance, if you add keyA and then keyB, are the keys equal or not? Does the map already have keyB or it doesn’t? Should it replace a value for an old key, or create a new key?

I don’t know how never returning -1 affects a b-tree performance, but just for successfully searching a key within a map, I think your cmp is fine.

2 Likes
#5

Ah, so belt maps can use the ordering to optimise operations on the datastructure?

That makes sense, thanks!

1 Like