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!
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.
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.
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.
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.
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).
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.
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.
Which, for virtually all languages, is “obviously not”.
An example would be https://hackage.haskell.org/package/containers-0.4.0.0/docs/....
size :: Map k a -> IntSource
O(1). The number of elements in the map.
member :: Ord k => k -> Map k a -> BoolSource
O(log n). Is the key a member of the map? See also notMember.
lookup :: Ord k => k -> Map k a -> Maybe aSource
O(log n). Lookup the value at a key in the map.
> Time complexity: O(N) where N is the number of elements to traverse to get to the element at index. This makes asking for the first or the last element of the list O(1).
I agree this is something more documentations should do when possible; it doesn't even have to be big-O notation as far as I'm concerned, just a "this will iterate over all keys" will be fine.
Ruby's delete() doesn't mention any of this, although you can easily see the (C) implementation in the documentation[2]. In principle at least, this doesn't have to be O(n) if the underlying implementation would be a hash for example, which of course has its own downsides but something like PHP may actually do this with their arrays as they're kind of a mixed data structure? Not sure.
[1]: from https://redis.io/commands/lindex
[2]: https://ruby-doc.org/core-3.0.0/Array.html#method-i-delete
Also, in languages with GCs, linked lists do not necessarily cause more cache misses than arrays, due to the way allocation works (this is especially true if you have a compacting GC, but bump-pointer allocation often makes it work even when you don't).
I will use this in English regardless. I like it.
Perfect example: Datetimes. In Golang, if you want to convert a string to a datetime (or vice versa), you _need_ to look at the godoc for datetime because it uses very specific permutations of "Jan 2, 2006" that you _have_ to include in your code. This is much more confusing than how this would be done in Python (provide the format of the date using ISO8601 notation) or Ruby (provide the string, get a Datetime, done).
The primary problem that I think the author was trying to get at is that go lacks tools for building abstractions. In a language with generic functions (for instance), it would be possible to implement a delete_at function completely in user code. The fact that you cannot reflects poorly on the language.
Of course it will always be possible to write functions that have arbitrarily slow time complexities. That's something you have to be aware of, with any function; it's not a reason to avoid including a linear-time function to remove an element at a given index of an array.
Abstractions are pretty and distracting but they are not why we write code and each one has a cost, which is often not apparent when introduced.
That’s not to say Go is perfect, there are a few little abstractions it would IMO be improved by having and the slice handling in particular could be more elegant and based on extending slice types or a slices package rather than built in generic functions.
As for a complicated for loop instead of the functional equivalent: I too am a fan of functional patterns in this case, but the for loop equivalent in my opinion is just as readable in 99% of cases. A little more verbose, that's all. Matter of taste.
If code breaks because list is now a hashmap, that seems like an anti-feature.
Can you find/quote where that principle comes from? I'm genuinely curious.
A range vs a series of filtering operations is an interesting question in terms of which is easiest to write or, crucially, for a beginner to understand after writing - not convinced foldl is easy for beginners. If you like abstractions like that, Go will be abhorrent to you, and that’s ok.
It is easy to build your own filter on a specific type, I’ve only done it a couple of times, it is literally no more than a for loop/range. Where I have written extensions and would appreciate helpers in the std lib is things like lists of ints and strings - contains, filter and friends would be welcome there in the stdlib (I use my own at present).
For filter etc I think I’d use them but am not convinced they would change the code much - the complexity is in what you do to filter not the filtering operation itself which probably adds about 3 lines and is very simple (set up new list, add to list in range, return list). For example in existing code I have lots of operations on lists of items which sit behind a function and for hardly any of them would I delete the function and just use filter in place at the call site, because I have the function to hide the complexity of the filtering itself (all those if conditions), which would not go away. I wouldn’t even bother rewriting the range to use filter because it’s not much clearer.
Very well said. If only more developers would understand this.
Yes I know, creating interfaces, inheriting everything from the void, adding as large amount of layers to create the beautifully constructed reusable structure is a nice drive but it might happen no one will reuse it as doesn't want to dive itself trough infinite level lasagna with rolling ravioli around it (and - thanks god, go doesn't have try/catch - throwing exceptions trough all the layers to force you to go down the guts of the construct to figure out what it means). Or, as it often happens, will be forced to reuse it, complicating his life and is code.
I do understand that inheritance, even operator overloading has its meaning and is extremely useful. But it has another side - everybody are overdoing it as "might come handy later" and the code becomes a case for "How to write unmaintainable code"[2].
When I am coding I am not doing it for philosophical reasons and go has until now succeeding being a very helpful tool without much of "meaning of life" complications. And i would love to see it stay that way.
If you are forcing me to read the documentation / code (presumably I know what I am trying to solve) to be able to use the "beautiful oo construct" and forcing you to read your beautiful design, you have failed making it and I have seen it in java everywhere. I just hope the same people making everything complicated more than it need to be wont skip from java[1] train to go train. I really don't want them anywhere close.
[1]https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpris...
[2]https://github.com/Droogans/unmaintainable-code (and 20 others)
Abstractions are a great idea, and Go has plenty of these (io.Writer is ubiquitous), but most business logic is dead boring and doesn’t need it.
Erlang has had these "popular patterns" for decades. And all languages that ignore them, making devs reimplement them, poorly, with third-party libs and ad-hoc solutions.
Most all of them can be implemented as single lines of code in Python.
I’m sure there were a lot of assembly programs that used the “call stack pattern”. I’m sure there are a lot of C programs that abuse struct packing to do inheritance (the “class pattern”, sometimes with crappy vtables) or the preprocessor to do “templates”. And even in Python, you’ve got to use the visitor pattern due to single dispatch.
[1] https://blog.golang.org/pipelines
It is a very long doc, but that also shows that concurrency has so many patterns one might like.
My own pattern is typically
1. Decide level of parallelism ahead of time and start workers (that many `go X()` invocations 2. Setup sync.Waitgroup for the same count 3. Create two channels, one for each direction. 4. Job itself needs some sort of struct to hold details
Most of my jobs don't support mid-work cancelation, so I don't bother with anything else.
It also uses context (useful for long running, concurrent jobs) and handles mid-work cancellation
Another example of this is how HTTP middlewares chain together, see for example all the middlewares in https://github.com/gorilla/handlers. All of these exhibit one particular quality of idiomatic Go code: a preference for composition over inheritance.
Another quality of idiomatic Go code is that concurrent algorithms prefer channels over locking mechanisms (unless the performance penalty of using channels is too severe). I don't have immediate examples coming to mind on this one though, since the use of channels and mutexes tends to be quite intertwined with the algorithm in question.
> Registry: Keep track of all subclasses of a given class
Go does not have classes.
writing generic functions is difficult, so it's nice if a language allows people to do so, otherwise you get N inefficient and/or buggy reimplementations of the function in every project needing it. (not sure if that is your point)
I was never able to understand what happens, when I looked at a particular snippet of Ruby code, if it was not me who wrote it. With Go, understanding others people code is a trivial task.
list.delete(x)
You literally can't know what's going on under the hood without popping it and looking for yourself.
Ruby's infatuation with clever magic code is what turned me off it years ago. You can get up to 80% in 20% of the time compared to other languages, but then you spend the 80% of time you have left fighting against the magic to get the last 20% done properly. There's way too much stuff You Just Need To Know.
That said, I agree Go could use a bit for ergonomic and handy methods, while still remaining efficient.
The example on Concurrency also has a different answer. Go gives you all the tools, but there are many different ways their problem can be solved. By explicitly avoiding a "join" method and having any default 'channels', Go makes all these possible. What is missing is some of the popular patterns that emerged in the last few years need to make it to into stdlib or some cookbooks.
1. If you want a worker model, I would start n=3 go-routines and they all receive from a single channel. They don't need to much around with a channel of buffer 3, as in the example.
2. If the workers already return data from a compute, the read from driver serves as the wait.
3. In other cases, there is sync.Waitgroup available to synchronize completion status.
4. End of work from the driver can be indicated via a channel close. Closed channels can still be read from until they are empty and the reader can even detect end-of-channel.
Designing concurrent system is a bit complicated. Some tutorials do make it sound like a `go` keyword is all you need. All of these can fixed by improving std-lib or cookbooks.