Hacker News Reader

Comment by alok-g | Hacker News Reader

>> No built-in type for sets (have to use maps and test for existence)

Is there any particular reason for this? Sets are so fundamental to mathematics and beyond that I am concerned right away about this. Sure you could use a map as a replacement, but what happens to "user experience"?

I do not get this for other languages as well. Data structures that are present in nearly all computer science books are often not built into the language or standard libraries, like trees, graphs. Reasoning given is that some other data structure could serve as a replacement (never mind that the programmer's intentions are not directly reflected in the code anymore), or because it is considered too removed from practical usage, or because some third-party library includes it. I do not buy any of these arguments.

View on HN

Every possible way to represent a set is a very thin wrapper around an existing data structure that is commonly implemented. There isn't a generally applicable way to represent a set. All sets are simply existing structures (BitVectors, Linked Lists, BST, or HashTables) with functions like Union and Intersection being tacked on and all have very different performance considerations.

Basically there really isn't a general purpose way to make a set and it’s not a fundamental component of programming, it is a modified HashTables or what ever. So I argue sets don’t actually exist in CS because you can’t represent one as it exists mathematically. You are simply tacking union and intersect to an existing data structure.

But if you do use a map as a wrapper, use map[keytype]struct{} . That way the values don't need any memory at all, struct{} is for free.

This would make sense for the case of a set. But does then Go provide (or intend to provide) these other data structures ("BitVectors, Linked Lists, BST, or HashTables")? Does it provide a sorted linked list?

A bitvector: []bool

Most of the time, you would use map[key]value rather than your own hash table or BST.

If you need an implicit linked list, there is one in the standard library: http://golang.org/pkg/container/list/

Yes, I noted that list container. If I need a sorted list, do I need to do that myself (which is OK though not ideal)? Or again there is some other container that can work possibly with a wrapper around it to emulate a sorted linked list?

I think the thing to do is just to write a function to keep stepping through the list until you find the right place to insert, and then just use container/list.

Sorry to be "that guy" who questions the question, but sorted lists aren't really a great data structure. As you probably already know, insertion is O(N), where N is the total number of elements in the list. It might be better just to use the GoLRB library, which provides some always-sorted tree structures.

You are right. I had a very specific case where I needed a sorted list. I do not recall why anymore.

The real reason is almost always "We didn't feel like it. So =P"

In Java, sets are merely wrappers around a map that maps to a dummy. I guess Go just left off the wrapper.

CPython's sets are implemented the same way.

A wrapper is totally fine really, actually better in some cases (see later). It still allows the programmer to map his intentions directly to the code, and make that intention directly visible to the reader. This adds to the "user experience" for the programmers.

Agreed that such wrappers are then easily built by the programmer himself. But then comes the added pain of including those definitions in everywhere within a project and in-between projects. They become one more dependency to handle.

Then come these wrappers or even whole data structures from third-party libraries. Nearly in every case I see, there is some impedance matching issue with some other libraries, requiring glue-logic to convert from one format to another. [Edit: Plus the added licensing/cost issues for those libraries.]

If a set is just a wrapper around some more generic data structure, it is OK to implement it like that in the library to avoid duplication of code in that library. However, by not making that wrapper, the system is resulting in much more amount of duplicated code in the user space and now with the mentioned impedance mismatch or with weak mapping of programmer's intentions to the code.

To be fair, Go includes a heap, list, and "ring" (circular doubly-linked list).

I agree that Go should include a Set type modeled after its List. Sets are simple and there's really just one way to implement them. My own is less than 40 lines; a simple set of tests are about 60 lines.

For trees, graphs, etc. I do think it is fair to establish these as the domain of the community. These are more complex, and there is more variety.

A map is a set. In a map, the key and value can be different things. In a set, they are the same. That's the only difference. They are both associative containers.

So what? Got to start isolating interface from the implementation. That implementation inside has overlaps does not mean the interface should be compromised. The latter needs to be designed according to the common needs of the user (here, programmers) rather than the implementation alone. Think "user experience" people!

You asked why they would do this. I answered your question. Maps are sets. And by implementing map, you can use it as a map or a set. Perhaps you're not looking for an answer to your question?

Say I implement log, but not log2. If you understand what log is and how to use it, you have log2. If you don't understand this, you ask why log2 is not provided.

I think I do understand what you are saying. But then, by the same token, so many things are not needed in a programming language. C++ for example has often being criticized for not having a power operator (a^b). Why not just work with a Turing machine (simulated on a computer), then you have everything.

It is not just about having it or not having it. It is also about user experience. Why should I write log(x)/log(2) assuming that is a commonly used operation such that the library could have provided me with simply log2(x)?

Just yesterday there was an user experience related article on confirmation vs. undo. The message was that if most of the users are likely to take the action, then undo is better than confirmation, and if most of the users are unlikely to take the action, then a confirmation is better.

While it is bad to provide every option to the user, it is also just as bad to miss the options that the users commonly use.

The real question then is if a set is commonly required or not. I believe it is used often enough.

It's like some people don't understand that an API is an "interface" and simplifying that interface is a boon to productivity, readability, DRYness, etc. All your points are spot on and its absurd that some people don't get that in this day and age.

"Abstractions are useless, lets all just program with cmp and jmp statements"--seriously folks, have we not learned anything?

Indeed.

What I hate is that even after having a good understanding of software development and computer science fundamentals, and having a good picture of the solution to a given problem, I still cannot today program without having to perform multiple Google searches, reading Stack Overflow messages, etc. to deal with what should be trivial stuff.

Just for example, if I were to need a set, I would search for "set" in Go documentation. If the set itself is not included, on the very least the documentation should talk about what should I do instead. But they won't even have that in there. Result: Few more Google searches.

Reply on news.ycombinator.com