View mode: basic / threaded / horizontal-split · Log in · Help
May 05, 2012
[Feature Request] Adding to D lang "set" built-in
Dear, i hope i will got some answer from druntime/phobos dev .
A set is an array of unique element:
>>> set( 1, 5, 7, 1, 7)
give this array => [1, 5, 7]

Currently in D the hack it is to use an associative array with any
value.
byte[size_t] a = [ 1:0, 5:0, 7:0, 1:0, 7:0 ];

then it is easy to have a set in D just add a syntax or a built-in where
use associative array without using value.

I hope really this little feature and seem really easy to add


thanks a lot for your great works
May 05, 2012
Re: [Feature Request] Adding to D lang "set" built-in
I think a much more realistic suggestion would be to add it to phobos
as a struct, which wraps this no-value AA solution.

On Sat, May 5, 2012 at 9:14 PM, bioinfornatics
<bioinfornatics@fedoraproject.org> wrote:
> Dear, i hope i will got some answer from druntime/phobos dev .
> A set is an array of unique element:
>>>> set( 1, 5, 7, 1, 7)
> give this array => [1, 5, 7]
>
> Currently in D the hack it is to use an associative array with any
> value.
> byte[size_t] a = [ 1:0, 5:0, 7:0, 1:0, 7:0 ];
>
> then it is easy to have a set in D just add a syntax or a built-in where
> use associative array without using value.
>
> I hope really this little feature and seem really easy to add
>
>
> thanks a lot for your great works
>



-- 
Bye,
Gor Gyolchanyan.
May 05, 2012
Re: [Feature Request] Adding to D lang "set" built-in
There's a few ways to implement your own Sets right now, if 
needed. You found one way (using the built in AAs), but that's 
not all.

* You could use Array!bool (which efficiently stores bools) to 
store whether integers are in or out of your set.
* You can use std.container's redBlackTree to make a set which 
would work better if your items are objects or you're dealing 
with a sparse array.

There's probably a few other extremely simple methods, but those 
are the two I had on the top of my head. I'm not really sure 
having a particular "Set" in the library would be all that 
useful. Generally, if I want a set, I have a particular idea of 
how one should be implemented for my particular data.
May 06, 2012
Re: [Feature Request] Adding to D lang "set" built-in
On Sat, May 05, 2012 at 07:14:27PM +0200, bioinfornatics wrote:
> Dear, i hope i will got some answer from druntime/phobos dev .
> A set is an array of unique element:
> >>> set( 1, 5, 7, 1, 7)
> give this array => [1, 5, 7]
> 
> Currently in D the hack it is to use an associative array with any
> value.
> byte[size_t] a = [ 1:0, 5:0, 7:0, 1:0, 7:0 ];
> 
> then it is easy to have a set in D just add a syntax or a built-in where
> use associative array without using value.
> 
> I hope really this little feature and seem really easy to add
[...]

It's not too hard to implement something like this yourself. One of the
first projects I did when I started learning D was to implement an
integer set (basically a bit array). It supports full set operations,
like union, intersection, difference, optimized filling with first n
numbers, foreach, etc.. Some of the operations use bit-twiddling tricks
to maximize performance.

The only flaw is that it's essentially just a bit array, so it only
works well for sets whose elements are relatively small numbers. If you
want sparse sets, you may be better off adapting D's AA implementation
to have an AA that consists of just keys. Basically, you still have the
hash table and buckets, just without the value field in each slot. (I
wonder if it's possible for the new AA implementation to support this by
specifying void as the value type.)


T

-- 
Klein bottle for rent ... inquire within. -- Stephen Mulraney
May 06, 2012
Re: [Feature Request] Adding to D lang "set" built-in
On Sunday, 6 May 2012 at 22:10:03 UTC, H. S. Teoh wrote:
> slot. (I
> wonder if it's possible for the new AA implementation to 
> support this by
> specifying void as the value type.)

That would actually be very nice if it were the case.
May 06, 2012
Re: [Feature Request] Adding to D lang "set" built-in
On 5/7/12, Andrej Mitrovic <andrej.mitrovich@gmail.com> wrote:
> just write an
> some

Beautiful way to start a sentence. :P
May 07, 2012
Re: [Feature Request] Adding to D lang "set" built-in
On Mon, 2012-05-07 at 00:42 +0200, Andrej Mitrovic wrote:
> On 5/7/12, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:
> > you may be better off adapting D's AA implementation
> > to have an AA that consists of just keys.
> 
> Yeah I do that in my code right now. It's pretty easy, just write an
> some opApply/opBinary functions, add to!string(innerhash.keys) for
> good measure and you're set (heh, set).

