Steve Horne wrote:
> 
> But I still think there should be alternative containers in the
> library (assuming they're not there anyway and I've just missed them).
> I know the term 'perfect hash', but the term is precisely that - not
> 'perfect container'! There are things that hashtables can't do (or at
> least, can't do very efficiently for large datasets) like in-order
> iterating or picking out an ordered subrange.

Definitely.  I'm mostly supporting arrays at the moment because they're built-in, and I haven't seen a container library for D yet that I'm convinced is the perfect solution.  But eventually, I'd like to revert to an iterator sort of approach instead.  Oskar mentioned recently that we can sort of do that now by supporting anything with opIndex and a length property, but I'm not sure I see a tremendous value there over arrays--largely because I can't think of many objects I'd implement with these methods that I'd want to run algorithms on.


Sean

On Thu, 07 Sep 2006 11:19:12 -0400, nobody <nobody@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?

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

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.

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.

Mind you, I guess a complex list-type specification might have benefits along the lines of...

  list!(item-type, link-style, separate-iterators-flag, ...)

But templates can do that. And anyway, lists are naff! I like trees!

-- 
Remove 'wants' and 'nospam' from e-mail.

Steve Horne wrote:
> On Thu, 07 Sep 2006 11:19:12 -0400, nobody <nobody@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.

On Fri, 08 Sep 2006 09:48:36 -0400, nobody <nobody@mailinator.com> wrote:

>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.

Disagree. Accessing a list element requires a list position. That could be as simple as an iterator - a pointer, IOW. If I was going to subscript into a container, I probably wouldn't use a linked list.

>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

I've Lisped in a past life, though not much. I dunno, though. After all, it's a low level tool - not a high level container. When a tool can do anything, its not always clear what it's supposed to be doing, so you won't be told when you're doing it wrong.

But then, it is just a struct with two pointers.

-- 
Remove 'wants' and 'nospam' from e-mail.