What you see in functional languages such as Haskell is that lists are not mutable, so *behind the scenes*, they are treated more like pipes anyway, a way to get data items from one place to another, and can in fact be implemented as flat vectors providing the compiler can see enough about what's going on and predict the length requirement.

When you make the lists mutable, you're forcing the compiler to implement them in a certain way at runtime.  I'm not arguing that lists are not necessary;  in fact the opposite, as they have quite different complexity than flat vectors, which dramatically changes performance once they grow to a given large size.  With small lists, it really doesn't matter if you use a vector instead, you won't notice the difference until you start dealing with thousands of objects or more.

A sorted structure is in D already, it's an associative array... if all you want is to sort the objects, use the object itself as a key and void as the associated type, like   void[MyKeyType]  .   To be honest I am not sure that will compile, but it should.

A set is in D already, it's an associative array of bit.

There's a big difference between "feature X should be in D" and "feature X should be in the D language".  All this stuff could in fact go into the D standard runtime library, if template syntax wasn't so ugly.  Putting them in the language itself provides some convenient syntax sugar, but I'd rather a way be found to make templates less ugly.  Ok, it's not so bad anymore, just a single set of parens and a bang character...  now if we could just get rid of the bang.  ;)

Sean

Matthias Becker wrote:
|| never ever used linked lists myself yet..
|
| Never? Interssting.
|
|| on the other side, there is more reason for a map-implementation to
|| get into the language as a linked list. why? because linked lists
|| and dynamic arrays have the same features (not in performance, but
|| they are both essencially dynamic arrays..).
|| maps are something else. they are a key-value-container, and due
|| that often needed in situations an array itself doesn't work
|| anymore..
|
| But what about sets? Why isn't there a set in the language? What
| about sorted structures (trees)?
|
|
|| linked list doesn't give you anything really.. there was, once, a
|| proposed way, sort of this:
|| type[^] will be the same as list!(type)..
||
|| just as type[] will stay vector!(type)
||
|
| Well, if implemented right, they can give you a lot. Have you ever
| used a functional lanugage like Haskell or something? Imagine you
| want a list of all Elements smaller than a threshold. Using linked
| lists that could be nicly written as:
|
| Type[^] filter (Type[^] list, Type threshold)
| {
| if (list.head < threshold)
| return new Type[^](list.head, filter(list.tail, threshold));
| else
| return filter(list.tail, threshold);
| }
|
|
| As allways: Using some helper functions you can do the same with
| dynamic arrays as convenient (but slower).

void[type] works.

at least, it worked last time i've used it..

i think..

it's late:D

