Prev: Countless Hum de dumm dum dumpty, I count 2 lines.of astonishing drivel
Next: Proposed quantum algorithm for inverting one-way permutations
From: Ollie Saunders on 15 Oct 2009 13:07
I'm trying to understand what is really meant by these words in
computer science. It seems like lots of programming language have
different definitions of what these are (read: an array in C is not
the same as an array in Ruby).

The reason I ask this question is because I was designing my own
programming language a while ago and I was having difficulty giving
the correct names to the data structures.
From: Mark T. B. Carroll on 15 Oct 2009 13:19
Ollie Saunders <oliver.saunders(a)gmail.com> writes:

> I'm trying to understand what is really meant by these words in
> computer science. It seems like lots of programming language have
> different definitions of what these are (read: an array in C is not
> the same as an array in Ruby).
>
> The reason I ask this question is because I was designing my own
> programming language a while ago and I was having difficulty giving
> the correct names to the data structures.

Associations I tend to have with these are:

vector: one-dimensional array, so, fixed size, O(1) lookup, contiguous
allocation
list: Lisp-like cons (singly-linked list), so O(n) lookup, can grow
tuple: fixed size (typically small), heterogeneous elements, element
position determines its type

As you're finding, there are myriad variants, but I hope the above
guides a little. Advanced underlying implementations using anything
from skip lists to 2-3 finger trees can improve features and
performance.

Mark
From: Ollie Saunders on 15 Oct 2009 14:50
On Oct 15, 6:19 pm, "Mark T. B. Carroll" <Mark.Carr...(a)Aetion.com>
wrote:
> Ollie Saunders <oliver.saund...(a)gmail.com> writes:
> > I'm trying to understand what is really meant by these words in
> > computer science. It seems like lots of programming language have
> > different definitions of what these are (read: an array in C is not
> > the same as an array in Ruby).
>
> > The reason I ask this question is because I was designing my own
> > programming language a while ago and I was having difficulty giving
> > the correct names to the data structures.
>
> Associations I tend to have with these are:
>
> vector: one-dimensional array, so, fixed size, O(1) lookup, contiguous
>         allocation
> list: Lisp-like cons (singly-linked list), so O(n) lookup, can grow
> tuple: fixed size (typically small), heterogeneous elements, element
>        position determines its type
>
> As you're finding, there are myriad variants, but I hope the above
> guides a little. Advanced underlying implementations using anything
> from skip lists to 2-3 finger trees can improve features and
> performance.
>
> Mark

If a vector is 1D, is it a vector if you can store vectors within
vectors?
From: Mark T. B. Carroll on 15 Oct 2009 15:31
Ollie Saunders <oliver.saunders(a)gmail.com> writes:

> On Oct 15, 6:19 pm, "Mark T. B. Carroll" <Mark.Carr...(a)Aetion.com>
> wrote:
)(snip)
>> vector: one-dimensional array, so, fixed size, O(1) lookup, contiguous
>>         allocation
(snip)
> If a vector is 1D, is it a vector if you can store vectors within
> vectors?

Maybe. (-: It's not something that really comes up for me. Exact
definitions will vary from language to language. I'd not prohibit it,
especially, given a vector whose elements are of some parametrically
polymorphic type, why not let them be vectors? In practice when I'm
thinking vector-of-vectors, at pseudocode level I'm often thinking of
them as multi-dimensional arrays, especially in languages which only
ever really have one-dimensional arrays (i.e. vectors) and actually
expect you to have pointers to arrays as elements if you want multiple
dimensions.

(An irrelevant aside: of course, array of pointers to arrays can be
useful for efficiently storing large triangular matrices.)

From a practical point of view, if some facet of your new language can
be made just like that of some popular language without costing you
simplicity, power, harmony, etc., then it can certainly assist with
teaching and adoption to borrow accordingly. For instance, one lesson
from the past couple of decades is, alas: if you want your language to
be adopted popularly, give it C++-like syntax. Or, at least, syntax not
needlessly dissimilar from some familiar to those you hope to attract.

Mark
From: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen on 16 Oct 2009 07:07
Ollie Saunders <oliver.saunders(a)gmail.com> writes:

> I'm trying to understand what is really meant by these words in
> computer science. It seems like lots of programming language have
> different definitions of what these are (read: an array in C is not
> the same as an array in Ruby).
>
> The reason I ask this question is because I was designing my own
> programming language a while ago and I was having difficulty giving
> the correct names to the data structures.

Array: May be multidimensional, lookup of arbitrary elements in constant
time, size determined at initialisation/allocation time and can not
(easily) be extended.

List: One-dimensional, O(n) access to nth element, but also O(N)
iteration over elements, where N is the size of the list. Size can
easily be extended by adding new elements to existing lists. Two lists
can share tails. Concatenation is O(n).

Vector: Often a synonym for one-dimensional array.

Tuple: Size specified by type, elements can be of different type, but
the type of each element is determined by the type of the tuple.
Essentially equivalent to a record, but with numbered fields instead of
named fields. Tuples are often generic, where records are typically
not.

Additionally:

Record: A collection of named fields, accessed by specifying field name.
Also called "structs".

Object: Like a record, but where some fields can be methods, i.e.,
functions that each have the full object as an implicit parameter
(usually called "this" or "self").

Union: A value that can be from one of a (usually small) number of
specified alternative types. In most cases, it is possible to test
which of the types the value is from (disjoint unions) but in other
cases not (like in C). Also called "sum types" or "variants".

Sequence: May be a synonym for a list, but can also be a structure where
subsegment (part of sequence from element m to element n) and
concatenation are O(log(N)), where N is the size, but where accessing
even the first element may also be O(log(N)).

Multiset: Collection where the order of elements do not matter, but
their multiplicity do. So [1,2,2] is the same as [2,1,2], but different
from [1,2].

Set: Collection where neither order nor multipliciy matters, so {1,2} is
the same as {2,2,1}.

Map: Binds keys to values, where keys and values can be of any type
(though some languages impose restrictions on key types) and where you
can add new bindings cheaply. Maps are also called "associative
arrays".

Torben
 | 
Pages: 1
Prev: Countless Hum de dumm dum dumpty, I count 2 lines.of astonishing drivel
Next: Proposed quantum algorithm for inverting one-way permutations