Stream: API design

Topic: Checking equality

Kasper Møller Andersen (Jun 14 2024 at 21:05):

Roc has the classic == operator, and the Eq ability to implement custom comparison. But I'm curious if there was ever discussion to drop this API, or at least make something significantly different?

The reason I ask is that I feel the existing API has many of the problems that are solved by e.g. Inspect. That is, checking equality is conceptually simple, and is exposed with a simple operator, but in reality, there are many kinds of equality, and putting them all behind one interface presents foot guns.

For example, for any entity with an ID, I may want my equality check to only check whether two entities have the same ID. But I may also want an equality check for whether two entities contain the same data regardless of ID. Do I implement Eq to mean one or the other?

Similarly, a full equality check may be computationally expensive, so maybe I implement a cheap check to compliment the full thing. Should that be the Eq implementation or not?

One could argue that you shouldn't implement Eq at all for types where it's not clear what kind of equality it means. But is there an underlying assumption that Eq always implies a specific kind of equality?

Brendan Hansknecht (Jun 14 2024 at 21:23):

Eq is explicitly flexible to support non structural equality. For example, dict and set do and out of order eq despite having an order. Types can opt into whichever default form of eq makes most sense for them. Also, only opaque types get to opt into this. All other types just do structural eq.

I don't see how inspect fixes anything related to eq, can you expand on that

Brendan Hansknecht (Jun 14 2024 at 21:24):

As for your id example. I would default to just the id. It sounds like that is your short circuit expectation and the deep equal is an exception....but ultimately this would be type specific.

Kasper Møller Andersen (Jun 14 2024 at 21:28):

I meant that Inspect solves a similar problem in a different domain. That is, instead of each type only getting a single toString function to convert to a string, you pass it a formatter to specify how it should be done. Presumably something analogous for equality might make sense.

Brendan Hansknecht (Jun 14 2024 at 21:29):

Ah, you mean eq were you also pass a config

Brendan Hansknecht (Jun 14 2024 at 21:31):

I think even if we added that, we would still want a default == for convenience. Even if you could separately call Bool.eq a b myConfig

Though is there really an advantage to that over MySpecialEq a b. Cause I wouldn't expect much if any sharing between configs. So I would expect it to be custom by type rather than something more general like inspect.

Brendan Hansknecht (Jun 14 2024 at 21:33):

I guess if we are thinking of a more bespoke versions of equal, we could make deep, custom, and structural equal or something like that.

Kasper Møller Andersen (Jun 14 2024 at 21:35):

I also think just having functions would be better in a lot of cases, but having the == operator even be available means people will want to use it when it's not prudent.

I also know just outright removing == would be controversial, so I won't suggest that. But maybe it's possible to make it clearer what its semantics should be.

Kasper Møller Andersen (Jun 14 2024 at 21:39):

I think Dict equality is an interesting case too. Equality probably shouldn't account for ordering there, but there are also times when you do care about the ordering of the keys. In that case, a different type a la OrderedDict may be preferable, but if Dict already maintains order, then being able to compare equality one way or another might be nice too.

Brendan Hansknecht (Jun 14 2024 at 22:01):

If you need ordering, just myDict |> Dict.toList == ... or we could add an explicit method to dict. That is definitely not the common case for an unordered dict.

But yeah, I agree overall, that semantics are kinda user dependent right now, which could definitely lead to bugs/confusion in some cases

Brendan Hansknecht (Jun 14 2024 at 22:03):

At the same time, I think it is user dependent in essentially all languages and some common expectations have arisen. Not saying that is good, but it does have a common set of expectations.

Kasper Møller Andersen (Jun 15 2024 at 09:11):

My point of reference is that when I need an ordered dictionary at work, I reach for ListMap in Scala. In our Elm code, we've also implemented an ordered set.

In Scala, ListMap implements the Map trait, so it's still easy to pass around to the code that doesn't care if the map is ordered or not, and I get the right equality behavior. Since Roc doesn't want that level of abstraction, I would expect something like a Dict.isEqWithOrdering function that I could use. Converting to a list would also be fair, though less efficient presumably.

Kasper Møller Andersen (Jun 15 2024 at 09:13):

