Comment by rdtsc | Hacker News Reader

Comment by rdtsc | Hacker News Reader

Parent Full thread

Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that.

But I think you probably meant having and using set operations effectively in day to day tasks, as in "make 2 sets and do a set different operation" instead of "do a for loop on first hash check if it is in the second, then put results in an accumulator.

Another thing is to think about set of sets. Can that be useful sometimes? Implementing that is slightly trickier. You'd need to be able to get a hash of a set. Python has frozenset https://docs.python.org/3/library/stdtypes.html#frozenset. I've used those on occasion.

Then of course there is Erlang sofs (sets of sets) module. Stumbled on it by accident. Oh my, it comes complete with an introduction to set theory and relational algebra:

http://erlang.org/doc/man/sofs.html

It just struck me as so out of place with the rest of the standard library modules. Would like to know its history

Yes, while a set can be derived or mimicked if you have a hashtable for example, I'm specifically referring to all the common set operations you'd typically want to have.

Using a map/hashtable as a set is just the tip of the iceberg.

In many cases you don't need a key and a value and you can get rid of a lot of loopy and complicated code if you had a simple set to utilize with its useful operations.

>"Though once you have hash/maps/dicts set are with reach by making sets from hashes were keys are the element and values are just true or 1 or something like that."

Can you elaborate on how you can derive a set from hashes by using values of True or 1? Might you have a link? Thanks.

> Can you elaborate on how you can derive a set from hashes by using values of True or 1? Might you have a link? Thanks.

Sure. Np!

I mean that a simplified set is just a hash where the elements of the set are keys of the hash table and the values can be anything. I used 1 or True as example.

As in adding an element would be:

   my_dict[element] = 1

Then membership check is:

   if element in my_dict

Then removal is deleting:

   del my_dict[element]

and so on.

In other words, the reason sets are sometimes not explicitly there is because they are easy to implement on top of existing data structures.

Basic operations like union, difference, intersection between two sets can be done with a few simple for loops.

But like I mentioned in other comment, there is one interesting aspect to set (and hashes) in that the element now have to be hash-able. That kind of depends how mutability and identity works in the particular language.

Thanks for the clear explanation, this makes total sense. Cheers.

Ruby's standard library does this. Here's the code: https://github.com/ruby/ruby/blob/trunk/lib/set.rb

Python essentially does this as well.

The idea is that an item is in the set if it's in the hash table. You can add, remove, or test for membership in constant average time.

Set operations still need to be built on top of this.

Reply on news.ycombinator.com