Suggestion: dynamic array operations

[nobody]

Steve Horne wrote:
> On Thu, 07 Sep 2006 11:19:12 -0400, nobody <nobody at mailinator.com>
> wrote:
> 
>> So what sort of silly stuff would you write about possible benefits derived from 
>> having a list data structure built into the language?
> 

Thanks for taking the time to respond.

> There's already a built-in type for the links. It's called 'pointers'
> ;-)

A pointer is a pointer ;-)

Accessing a pointer to a value requires just the pointer. Accessing an array 
element requires a pointer and an offset. Accessing a list element requires a 
pointer and a depth.

> There's just too many ways to do a linked list. Singly linked. Doubly
> linked. Circular or with a clear start and end. Do you want separate
> whole-list and iterator classes, or do you want to package the two in
> a single class (as with a stack).
> 
> Bidirection lists implemented with a single link per item are fairly
> cool, even though the iterators are a bit of a pain - each link is the
> XOR of the previous and next item addresses, and the iterator needs
> two adjacent item addresses. Needs a custom allocator to get the
> benefit, but still good for listing very small items.
> 
> Picked it up from a website by an ex-Microsoft employee, IIRC. He used
> address differences for the links, but XOR is a tad easier IMO.

These are all great examples of how one might use a basic list structure. I had 
the Lisp cons cell in mind and was apparently expecting you to discover that via 
ESP -- another great feature D will probably never have. The cons cell as I was 
imagining it has room for two pointers. The first is usually known as the car of 
the list and the second is the cdr:

   http://en.wikipedia.org/wiki/Car_and_cdr

   Introduced in the Lisp programming language, car (IPA ['kar], just like the
   English word "car") and cdr (IPA ['k? d?r] or ['ku d?r]) are primitive
   operations upon linked lists composed of cons cells. A cons cell is composed
   of two pointers; the car operation extracts the first pointer, and the cdr
   operation extracts the second.

> A small set of built-in complex types is good, but libraries and
> templates exist for a reason. If a standard library list type gets
> really heavy use, it can always be absorbed into the language later.

The great thing about a cons cell is the cons cell alone is not any particular 
flavor of list or tree. You can build all sorts of interesting data types.