D has a built in hashed associative container, which is great.

I've noticed though it has no built-in "hashed container" for when you just need to store unique elements, but without any specific data associated (lists of names, for example).

Has anybody requested this before? Would there be any plans for it?

----
The current "workaround" is to just dummy it.
alias bool Dummy;
Dummy[string] names;
names["Paul"] = true; //Ew.

But it is not very obvious what is going on. I also tried "void"ing it, eg:
void[string] names;
But that doesn't work either: Error: can't have associative array of void.

----
What would you think of introducing a built-in hashed container, that contains only keys?

We could call them "HA" for Hashed Array, and declare them with this simple syntax:

[string] names;

he interface would be mostly the already existing functions of AA (".remove", "in", "rehash()"), plus ".insert" to insert a key.

Thoughts?

monarch_dodra:

> I've noticed though it has no built-in "hashed container" for when you just need to store unique elements, but without any specific data associated (lists of names, for example).

They are often named "hash sets". In Python this is a built-in type. But in D I think it's better to define such sets as a library template in a module to import. This is meant to be in Phobos.


> he interface would be mostly the already existing functions of AA (".remove", "in", "rehash()"), plus ".insert" to insert a key.

It also needs some other methods, see:
http://docs.python.org/2/library/sets.html

Bye,
bearophile

On 11/12/12, monarch_dodra <monarchdodra@gmail.com> wrote:
> I've noticed though it has no built-in "hashed container" for when you just need to store unique elements, but without any specific data associated (lists of names, for example).

You probably mean a Set? I think we could really use some syntax support for sets. Otherwise people use workarounds like "alias void[0][string] StringSet", and wrap such a type in a struct with operator overloads to emulate the built-in hash syntax.

Andrej Mitrovic:

> I think we could really use some syntax support for sets.<

I don't agree. I think in D there is no real need for built-in support for sets, despite built-ins are handy. It's better to leave the compiler changes to things that can't be implemented in library code, like a good syntax for tuple unpacking and other things.

I think the only feature you can't implement in D is "full" operator support for set comparisons, because currently D operator overloading doesn't allow you to define ">=" and ">" independently. But this is a minor limitation that doesn't justify built-in sets.

Bye,
bearophile

On Monday, 12 November 2012 at 14:50:48 UTC, bearophile wrote:
> monarch_dodra:
>
>> I've noticed though it has no built-in "hashed container" for when you just need to store unique elements, but without any specific data associated (lists of names, for example).
>
> They are often named "hash sets". In Python this is a built-in type. But in D I think it's better to define such sets as a library template in a module to import. This is meant to be in Phobos.
>
>
>> he interface would be mostly the already existing functions of AA (".remove", "in", "rehash()"), plus ".insert" to insert a key.
>
> It also needs some other methods, see:
> http://docs.python.org/2/library/sets.html
>
> Bye,
> bearophile

Well, I don't see why AA would be built-in, but not set.

In particular, more often than not, AAs are implemented in terms of set (and not the other way around) anyways, so if we take the time to implement AA, why not hashed sets?

The advantage of having it built-in would mean more convenient declaration syntax:
int[string] vs AA!(string, int) // string => int
[string] vs Set!(string) //set of string

But of course, a library solution would be good too.

Might even make it my next project and get started on it now :)

On Monday, 12 November 2012 at 14:53:19 UTC, Andrej Mitrovic wrote:
> On 11/12/12, monarch_dodra <monarchdodra@gmail.com> wrote:
>> I've noticed though it has no built-in "hashed container" for
>> when you just need to store unique elements, but without any
>> specific data associated (lists of names, for example).
>
> You probably mean a Set? I think we could really use some syntax
> support for sets. Otherwise people use workarounds like "alias
> void[0][string] StringSet", and wrap such a type in a struct with
> operator overloads to emulate the built-in hash syntax.

Well "set" is just a name by convention. In C++, set's complexity restrictions forces the binary tree implementation on it.

On 11/12/12, monarch_dodra <monarchdodra@gmail.com> wrote:
> But of course, a library solution would be good too.

dcollections has sets http://www.dsource.org/projects/dcollections (not sure if it still compiles though)

monarch_dodra:

> Well, I don't see why AA would be built-in, but not set.

It's generally wise to minimize the amount of stuff you put in the D front end or in the D runtime.


> so if we take the time to implement AA, why not hashed sets?
>
> The advantage of having it built-in would mean more convenient declaration syntax:
> int[string] vs AA!(string, int) // string => int
> [string] vs Set!(string) //set of string

The situation is not fully symmetrical: associative arrays fully defined in Phobos have bad literals.

Bye,
bearophile

On Monday, 12 November 2012 at 15:22:00 UTC, bearophile wrote:
> The situation is not fully symmetrical: associative arrays fully defined in Phobos have bad literals.

I apologize, I'm not sure what you mean.

On 11/12/2012 03:53 PM, Andrej Mitrovic wrote:
> You probably mean a Set? I think we could really use some syntax
> support for sets. Otherwise people use workarounds like "alias
> void[0][string] StringSet"

Can you give a bit more explanation of how that workaround would work?  I can't see how you would insert entries in that case ...

    StringSet s;

    s["one"] = .... ?