I've been thinking lately that it would be good if we could declare
containers of unspecified type, and let the compiler choose the
implementation.  There are 3 major types of container that I can think
of:
    * Unsorted, unindexed (bag)
    * Sorted, unindexed (list)
    * Unsorted, indexed (map/hash)
I suppose you could have a sorted,indexed containter, but what would
that be?

My thought here is that each of those containers has a fair analogy in
the array syntax:
    * Sorted, unindexed: associative array
    * Unsorted, indexed: integer-indexed array
    * Unsorted, unindexed: integer-indexed array (no reason we CAN'T
have indexes...)

For most purposes, a container is just a container - the programmer doesn't really need to know how it is implemented.  So what if we thought of an array not as an array, but as a generic container declaration, which could be implemented as an array or as some other type?

Basically, the idea is that the compiler would look at the things that you do to the container, and choose an appropriate type.  If all you ever do is array.addTail and array.removeFront, then it will decide to implement your container as a linked list (or doubly-linked list, if that's appropriate).  If all you do is access by integer indexes, then it uses an array.  And so on.

Of course, performance-critical code would want to specify how the thing was implemented.  So you add an optional "as" clause to array declarations:

    int[char[]] myIntArray;    // compiler chooses container type
    int[char[]] as hash myHashTable;    // compiler obliged to use
"hash" as the container type

Then we would add a series of container-like properties to arrays:
    addTail - exactly equivalent to the ~ operator, but included to
match addFront,removeTail,removeFront
    addFront
    removeTail
    removeFront
    push - alias of addTail
    pop - alias of removeTail
    getTail - doesn't remove the object
    getFront - doesn't remove the object
    others?

Explicit container types could include:
    array (only valid if the index type is integers)
    hash
    list
    dlist
    tree
    avltree
    others?

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]

I agree. Walter mentioned something about datatype implementation taking a lot of time. But what do I know, perhaps these are a different type of datatype or parhaps it's worth it? If it was possible to program your own properties for arrays, cuppled with tempates, it may be possible to write your own (or standard libarary it). Parhaps there could be a class tempate that extends array types, allow you to program your own variants. Although I don't know how the syntax would look.

How about conversions between formats. ie you could covert a unsorted array time to sorted for a period of code and then convert it back (ie you don't care about maintaining the arrays in sorted format, although it's allright if it is). For example, in some cases there are parts in algorithms where you need to convert an unsorted array into a sorted hash (perhaps for a multiple binary search and remove) but because this operation is not used frequently it better to generally better keep an unsorted array. D has the .sort, but sometimes a data-struct is more adapt to certain tasks.

"Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:3D3BFC0F.50C9D499@deming-os.org...
> I've been thinking lately that it would be good if we could declare
> containers of unspecified type, and let the compiler choose the
> implementation.  There are 3 major types of container that I can think
> of:
>     * Unsorted, unindexed (bag)
>     * Sorted, unindexed (list)
>     * Unsorted, indexed (map/hash)
> I suppose you could have a sorted,indexed containter, but what would
> that be?
>
> My thought here is that each of those containers has a fair analogy in
> the array syntax:
>     * Sorted, unindexed: associative array
>     * Unsorted, indexed: integer-indexed array
>     * Unsorted, unindexed: integer-indexed array (no reason we CAN'T
> have indexes...)
>
> For most purposes, a container is just a container - the programmer doesn't really need to know how it is implemented.  So what if we thought of an array not as an array, but as a generic container declaration, which could be implemented as an array or as some other type?
>
> Basically, the idea is that the compiler would look at the things that you do to the container, and choose an appropriate type.  If all you ever do is array.addTail and array.removeFront, then it will decide to implement your container as a linked list (or doubly-linked list, if that's appropriate).  If all you do is access by integer indexes, then it uses an array.  And so on.
>
> Of course, performance-critical code would want to specify how the thing was implemented.  So you add an optional "as" clause to array declarations:
>
>     int[char[]] myIntArray;    // compiler chooses container type
>     int[char[]] as hash myHashTable;    // compiler obliged to use
> "hash" as the container type
>
> Then we would add a series of container-like properties to arrays:
>     addTail - exactly equivalent to the ~ operator, but included to
> match addFront,removeTail,removeFront
>     addFront
>     removeTail
>     removeFront
>     push - alias of addTail
>     pop - alias of removeTail
>     getTail - doesn't remove the object
>     getFront - doesn't remove the object
>     others?
>
> Explicit container types could include:
>     array (only valid if the index type is integers)
>     hash
>     list
>     dlist
>     tree
>     avltree
>     others?
>
> --
> The Villagers are Online! http://villagersonline.com
>
> .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
> .[ (a version.of(English).(precise.more)) is(possible) ]
> ?[ you want.to(help(develop(it))) ]
>
>

> > Then we would add a series of container-like properties to arrays:
> >     addTail - exactly equivalent to the ~ operator, but included to
> > match addFront,removeTail,removeFront
> >     addFront
> >     removeTail
> >     removeFront
> >     push - alias of addTail
> >     pop - alias of removeTail
> >     getTail - doesn't remove the object
> >     getFront - doesn't remove the object
> >     others?
If nothing else comes through from your idea, these properties (and some more) should of course be added to the built-in arrays. That seems easy enough.

"Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:3D3BFC0F.50C9D499@deming-os.org...
> I've been thinking lately that it would be good if we could declare
> containers of unspecified type, and let the compiler choose the
> implementation.  There are 3 major types of container that I can think
> of:
>     * Unsorted, unindexed (bag)
>     * Sorted, unindexed (list)
>     * Unsorted, indexed (map/hash)
> I suppose you could have a sorted,indexed containter, but what would
> that be?

Lists aren't necessarily sorted (though they do have a definite order.)
Bags are unordered; i.e. they don't guarantee order from iteration to
iteration.  While iterating over a bag, it's ordered, but only during that
iteration, and only if nobody adds or removes objects during that traversal.
You can do some interesting optimizations when order doesn't matter.  Delete
is swap with last, delete last.  Insert can always go at the end, or into an
empty slot if you have them.
Arrays are ordered and indexed (always by integer position in the array) but
generally unsorted.  Matrices are related to arrays.
Sets are indexed (probably sorted, but that's an implementation detail) and
the only real property is inclusion/exclusion (and iteration).  For integer
indices it's essentially a bit array.
Sparse arrays (save space at expense of access speed)
Maps and hashtables are like associative arrays; indexed on any type.  Maps
have ordering that makes sense (usually just what < provides);  the ordering
of hash tables is entirely dependent on choice of hash.
Stacks and queues are really basic containers too but can be easily
implemented atop arrays or lists.
Deques seem to be a list of small arrays; indexed (slow!) and ordered.
Trees of various forms, usually binary.
Graphs are similar to trees.

A sorted, indexed container is like a sorted array, conceptually.  A map could fall into this category.


> My thought here is that each of those containers has a fair analogy in
> the array syntax:
>     * Sorted, unindexed: associative array
>     * Unsorted, indexed: integer-indexed array
>     * Unsorted, unindexed: integer-indexed array (no reason we CAN'T
> have indexes...)

I'd like to think of an associative array like I'd think of a map: a (slow to index) sparse array that can be indexed by any type.

Yes, indexing is usually something one might be willing to give up in exchange for other optimizations.  Sometimes a list is the most natural type of container for a given data set.  Using an array where a list is needed can result in large algorithmic penalties (mainly for reallocations).

> For most purposes, a container is just a container - the programmer doesn't really need to know how it is implemented.  So what if we thought of an array not as an array, but as a generic container declaration, which could be implemented as an array or as some other type?

Because the programmer also needs control over what type the container is. At least the ability to hint to the compiler what kind of things are important (consistent total order, index speed, iteration speed, insertion/removal speed (at ends, or arbitrary), search speed, foreknowledge of maximum capacity).  All these things can give large hints as to which implementation would be most suitable.

So, we call these common groups of traits the "common" name for that type: list, array, what have you.

Of course you could use some strange syntax to differentiate between them.

The main problem syntactically is that you can't use [] on lists;  indexing lists is contrary to the nature of the class (although possible, algorithmically it's very slow).  Arrays, while conveniently indexable by integer, also don't index well when the index isn't integral.  And when it is integral, it can end up wasting lots of space if data is sparse.  So sparse arrays would be nice too.

Iteration seems to be the one common factor in (almost!) all containers. Indexing is a luxury that can be emulated if necessary.

> Basically, the idea is that the compiler would look at the things that you do to the container, and choose an appropriate type.  If all you ever do is array.addTail and array.removeFront, then it will decide to implement your container as a linked list (or doubly-linked list, if that's appropriate).  If all you do is access by integer indexes, then it uses an array.  And so on.

Getting the compiler to detect this sounds difficult.  I'd rather just tell it what kind of container I want.

> Of course, performance-critical code would want to specify how the thing was implemented.  So you add an optional "as" clause to array declarations:
>
>     int[char[]] myIntArray;    // compiler chooses container type
>     int[char[]] as hash myHashTable;    // compiler obliged to use
> "hash" as the container type

That sounds fairly ok.

> Then we would add a series of container-like properties to arrays:
>     addTail - exactly equivalent to the ~ operator, but included to
> match addFront,removeTail,removeFront
>     addFront
>     removeTail
>     removeFront
>     push - alias of addTail
>     pop - alias of removeTail
>     getTail - doesn't remove the object
>     getFront - doesn't remove the object
>     others?

Didn't I just post a list similar to this a few weeks ago?  ;)

> Explicit container types could include:
>     array (only valid if the index type is integers)
>     hash
>     list
>     dlist
>     tree
>     avltree
>     others?

There are a few above.

Sean