View mode: basic / threaded / horizontal-split · Log in · Help
November 12, 2012
hashed array?
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?
November 12, 2012
Re: hashed array?
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
November 12, 2012
Re: hashed array?
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.
November 12, 2012
Re: hashed array?
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
November 12, 2012
Re: hashed array?
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 :)
November 12, 2012
Re: hashed array?
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.
November 12, 2012
Re: hashed array?
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)
November 12, 2012
Re: hashed array?
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
November 12, 2012
Re: hashed array?
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.
November 12, 2012
Re: hashed array?
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"] = .... ?
« First   ‹ Prev
1 2 3 4
Top | Discussion index | About this forum | D home