"Sean L. Palmer" <palmer.sean@verizon.net> schrieb im Newsbeitrag news:bvjmn2$noo$1@digitaldaemon.com...
> What you see in functional languages such as Haskell is that lists are not mutable, so *behind the scenes*, they are treated more like pipes anyway,
a
> way to get data items from one place to another, and can in fact be implemented as flat vectors providing the compiler can see enough about what's going on and predict the length requirement.
>
> When you make the lists mutable, you're forcing the compiler to implement them in a certain way at runtime.  I'm not arguing that lists are not necessary;  in fact the opposite, as they have quite different complexity than flat vectors, which dramatically changes performance once they grow
to
> a given large size.  With small lists, it really doesn't matter if you use
a
> vector instead, you won't notice the difference until you start dealing
with
> thousands of objects or more.
>
> A sorted structure is in D already, it's an associative array... if all
you
> want is to sort the objects, use the object itself as a key and void as
the
> associated type, like   void[MyKeyType]  .   To be honest I am not sure
that
> will compile, but it should.
>
> A set is in D already, it's an associative array of bit.
>
> There's a big difference between "feature X should be in D" and "feature X should be in the D language".  All this stuff could in fact go into the D standard runtime library, if template syntax wasn't so ugly.  Putting them in the language itself provides some convenient syntax sugar, but I'd
rather
> a way be found to make templates less ugly.  Ok, it's not so bad anymore, just a single set of parens and a bang character...  now if we could just get rid of the bang.  ;)
>
> Sean
>
> Matthias Becker wrote:
> || never ever used linked lists myself yet..
> |
> | Never? Interssting.
> |
> || on the other side, there is more reason for a map-implementation to
> || get into the language as a linked list. why? because linked lists
> || and dynamic arrays have the same features (not in performance, but
> || they are both essencially dynamic arrays..).
> || maps are something else. they are a key-value-container, and due
> || that often needed in situations an array itself doesn't work
> || anymore..
> |
> | But what about sets? Why isn't there a set in the language? What
> | about sorted structures (trees)?
> |
> |
> || linked list doesn't give you anything really.. there was, once, a
> || proposed way, sort of this:
> || type[^] will be the same as list!(type)..
> ||
> || just as type[] will stay vector!(type)
> ||
> |
> | Well, if implemented right, they can give you a lot. Have you ever
> | used a functional lanugage like Haskell or something? Imagine you
> | want a list of all Elements smaller than a threshold. Using linked
> | lists that could be nicly written as:
> |
> | Type[^] filter (Type[^] list, Type threshold)
> | {
> | if (list.head < threshold)
> | return new Type[^](list.head, filter(list.tail, threshold));
> | else
> | return filter(list.tail, threshold);
> | }
> |
> |
> | As allways: Using some helper functions you can do the same with
> | dynamic arrays as convenient (but slower).
>
>

"Sean L. Palmer" <palmer.sean@verizon.net> wrote in message news:bvjmn2$noo$1@digitaldaemon.com...
> What you see in functional languages such as Haskell is that lists are not mutable, so *behind the scenes*, they are treated more like pipes anyway,
a
> way to get data items from one place to another, and can in fact be implemented as flat vectors providing the compiler can see enough about what's going on and predict the length requirement.
>
> When you make the lists mutable, you're forcing the compiler to implement them in a certain way at runtime.  I'm not arguing that lists are not necessary;  in fact the opposite, as they have quite different complexity than flat vectors, which dramatically changes performance once they grow
to
> a given large size.  With small lists, it really doesn't matter if you use
a
> vector instead, you won't notice the difference until you start dealing
with
> thousands of objects or more.
>
> A sorted structure is in D already, it's an associative array... if all
you
> want is to sort the objects, use the object itself as a key and void as
the
> associated type, like   void[MyKeyType]  .   To be honest I am not sure
that
> will compile, but it should.

That's a bloody good idea, although I'm not sure we've got the syntax to test for existence yet. Checking docs now ...

...


The only properties are

      size
      length
      keys
      values
      rehash


so there'd need to be an "exists()" method to support void values

>
> A set is in D already, it's an associative array of bit.
>
> There's a big difference between "feature X should be in D" and "feature X should be in the D language".  All this stuff could in fact go into the D standard runtime library, if template syntax wasn't so ugly.  Putting them in the language itself provides some convenient syntax sugar, but I'd
rather
> a way be found to make templates less ugly.  Ok, it's not so bad anymore, just a single set of parens and a bang character...  now if we could just get rid of the bang.  ;)
>
> Sean
>
> Matthias Becker wrote:
> || never ever used linked lists myself yet..
> |
> | Never? Interssting.
> |
> || on the other side, there is more reason for a map-implementation to
> || get into the language as a linked list. why? because linked lists
> || and dynamic arrays have the same features (not in performance, but
> || they are both essencially dynamic arrays..).
> || maps are something else. they are a key-value-container, and due
> || that often needed in situations an array itself doesn't work
> || anymore..
> |
> | But what about sets? Why isn't there a set in the language? What
> | about sorted structures (trees)?
> |
> |
> || linked list doesn't give you anything really.. there was, once, a
> || proposed way, sort of this:
> || type[^] will be the same as list!(type)..
> ||
> || just as type[] will stay vector!(type)
> ||
> |
> | Well, if implemented right, they can give you a lot. Have you ever
> | used a functional lanugage like Haskell or something? Imagine you
> | want a list of all Elements smaller than a threshold. Using linked
> | lists that could be nicly written as:
> |
> | Type[^] filter (Type[^] list, Type threshold)
> | {
> | if (list.head < threshold)
> | return new Type[^](list.head, filter(list.tail, threshold));
> | else
> | return filter(list.tail, threshold);
> | }
> |
> |
> | As allways: Using some helper functions you can do the same with
> | dynamic arrays as convenient (but slower).
>
>

