Hacker News Reader

Comment by j1elo | Hacker News Reader

Go still doesn't have Set types. The usual thing to do is using a map of your type to either an empty struct, or maybe a bool, if I got that correctly (have only been using Go for a couple months so far)

Did you implement your own Set type and primitive functions?

View on HN

Yes in Go I think I’m mostly tempted to reinvent the wheel every few lines of code, for the sheer lack of stdlib abstractions I’ve grown used to.

This is funny to me, because Go is often touted as a language that has "everything you need" in the stdlib. Of course, I'm coming from the nodejs world, where before you can start working you first need to evaluate and choose: typescript or not typescript and if yes what build tool chain, which test runner, which assertion lib, which mocking lib, etc etc. Not really that long ago when you had to choose which async lib (now you just need to choose which async color).

Thankfully a lot of that stuff is in nodejs now, and there's a commitment to maintain parity with Web APIs which also helps, but there's still a lot of half-done work and path-dependencies on outside libs.

> This is funny to me, because Go is often touted as a language that has "everything you need" in the stdlib.

My usual example of something missing from the standard library is

    func max(a, b int) int {
      if a > b {
        return a
      } else {
        return b
      }
    }

math.Max only operates on two float64s (due to the absence of function overloads; many standard library functions such as this predated generics), so if you want to avoid casting (and/or potential loss of precision if you're working with int64), you need to reinvent the wheel.

Go has had generic forms of the `min` and `max` functions as builtins since 1.21. https://pkg.go.dev/builtin#max

Go 1.21 is the version from which it is noticeable that they are pushing towards (re)implementing things that were lacking before due to missing support for generics.

Like the new slices package, meant to do common operations on slices, that is brand new on 1.21.

I wouldn't be surprised to see more and more new additions leveraging generics in next releases.

Good to know! I admittedly haven't written much Go in the past year, and while min / max were some of the most egregious examples, I'm sure there are plenty more that still exist.

You actually don't need any of that stuff, you can just write .js files and run them in node. The node.js standard library is quite extensive.

It's much much better now, especially if you are willing to adopt the experimental modules.

I did it using maps and generics and implemented a subset of the convenience methods that python has in sets.

Most languages implement sets using maps. The only major difference you can optimise for is the fact that in majority usage, keys in maps are likely to exist, whereas sets are used for membership checks. Bar that, you can just as well use a map with a dummy value.

Can you give a reference for that? It sounds very unlikely to me, although I've only read/gone through two relevant standard library implementations: F# and OCaml.

Neither of them use dummy values as you suggest. They have similar implementations (both are AVL trees) but sets really do contain only one value while maps contain two. I would be surprised if many other languages did as you suggest.

Python, Ruby, Perl. Languages where hashmaps are a builtin.

Python has its own set type not based on hashmap/dict, and that's been the case for years.

The set implementation points out some of the differences, at https://github.com/python/cpython/blob/main/Objects/setobjec... :

   Unlike the dictionary implementation, the lookkey function can return
   NULL if the rich comparison returns an error.

   Use cases for sets differ considerably from dictionaries where looked-up
   keys are more likely to be present.  In contrast, sets are primarily
   about membership testing where the presence of an element is not known in
   advance.  Accordingly, the set implementation needs to optimize for both
   the found and not-found case.

Java as well: https://github.com/pengisgood/jdk-source-code/blob/master/sr...

EDIT : and Rust: https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.ht... (this is used by the default implementation of HashSet).

Rust's HashSet is a HashMap mapping to "()", which is Rust's equivalent to "void".

That is true for the internal implementation details but HashSet provides a different API, it is not just a type alias. So you don't have to worry about semantics of what the values mean (like the bools in Go), and it has no size overhead.

Update: Looks like I had good reason to be surprised. Thanks everyone for the examples.

Reply on news.ycombinator.com