Hacker News Reader

Comment by arp242 | Hacker News Reader

> Going by their first example, the fact that I couldn't write list.delete(value) without realizing it involves a linear search is considered one of the benefits of Go.

I think this is mostly okay. Most experienced programmers will realize this is a linear search and that it may be slow on large arrays. And turns out that in the overwhelming majority of the cases that's just fine!

For other cases it's not-so-fine, but the mere presence of "list.delete" doesn't really stand in the way of implementing another, more efficient, solution.

Overall, I certainly think it's better than implementing the same linear searches all the time yourself!

View on HN

And it's not exactly gatekeeping to think that anyone who uses a method on any data structure on their platform should know the (rough) complexity of it (At least in the family constant, linear, or better/worse than linear). Removing a value from an array-backed list that isn't at the end is usually not a good idea.

My main problem with having "remove items by value" in standard library apis is that it assumes a notion of value equality. Having that notion inserted at the very "bottom" (Like Equals/GetHashCode in .NET for example) is a mistake that has caused an infinite amount of tears.

I much prefer this situation where the user must provide his own implementation and think about equality. It's boilerplate, but the boilerplate is useful here.

> I much prefer this situation where the user must provide his own implementation and think about equality.

But that doesn’t scale beyond the first user. Every subsequent developer now needs to read implementations to understand what the code does thanks to a lack of standardization for these functions. Consider if there was a smaller standard library with fewer interfaces and conventions, it would become a lot harder to understand a number of concepts in Go, by design. That’s fine, but conventions are what made Ruby on Rails projects so successful that they scaled up to being the monolith monstrosities most of us with startup experience ended up knowing them to be.

Note that I’m suggesting something akin to C++’s standard library where algorithms are already written for you to use and compose with. Yes, the drawbacks are a slower compile time, and some conventions like constexpr can really complicate things, but… I can’t say that a larger standard library or a larger set of conventions would make Go harder to use assuming the implementations hide a sufficient amount of complexity to outweigh the overhead of learning of them in the first place.

What functions provide more value than the overhead required to learn them? Delete is one such function, mutable immutable data structures generally are likely another. Yes, the documentation needs to specify big O complexity, but it can still be easy to read. For example: https://immutable-js.github.io/immutable-js/docs/#/List

The only way to get easier than that would be to use the same syntax for immutable operations as mutable ones: https://immerjs.github.io/immer/docs/introduction

I recognize that the Go community finds the built-in standard library restrictive now, but that’s no reason not to support a versioned standard library that ships separately but contains common functionality. I can only point to TypeScript for how such a system might work, given the large community project that exists to provide and publish types for that language, without actually publishing them with the language or compiler itself, excluding browser dom etc.

> But that doesn’t scale beyond the first user. Every subsequent developer now needs to read implementations to understand what the code does thanks to a lack of standardization for these functions.

There is no standardization. It’s a hidden piece of logic that developers slowly and painfully understand.

If I you have to pass an equality function when removing an item from a list by value (or equivalently when creating a set or dictionary) it would always be explicit. That doesn’t mean it can’t be standardized. A framework can provide typical implementations (and often does!) such as “ReferenceEquals” or “StringComparison.Ordinal” etc.

Another unfortunate side effect of the “equality as a property of the type” is that you can only have one such equality. And if you are passed a Set of dogs you still can’t know for sure whether the equality used is actually the one declared in the Dog type of at Set creation (or possibly in the Animal base class). It’s a mess. And it’s so easy to avoid - the default virtual equality is simply not necessary.

This is why I tend to like the example shown by the Immutable javascript libraries. They implement find-by-value using a library-specific calculation of equality built on primitives, but if you need something custom, you can pass predicate functions to, for example, perform your own equality check.

I think we're agreeing here, despite the initial disagreement. Standards don't have to solve every edge case, nor do they have to integrate with existing language patterns such as "equality as a property of the type" though a standard function could have multiple variants. The Go way of doing this might be like how regular expression function names are built.

Also, the library doesn't have to implement delete that way. If functional programming and predicate functions are an encouraged design pattern, you could replace delete-by-value functions with a filter function which could clearly indicate what happens if more than one value is found as well as how the equality check is performed but glosses over using slices to update the array. Some might say it's slower https://medium.com/@habibridho/here-is-why-no-one-write-gene... but it doesn't have to be slower, it's just tradeoffs in how the go compiler and language currently works vs could work.

Why would introducing value equality of all things be a problem? I think the opposite is true: many languages force you to write error-prone boilerplate because they lack a good definition of value equality built into the language and ecosystem.

Go in particular is worse on this front than any language more high-level than C. It defines equality for a very limited subset of built-in types, with no way to extend that notion of equality to anything that is not covered; nor any way to override the default equality assumptions. This makes it extremely painful whenever you want to do something even slightly advanced, such as creating a map with a struct as key when that struct has a pointer field .

And since pointers have lots of overloaded uses in Go, this turns a potentially small optimization (remember this field by pointer to avoid creating a copy) to a mammoth rewrite (we need to touch all code which was storing these as map keys).

I’m sorry for the “gatekeeping”, but do you really want to work together with someone that doesn’t know the language’s standard library or won’t even look at the documentation? And instead it would be positive that he/she writes the very implementation of something?

This problem transcends documentation of any given language's standard library. list.delete(value) in any programming language is a degenerate without an ordering or hash built-in to the underlying data structure.

If you ever need to delete based on value, it's a smell that a list is the wrong data structure. I'm sure there are cases in constrained environments where a linear search is heuristically okay, but generally in application development list.delete(value) is a hint that you're using the wrong data structure.

Good point. I guess the reason the author finds removing from lists to be relevant is because there is no Set structure in the Go standard library. They should use a `map[t]bool`, but that is non-obvious to many programmers.

My Google search suggests that maps in Go aren’t ordered. If so this doesn’t work in place of an array.

`map[t]struct{}` saves you a few bytes per entry. Just use the `_,found := foo[key]` form of lookup

map[t]struct{} so that the values don't require any space.

Unfortunately, map[t]bool (or map[t]struct{}) only works for special structs that happen to have equality defined for them. It's not a general purpose solution, it's just a hack.

> Most experienced programmers will realize this is a linear search and that it may be slow on large arrays.

Experienced programmer can think that values in a list with such operation are indexed by a hash and delete by value is O(1) unless there is a big warning in documentation. Novice programmer probably haven’t seen such combination of an array and a hash table and will assume O(N) as taught in a college.

Experienced programmers will know that such a thing is possible, but I've never seen any (non-JavaScript, non-PHP) language where primitive arrays involve a hash table.

And even in JS and PHP (and Lua) where arrays and hash tables are technically the same data structure, a hash table used as an array isn't actually indexed on elements, just numbers, so you don't get O(1) search.

Experienced programmers, if perf matters to their project, should think about their data structures, memory size, and access patterns. It's not clear why an experienced programmer would think an array defaults to wasting memory on a hash table. Why use an array, if they need lots of values and to delete them at random?

Experienced programmer will know whether the vanilla array of the language they use feature this kind of convoluted data structure.

Which, for virtually all languages, is “obviously not”.

Reply on news.ycombinator.com