Matthew wrote:
>> "Sean L. Palmer" <palmer.sean@verizon.net> wrote in message news:bvjmn2$noo$1@digitaldaemon.com...
>>> A sorted structure is in D already, it's an associative array... if all you want is to sort the objects, use the object itself as a key and void as the associated type, like   void[MyKeyType]  .   To be honest I am not sure that will compile, but it should.
>>
>> That's a bloody good idea, although I'm not sure we've got the syntax to test for existence yet. Checking docs now ...
>>
>> ...
>>
>>
>> The only properties are
>>
>>       size
>>       length
>>       keys
>>       values
>>       rehash
>>
>>
>> so there'd need to be an "exists()" method to support void values
>>

if (someKey in hash.keys) { ... }

I believe that works.

-----------------------
Carlos Santander Bernal

"Carlos Santander B." <carlos8294@msn.com> wrote in message news:bvjpu4$tff$1@digitaldaemon.com...
> Matthew wrote:
> >> "Sean L. Palmer" <palmer.sean@verizon.net> wrote in message news:bvjmn2$noo$1@digitaldaemon.com...
> >>> A sorted structure is in D already, it's an associative array... if all you want is to sort the objects, use the object itself as a key and void as the associated type, like   void[MyKeyType]  .   To be honest I am not sure that will compile, but it should.
> >>
> >> That's a bloody good idea, although I'm not sure we've got the syntax to test for existence yet. Checking docs now ...
> >>
> >> ...
> >>
> >>
> >> The only properties are
> >>
> >>       size
> >>       length
> >>       keys
> >>       values
> >>       rehash
> >>
> >>
> >> so there'd need to be an "exists()" method to support void values
> >>
>
> if (someKey in hash.keys) { ... }
>
> I believe that works.
>
> -----------------------
> Carlos Santander Bernal

<blushes>Of course</blushes>

Thanks

Just realized I am wrong.  A set is more like an associative array of void, also.

Sean

Sean L. Palmer wrote:
| A set is in D already, it's an associative array of bit.

Sean L. Palmer wrote:

>Just realized I am wrong.  A set is more like an associative array of void,
>also.
>
>Sean
>
>Sean L. Palmer wrote:
>| A set is in D already, it's an associative array of bit.
>
>
>  
>
If it's a set of numbers (within a reasonable range) you can simply use an array of bits.

ie
bit [] set;

-- 
-Anderson: http://badmama.com.au/~anderson/

That's a Pascal-style set, and it doesn't scale well.  It's more like an automated flags DWORD than a real set.  Sure, if the set domain is known at compile time it could be implemented as such.

Sean

J Anderson wrote:
| Sean L. Palmer wrote:
|
|| Just realized I am wrong.  A set is more like an associative array
|| of void, also.
||
|| Sean
||
|| Sean L. Palmer wrote:
||| A set is in D already, it's an associative array of bit.
||
||
||
||
| If it's a set of numbers (within a reasonable range) you can simply
| use an array of bits.
|
| ie
| bit [] set;

Matthew wrote:
> "Carlos Santander B." <carlos8294@msn.com> wrote in message news:bvjpu4$tff$1@digitaldaemon.com...
>>
>> if (someKey in hash.keys) { ... }
>>
>> I believe that works.
>>
>> -----------------------
>> Carlos Santander Bernal
>
> <blushes>Of course</blushes>
>
> Thanks

That was wrong too. It's only
        someKey in hash

-----------------------
Carlos Santander Bernal