6 ms·

>> 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 bey

by alok-g 13y ago

>> 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.

gamegoblin 13y ago
In Java, sets are merely wrappers around a map that maps to a dummy. I guess Go just left off the wrapper.
- guelo 13y ago
  CPython's sets are implemented the same way.
- alok-g 13y ago
  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.
Zergy 13y ago
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.
- arnehormann 13y ago
  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.
- alok-g 13y ago
  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?
  - cmccabe 13y ago
    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/ http://golang.org/pkg/container/list/
    - alok-g 13y ago
      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?
zhemao 13y ago
The real reason is almost always "We didn't feel like it. So =P"
deleted 13y ago
[deleted]
16s 13y ago
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.
- alok-g 13y ago
  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!
  - 16s 13y ago
    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.
    - alok-g 13y ago
      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.
mratzloff 13y ago
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.

by alok-g 13y ago

gamegoblin 13y ago

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

guelo 13y ago
CPython's sets are implemented the same way.
alok-g 13y ago
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.

Zergy 13y ago

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.

arnehormann 13y ago
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.
alok-g 13y ago
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?
- cmccabe 13y ago
  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/ http://golang.org/pkg/container/list/
  - alok-g 13y ago
    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?

zhemao 13y ago

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

deleted 13y ago

[deleted]

16s 13y ago

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.

alok-g 13y ago
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!
- 16s 13y ago
  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.
  - alok-g 13y ago
    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.

mratzloff 13y ago

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.