It would be nice for == to always imply structural equality (or something that behaves like it), and then asking users to implement their own functions for other equality checks I think.

Kasper Møller Andersen (Jun 15 2024 at 09:15):

Relatedly, I've wanted an isRefEq function in Elm a few times, since it can be a big performance optimization when implementing custom equality functions.

Brendan Hansknecht (Jun 15 2024 at 17:24):

Ok. So let's piece that apart.

Firstly, Roc's Dict has an ordering based on insertion and deletion. So it should feel pretty similar to ListMap. Though it is not an ordered dictionary (at least not how ordered is normally used. Ordered dict normally means automatically sorted).

Brendan Hansknecht (Jun 15 2024 at 17:26):

Secondly, structural equality is essentially meaningless on Roc's dict. Due to the metadata, it will essentially always be false.
This is true of many data structures. On top of that, structural equal is often very very very slow in the worst case.

Brendan Hansknecht (Jun 15 2024 at 17:27):

This is why I think == defaulting to structural equal is not a good idea. Especially given opaque types can be used for data hiding so it literally may expose data that should be hidden.

Brendan Hansknecht (Jun 15 2024 at 17:29):

As for Dict.isEqWithOrdering, we totally could add that. It would be equivalent to Dict.toList dictA == Dict.toList dictB. toList is a free operation so no performance concerns.

Brendan Hansknecht (Jun 15 2024 at 17:31):

I don't think isRefEq is generally safe in roc. So I think it could only be implemented/used safely for built-in types (I think list may already do this as a short circuit). Not to mention copying due to uniqueness and refcounting can happen. So I don't think it would generally fit well as something available to roc userland.

Kasper Møller Andersen (Jun 15 2024 at 17:46):

Ah yes, I wasn't referring to Dict applying any sorting, thanks for clearing that up.

For structural equality being false due to meta data, this was what I meant by something "behaving like it". It would be nice for structural equality (minus meta data) to be the target for what Eq should check, and relegate other behavior to dedicated functions. On the other hand, that definitely has some bad corner cases, which just brings us back to the original point of == being too simple an interface for what we are asking if it.

I wasn't aware Dict is implemented as a list, so nice for that :blush: though presumably e.g. Set.isEqWithOrdering would be cheaper than doing Set.toList a == Set.toList b, as I assume Set is based on Dict with dummy values assigned?

Kasper Møller Andersen (Jun 15 2024 at 17:50):

I'm curious why isRefEq would be unsafe though? Even in the face of copies and ref counting, wouldn't it just be cases which returns false, even though they could have been true? In other words, I'm only looking for it being a short circuit operation when it's definitely true, so having false negatives isn't a deal breaker. Only false positives would be bad.

Brendan Hansknecht (Jun 15 2024 at 18:16):

I guess that is what I mean by unsafe. It is only valid as a short circuit. Used otherwise could be buggy. Also, seamless slice might lead to some strange edge cases if you aren't careful. As in pointers to the same allocations but different slices of the allocation. Or same start but different length.

Brendan Hansknecht (Jun 15 2024 at 18:19):

Yeah, for set, it should also be free, but I would guess that today we wouldn't optimize it correctly. Cause maping a List (key, {}) to a List key should be a noop. They are exactly the same in memory

Kasper Møller Andersen (Jun 15 2024 at 18:28):

True, slices can present false positives. Unless they get a special implementation of course. I would personally want really want something like this short circuiting available to be able to make best use of Roc's guarantees. I.e. this is a place where Roc can offer better performance than something like C++ due to its design.

Even if it's already used on List, I would want to be able to apply it on all my custom Eq implementations essentially.

Brendan Hansknecht (Jun 15 2024 at 18:29):

To be fair, all pointers in roc are either tags or lists, so roc should always be able to apply this automatically

Brendan Hansknecht (Jun 15 2024 at 18:30):

*or strings

Kasper Møller Andersen (Jun 15 2024 at 18:32):

Sorry, I also meant to have it applied for custom checks which are not exposed as Eq implementations (like Dict.isEqWithOrdering). Presumably those cases would not be automatically covered.

