www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Adding sets to the language.

reply "w0rp" <devw0rp gmail.com> writes:
Every now and then I want a set type, but I have to either use my 
own library for it, or use a commonly known associative array 
trick. I really think (unordered hash) sets should be part of the 
standard library. While I was working on something else, I 
thought of one way of adding them to the standard library, maybe 
in the sort of core place associative arrays live in.

Define the following alongside the associative arrays.

// An alias for spelling it out.
// I shall count down the seconds to someone saying,
// "This should be named HashSet instead."
private alias Set(V) = void[0][V];

// Allow for set.contains(value) returning a boolean.
// The parameter types here may differ.
 nogc  safe pure nothrow
private bool contains(T, U)(const(void[0][T]) set, auto ref 
const(U) value)
if(is(const(U) : const(T))) {
     return (value in set) !is null;
}

// Allow for adding values with set.add(value)
// I think I got the types right here.
 safe pure nothrow
private void add(T, U)(ref void[0][T] set, auto ref U value)
if(is(U : T)) {
     set[value] = (void[0]).init;
}

// Allow for using sets as output ranges.
alias put = add;

Now people who are writing void[0][T] themselves for sets, or who 
have their own aliases, can use the two new functions to make 
their code look a little nicer.

Now I'll get into a list of perhaps related desires and gripes.

1. When the value type is void[0], perhaps associative arrays 
could do something special, if they don't already.
2. I would like the compiler to output Set!T in error messages 
instead of void[0][T].
3. I'm using 2.066 still, and some things like byKey aren't  safe 
and so on. These things need to have attributes set. (As always, 
opApply probably lacks one of  nogc,  safe, pure, nothrow because 
of the delegate types.)
4. I couldn't get the sets to be recognised as an output range no 
matter what I hammered in for the 'put' function. I don't know 
what's going on there.
5. When I used my alias Set!T as the parameter types for the 
functions above instead of void[0][T], type deduction failed. 
This could be a problem.
6. The key types for associative arrays really ought to be 
required to be immutable with immutable(T)[] being allowed too. 
You can allow mutable lookups with a copy and so on, but that 
doesn't work, because changing the hash for the object will make 
the second lookup fail.
Mar 29 2015
next sibling parent "w0rp" <devw0rp gmail.com> writes:
The signatures only had 'private' in there because I copy and 
pasted them out of something I was working on. (Because they 
work.)
Mar 29 2015
prev sibling next sibling parent "w0rp" <devw0rp gmail.com> writes:
On Sunday, 29 March 2015 at 09:17:17 UTC, w0rp wrote:

 3. I'm using 2.066 still, and some things like byKey aren't 
  safe and so on. These things need to have attributes set. (As 
 always, opApply probably lacks one of  nogc,  safe, pure, 
 nothrow because of the delegate types.)


I also just realised that the ranges over the associative arrays 
are maybe  system because you can't guarantee that the 
associative array won't be modified while you're iterating over 
it.

I'll shut up now.
Mar 29 2015
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
w0rp:


 Every now and then I want a set type,


I think you can implement good enough sets in Phobos, do you 
agree?

But you can't do the same with tuples. So I prefer sets in Phobos 
and tuples in the language.

Bye,
bearophile
Mar 29 2015
parent reply "weaselcat" <weaselcat gmail.com> writes:
On Sunday, 29 March 2015 at 14:23:10 UTC, bearophile wrote:

 w0rp:


 Every now and then I want a set type,


 I think you can implement good enough sets in Phobos, do you 
 agree?

 But you can't do the same with tuples. So I prefer sets in 
 Phobos and tuples in the language.

 Bye,
 bearophile


+1 for tuples in language, it's one of the few things that would 
become far more useful as a core language feature.


Is std.container in need of more containers?
Mar 29 2015
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
On Sunday, 29 March 2015 at 19:32:48 UTC, weaselcat wrote:

 Is std.container in need of more containers?


These

https://github.com/economicmodeling/containers

have Phobos-compatible license (Boost) and, with some work, I 
guess some of them could be merge into std.container, in your 
case *hashset.d is what you're looking for.
Mar 29 2015
parent "weaselcat" <weaselcat gmail.com> writes:
On Sunday, 29 March 2015 at 19:39:36 UTC, Nordlöw wrote:

 On Sunday, 29 March 2015 at 19:32:48 UTC, weaselcat wrote:

 Is std.container in need of more containers?


 These

 https://github.com/economicmodeling/containers

 have Phobos-compatible license (Boost) and, with some work, I 
 guess some of them could be merge into std.container, in your 
 case *hashset.d is what you're looking for.


looks like they all rely on std.allocator which has been 
stagnating for a long time
Mar 29 2015