Operator constraints in Go | Hacker News Reader

Operator constraints in Go

blog.merovius.de

47 pointsMerovius18 comments

For a function, it makes sense to just write two functions, the easiest to use, and the one with maximum flaxibility.

    func SortOrdered[T constraints.Ordered](s []T) {
      // …
    }

    func Sort[T any](s []T, less func(T, T) bool) {
      // …
    }

For a data structure, I recommend using

    type SearchTree[T any] struct {
      Less func(T, T) bool
      // …
    }

and then writing two constructors

    func NewSearchTree(less func(T, T) bool) *SearchTree[T] {
      // …
      return &SearchTree[T]{
        Less: less,
        // …
      }
    }

    func NewOrderedSearchTree[T constraints.Ordered]() *SearchTree[T] {
      // …
      return &SearchTree[T]{
        Less: func(x, y T) bool {return x < y},
        // …
      }
    }

Personally, I very much dislike that this makes the zero value of `SearchTree[T]` not useful. I personally feel that anything which only handles data (as opposed to something like an os.File) shouldn't require explicit initialization.

I genuinely think I might personally converge on the `Comparator[T]` approach only (at least for types), for that reason.

Hrmm. How do float32 and float64 satisfy constraints.Ordered? The Go spec (which is almost uselessly vague and will some day contain 1000 pages of caveats) just says that floats are "comparable and ordered, as defined by the IEEE-754 standard" but of course that standard doesn't really say that, it specifically says that NaN are unordered. I just checked quickly with Compiler Explorer and float32<float32 emits UCOMISS on x86, which makes sense, resulting in 42.0<NaN and NaN<42.0 both being false, as expected. So how does it handle the constraint for float?

Basically, it doesn't work for sorting. https://pkg.go.dev/golang.org/x/exp/slices#Sort mentions this explicitly and has a suggested alternative solution. You can see this in action here: https://go.dev/play/p/6GuDa8ziU0L

Note in the second case, that's not "Go" sorting NaNs to the front, that's the requested result from the passed-in function. You could create any result you wanted with a suitable choice of such function.

This isn't particularly special to Go. Most languages have "quirks", to put it charitably, around floats. Even Haskell would have similar behavior. It's really the IEEE standard that is broken, arguably; defining an entity that is not equal to itself proceeds to effectively break a huge swathe of things that you may not have even realized was based on the presumption that the identity property holds, because... why would you think about what is based on that? It's so foundational. As anyone who has dealt with NaNs for any period of time can attest, it's really difficult to work with such entities.

(Similarly, while I understand what they were trying to get at, I think SQL NULL should be equal to itself. I could be down with NULL < 1 being false and NULL > 1 being false but I'm not a huge fan of how it's NULL either. We've had many languages written since then with more conventional ideas about "invalid" values and how they participate in operators and I think the modern way almost everything else works is better, even if it arguably less "correct".)

The entire C++ STL is a huge footgun for this very reason. None of the algorithms work on floats unless you guarantee the absence of NaN (which the STL assumes without being terribly vocal about it).

This is problematic even in dependently-typed languages like Idris, because while you can require a proof that something is not (or does not contain) NaN, it's pretty easy to call a function that is allowed to return NaN, which means that you actually cannot satisfy that proof after calling one of those functions unless you actually check again.

Rust handles this in a "correct", if annoying way: the stdlib sort requires its elements to have a "totally ordered" trait, and floating point doesn't have that trait. You have to either give a custom comparison function, or use a "non-NaN and totally orderable floating point" type some non-stdlib crates have.

This perfectly illustrates the cultural difference between Rust and Go: Rust wants to be "correct", Go wants to be "good enough".

> How do float32 and float64 satisfy constraints.Ordered?

Well, the simple answer is that constraints.Ordered is a type set which lists them: https://pkg.go.dev/golang.org/x/exp/constraints#Ordered

The other answer is of course, that float32 and float64 have a < operator, so every type listed in constraints.Ordered does, so you can use the < operator on a type parameter constrained by constraints.Orderded.

The real question you seem to be asking though, is "how does Go support < on float32 and float64 if the IEEE-754 standard says that NaN are not comparable". I can't comprehensively answer that, because I don't know that standard well enough. But for == the answer is that == is supported on floats and x == y is always false if either is NaN. Empirically, the same seems to be true for NaN <= NaN: https://go.dev/play/p/hB9CnrzpAVq

In any case, Wikipedia claims that IEEE-754 defines in fact an ordering, which is the one Go is going to use use: https://en.wikipedia.org/wiki/IEEE_754#Total-ordering_predic...

Nice write-up and summary. The emoji chart would be easier to visually parse with more traditional symbols e.g. [I realize these Unicode symbols could also be considered emoji but are less emotional.]

Or even with words. "yes" and "no" are much easier to distinguish at a glance than thumbs-up-emoji and thumbs-down-emoji.

I considered both. The issue I'm having is that "yes" and "no" is semantically wrong - or rather, semantically uninteresting. The interesting question is if a particular mechanism is "good" or "bad" in a particular way. For "boilerplate types", a "yes" is bad. For "custom order", a "yes" is good.

Writing "yes" or "no" (or using checkmarks and crosses) means I either have to put it on the reader to do that extra step of inference. Or that I have to re-phrase every item to be aligned in this way, while staying snappy. Or I could write "good" and "bad", of course, which seemed… overly simplistic.

Anyways, I did think about all of this and it was a conscious decision. For better or for worse. And I'm okay with it, criticism notwithstanding :)

Hmm wow, it was incomprehensible to me that much thought went into it to end up with a grid of yellow indecipherable blobs. Green and red are much more representative than thumbs up/down if the symbols look the same. How about green thumbs up and red thumbs down?

Even though you are being snarky and intentionally obnoxious: I even thought about that, yes. If unicode would allow to use red and green as skin tone modifiers, I would've done it. Except I probably wouldn't have used red and green, but red and blue or something. Because color blindness is a thing.

Look, I accept the criticism that the table is a bit hard to read. I thought about it and it's still the way I like it best. And it's the most low-stakes thing possible. It doesn't matter if it is slightly hard to read. It's my personal blog. "I like it best this way" is enough said.

I don't program in Go. But I could imagine that I might at some point want to sort a list of a custom struct by one of its members. And that's probably as advanced as it would get for my purposes.

Note that the article targets people writing generic code, not consuming it. So it's not really about what you want to sort. It's about what (and how) you want to support with your sorting algorithm.

As for that use-case: Go generics currently don't have a way to constrain on struct fields. So that will always have to be done with some sort of custom comparison function written by the user of your code, which returns the appropriate field.

Imagine looking at a Garbage Collected language that isn't even a complete language (You just got generics, FFS) and thinking, "Yeah, this is a great idea!"

What is shown in the examples I know as the term "generic interface" or, in some fancy languages, "typeclasses"

Reply on news.ycombinator.com