Brendan Hansknecht (Jun 15 2024 at 18:56):

So like, for that check, you would compare the underlying lists. So the lists would get short circuit eval.

Kasper Møller Andersen (Jun 15 2024 at 19:08):

Sure, but that was just an example of a non-Eq equality check. Other non-Eq checks might not hit that.

Kasper Møller Andersen (Jun 15 2024 at 19:11):

Rather than isRefEq : a, a -> Bool, the function might instead be isRefEq : a, a -> [DefinitelyEqual, EqualityUnknown], which would make it clearer what it can be used for I'd say.

Kasper Møller Andersen (Jun 15 2024 at 20:43):

As an example of a non-Eq equality check where this would be useful: I've had to write a function which compares two lists for equality, where each element in the list is a record. But some fields in those records should be ignored for equality, so there's no way around iterating through the lists and checking the right fields. Except if you can tell the two lists have the same reference and at least short circuit the process some of the time.

Brendan Hansknecht (Jun 15 2024 at 21:33):

So that would just be normal list equality short circuit. So nothing special needed.

Brendan Hansknecht (Jun 15 2024 at 21:35):

I think all pointer types should be possible to automatically have short circuit equality in roc. As I said earlier, the only pointer types in roc are controlled by the language (str, list, recursive tag, and I guess box). So roc can just define their equality to short circuit by default. Users don't need to define anything for that or ever call something like isRefEq

Brendan Hansknecht (Jun 15 2024 at 21:38):

When writing custom equal of a type wrapping a list, doing a.list == b.list will also short circuit.

Brendan Hansknecht (Jun 15 2024 at 21:38):

I guess that is only fine if you are ok using the records ==

Brendan Hansknecht (Jun 15 2024 at 21:42):

So I think I see what you are saying. Like you have a list of records, but you want to check equality on a limited subset of fields. That equality would be check with List.walkUntil such that it could early exit, but you would like to short circuit on the exact same list instance, but that wouldn't be possible cause you are only looking at a couple of the fields and the record doesn't have a custom equal only for those couple of fields.

Kasper Møller Andersen (Jun 16 2024 at 06:21):

Indeed, though I would also have to check that the lists have the same length, then do List.map2 a b Pair, and then do walkUntil

Richard Feldman (Jun 16 2024 at 14:37):

I really don't want the concept of "reference equality" to be a thing anyone ever has to think about in Roc, so the explicit plan is to never add anything like this! :big_smile:

Richard Feldman (Jun 16 2024 at 14:43):

I appreciate that in this particular scenario it would be helpful for performance, but I'd be really curious to know how important that short-circuit was in practice in this situation

Richard Feldman (Jun 16 2024 at 14:43):

it seems extremely narrow! :sweat_smile:

Kasper Møller Andersen (Jun 16 2024 at 15:07):

Oh, totally narrow. Another use case would be implementing something like the Html.Lazy.lazyN functions from Elm in user space. In Roc that might be provided by the platform, but the only thing that's really missing to make it implementable in user space is something like isRefEq as far as I can tell.

It's basically useful for implementing memoization.

Kasper Møller Andersen (Jun 16 2024 at 15:26):

To be clear, the isRefEq ask isn't all that big for me, and is really just an offshoot of the original question about considerations about what Eq actually implies.

Richard Feldman (Jun 16 2024 at 15:32):

Kasper Møller Andersen said:

Oh, totally narrow. Another use case would be implementing something like the Html.Lazy.lazyN functions from Elm in user space. In Roc that might be provided by the platform, but the only thing that's really missing to make it implementable in user space is something like isRefEq as far as I can tell.

the bigger problem with the lazy functions is that they'd be completely broken in Roc because we do in-place mutation...so they would just give the wrong answer and cause bugs :laughing:

Kasper Møller Andersen (Jun 16 2024 at 16:05):

Would it though? Roc only does in place mutation if there's only a single reference to some data, but if you implement lazyN equivalents in user space, you also need to explicitly store the input in a cache somewhere to be able to compare it later. This automatically gives you multiple references, so it would work fine as far as I can tell :grinning_face_with_smiling_eyes:

Last updated: Jul 06 2025 at 12:14 UTC