News for hackers. Stuff that matters.
Re:Rob Pike's Rules of Programming (1989) by seanmcdirmid on Saturday September 16, 2017 @03:13PM (#15266160)
If they don't need order, a hash set is indeed more simple conceptually.
Re:Rob Pike's Rules of Programming (1989) by Sniffnoy on Saturday September 16, 2017 @03:39PM (#15266305)
A set, the abstract interface, is simpler conceptually than a list. A hash set, the particular implementation of a set, is more complex.
Re:Rob Pike's Rules of Programming (1989) by tatterdemalion on Saturday September 16, 2017 @03:56PM (#15266416)
Fortunately there are many languages which will provide a generic abstraction for you, so you don't have to deal with any of the complexity of implementing a hash set and you can just treat it like a set.
Re:Rob Pike's Rules of Programming (1989) by jopsen on Saturday September 16, 2017 @04:08PM (#15266476)
Lots of code is written in C :)
Re:Rob Pike's Rules of Programming (1989) by tatterdemalion on Saturday September 16, 2017 @04:51PM (#15266682)
Or Go.
Re:Rob Pike's Rules of Programming (1989) by jzelinskie on Saturday September 16, 2017 @07:49PM (#15267411)
In Go, it's idiomatic to use map[T]struct{} for a HashSet. In fact, the compiler optimises struct{} so that it doesn't even allocate.
Re:Rob Pike's Rules of Programming (1989) by tatterdemalion on Sunday September 17, 2017 @01:20AM (#15268340)
This is also how HashSet is implemented in Rust (internally its a HashMap<T, ()>, and zero sized structs are optimized out just like Go).

But by providing a set type, Rust is able to provide for users various set operations which Go requires you to write by hand. It becomes hard to argue that a set is simpler than a slice when you have to write your own methods dealing with union, disjunction, intersection, difference, subsets/supersets, etc every time.

Re:Rob Pike's Rules of Programming (1989) by seanmcdirmid on Saturday September 16, 2017 @04:52PM (#15266696)
One could easily implement a hash set with an array, the reverse is not true at all. From the outside, arrays are extremely flexible, powerful, and complex constructs; a set, even a hash set, is not.

If it is easy to procure a set (as a hash set), then sets should be used when they could be used instead of arrays (unless there are performance concerns to using sets). In languages that do not include batteries (e.g. C), it makes sense to use an array simply because procuring a set isn't easy.

Re:Rob Pike's Rules of Programming (1989) by DamonHD on Saturday September 16, 2017 @04:55PM (#15266711)
I'm probably missing something, but eg awk implements its 'arrays' at least logically with something like a hash set, and indeed hash sets can be great for (say) sparse arrays.

Lots of low-level data structures can be implemented in terms of one another, and which makes sense depends on circumstance.

Re:Rob Pike's Rules of Programming (1989) by seanmcdirmid on Saturday September 16, 2017 @05:13PM (#15266791)
Low level doesn't mean simple. In this case, arrays provide a lot of flexibility with manual indexing. They are a low level hammer that can do anything.

Sets are much more restricted, they don't have manual indexing, they don't garaunteed iteration ordering without special semantics, they don't do as much as arrays even if they might be implemented with arrays.

Then why use an array when you only need a set and an array would be overkill?