[HN Gopher] Operator Constraints in Go
___________________________________________________________________
Operator Constraints in Go
Author : Merovius
Score : 37 points
Date : 2022-05-23 17:39 UTC (5 hours ago)
(HTM) web link (blog.merovius.de)
(TXT) w3m dump (blog.merovius.de)
| avgcorrection wrote:
| 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.
| Merovius wrote:
| 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.
| jeffbee wrote:
| 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?
| jerf wrote:
| 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".)
| jeffbee wrote:
| 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).
| nerdponx wrote:
| 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.
| dinosaurdynasty wrote:
| 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.
| Merovius wrote:
| > 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...
| lalaithion wrote:
| 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}, // ... }
| }
| Merovius wrote:
| 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.
___________________________________________________________________
(page generated 2022-05-23 23:01 UTC)