Any language with which the programmer has to develop their own set
implementation is sadly lacking.

It is true that set can be implemented using a map, but this should be
seen as implementation detail, not as programmer level tool. It
indicates that set should exist where set does. So for C++ it is in the
standard library, for Python it is a built-in (*).

The conclusion for D is straightforward. Which issue to I go to to vote?


(*) Although set was a second class citizen in Python 2, it is a first
class citizen in Python 3. There are even set comprehensions, just as
there are list comprehensions and dictionary comprehensions.  I just
love the influence of functional programming: be data evolution focused,
not control flow focused.

-- 
Russel.
=============================================================================
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder@ekiga.net
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel@winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
May 07, 2012
Re: [Feature Request] Adding to D lang "set" built-in
On Monday, May 07, 2012 06:49:00 Russel Winder wrote:
> On Mon, 2012-05-07 at 00:42 +0200, Andrej Mitrovic wrote:
> > On 5/7/12, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:
> > > you may be better off adapting D's AA implementation
> > > to have an AA that consists of just keys.
> > 
> > Yeah I do that in my code right now. It's pretty easy, just write an
> > some opApply/opBinary functions, add to!string(innerhash.keys) for
> > good measure and you're set (heh, set).
> 
> Any language with which the programmer has to develop their own set
> implementation is sadly lacking.
> 
> It is true that set can be implemented using a map, but this should be
> seen as implementation detail, not as programmer level tool. It
> indicates that set should exist where set does. So for C++ it is in the
> standard library, for Python it is a built-in (*).
> 
> The conclusion for D is straightforward. Which issue to I go to to vote?

We have RedBlackTree, so we have a set already. What we don't have is a 
HashSet. However, once the custom allocator stuff has been sorted out, I'd 
fully expect to have one in std.container along with a variety of other 
container types which we really should have but don't.

- Jonathan M Davis
May 07, 2012
Re: [Feature Request] Adding to D lang "set" built-in
On Sun, 2012-05-06 at 22:53 -0700, Jonathan M Davis wrote:
[...]
> We have RedBlackTree, so we have a set already. What we don't have is a 
> HashSet. However, once the custom allocator stuff has been sorted out, I'd 
> fully expect to have one in std.container along with a variety of other 
> container types which we really should have but don't.

I certainly went immediately to std.container to look for the work set,
map, etc. in some guise. I only posted after finding nothing
appropriate.

I guess the issue here is that maps (aka dictionaries, aka associative
arrays) are in the D language core (as in Python) rather than being is
the library (as in C++). This indicates set should be in the core rather
than in the library.

I wonder if the tradition of exposing HashMap and TreeMap was a
disservice by C++ and Java? Map and Set are programmer level concepts.
Where there are algorithmic issues that require knowing about trees or
has tables then the programmer is not working at the map or set level.

And the programmer has no control over how D's associative arrays work.

And let's not mention Java's LinkedHashMap.  :-)

-- 
Russel.
=============================================================================
Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder@ekiga.net
41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel@winder.org.uk
London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder
May 07, 2012
Re: [Feature Request] Adding to D lang "set" built-in
On Monday, May 07, 2012 07:05:28 Russel Winder wrote:
> I wonder if the tradition of exposing HashMap and TreeMap was a
> disservice by C++ and Java? Map and Set are programmer level concepts.
> Where there are algorithmic issues that require knowing about trees or
> has tables then the programmer is not working at the map or set level.

???

There are multiple ways to implement a set or a map. If a programmer knows 
their data structures (as one would hope that they would), then they know the 
difference between a hash set and a tree set (or hash map and tree map), and 
they'll pick the one that's most appropriate for what they're doing. And 
because the containers are very similar, it should be quite possible in many 
cases to replace one with the other quite easily - especially if you're using 
templates. That's one of the reasons that Java has the Set interface with 
HashSet and TreeSet implenting it.

std.container is designed with the idea that containers will be named after 
their data structures and _not_ what they're used for. Programmers can then 
select the data structure that best serves their purposes. And I'd be worried 
about any professional programmer who didn't know that you can use a red-black 
tree as a set or a map.

> And the programmer has no control over how D's associative arrays work.

It's clearly a hash map. If they want a tree map, then we have RedBlackTree 
(though we should probably provide a wrapper that makes it easier to use 
RedBlackTree as a map, since it's a bit unwieldy to do that at the moment). I 
don't see the problem.

- Jonathan M Davis
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home