Array article should have guidance on how to avoid use of negative indices

[GHNewbiee]

MDN URL

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array

What specific section or headline is this issue about?

Notes

What information was incorrect, unhelpful, or incomplete?

Instructions how to overcome the need of using negative indices.

1st Example
I have the consecutive numbers: x: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 and a function f(x).

The easiest way to save the results of the function for each number is to use an array with indices the numbers themselves:

result[-5] = f(-5);
result[-4] = f(-4);
// ...
result[0] = f(0);
// ...
result[4] = f(4);
result[5] = f(5);

This is not consistent since result.length is 6 and not 11.

2nd Example

I have another group of consecutive numbers: y: -2, -1, 0, 1, 2, 3 and a new function f(x, y).

Again, the easiest way to save the results of the functions is to use a 2-dim array with indices the numbers themselves:

result[-5][-2] = f(-5, -2);
result[-5][-1] = f(-5, -1);
// ...
result[-4][-2] = f(-4, -2);
// ...
result[0][-2] = f(0, -2);
// ...
result[4][-2] = f(4, -2);
// ...
result[5][-2] = f(5, -2);
result[5][-1] = f(5, -1);
// ...

What did you expect to see?

Some practical workarounds from a mathematical point of view, too, if possible.

Do you have any supporting links, references, or citations?

No response

Do you have anything more you want to share?

An object could be used to store the functions results:

1st Example

result['-5'] = f(-5);
result['-4'] = f(-4);
// ...
result['0'] = f(0);
// ...
result['4'] = f(4);
result['5'] = f(5);

which is relatively easy but not elegant at all.

But for the

2nd Example

using similar keys is not ideal at all.

result['-5'].['-2'] = f(-5, -2);
result['-5'].['-1'] = f(-5, -1);
// ...
result['-4'].['-2'] = f(-4, -2);
result['-4'].['-1'] = f(-4, -1);
// ...
result['0'].['-2'] = f(0, -2);
result['0'].['-1'] = f(0, -1);
// ...
result['4'].['-2'] = f(4, -2);
result['4'].['-1'] = f(4, -1);
// ...
result['5'].['-2'] = f(5, -2);
result['5'].['-1'] = f(5, -1);
// ...

MDN metadata

Page report details

• Folder: en-us/web/javascript/reference/global_objects/array
• MDN URL: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
• GitHub URL: https://github.com/mdn/content/blob/main/files/en-us/web/javascript/reference/global_objects/array/index.md
• Last commit: mdn/content@d72d468
• Document last modified: 2022-07-24T05:37:39.000Z

[Josh-Cena]

You seem to have realized yourself that result[-5] = f(-5); is functionally equivalent to result["-5"] = f(-5);, i.e. it sets a normal property on the array without actually changing the length. It seems like a weird intuition to set the -5 index and expect it to magically become the first element (or... the "-5th element"?) of the array. Does it work like that in any language? I'll admit I don't know many vector-based languages, but it doesn't work like that in Python (where negative indices wrap to the end) or R (where negative indices select all but the first x elements). It does work like that in C, but that's a whole different story. I'm curious what you intend to make it work like.

[GHNewbiee]

... Does it work like that in any language? ...

Please, have a look at the Comparison of programming languages (array).

[Josh-Cena]

I was not asking "does any language allow you to index with negative numbers" because I know quite a few that do. I'm asking if there's any language where arr[-1] = 1 sets "the element before index 0" rather than "the last element of the array"—assuming that's what your desired effect is. The only one I know is C, but C arrays aren't arrays anyway (they don't even have length so the problem is moot). What do you intend to accomplish when you do arr[-1] = 1? That's important for us to suggest workarounds.

[Josh-Cena]

@GHNewbiee would be great if you can elaborate, else it's not really actionable

[GHNewbiee]

I have the following table:

⃥↓ x \ y →  ...   -4   -3   -2   -1   0   1   2   3   4   5   ...
...                                 ...
-3
-2                                               6
-1
 0         ...                    f(x, y)                    ...
 1
 2
...                                 ...

For each pair (x, y), a number is calculated by means of a function f(x, y).

I would like the most natural (in a point of making sense) way to store the calculated numbers. For example:

array[x][y] = f(x, y) ie array[-2][3] = f(-2, 3) = 6

Tia

[Josh-Cena]

I see what you mean. I think we can make an "interesting" example with that—it would not be an array but would be fun to demonstrate anyway.

[GHNewbiee]

@Josh-Cena Try to be an array, because the workaround being asked is on array and not for fun.

[Josh-Cena]

The idea is to proxify an array. Arrays are exotic objects that observe assignments to length and indices. We just need to observe assignments to negative indices as well, and increment length accordingly. The "interesting" part is that Array.isArray() is the only method known to tear proxies apart, so even that would work with our array proxy.

[GHNewbiee]

Could be feasible for this to be implemented behind the scene as Array.prototype.bound(x) where x a negative number from which Array.length starts counting?

[ghost]

Well, to a good measure, this isn't really a JavaScript-specific issue; it's applicable to other languages, or just generally CS/Mathematics.

Instructions how to overcome the need of using negative indices.

1st Example
I have the consecutive numbers: x: -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 and a function f(x).

The easiest way to save the results of the function for each number is to use an array with indices the numbers themselves:

result[-5] = f(-5);
result[-4] = f(-4);
// ...
result[0] = f(0);
// ...
result[4] = f(4);
result[5] = f(5);

You have an interval of integers from [a, b]; you want to map [a, b] -> {Natural numbers}. You would define a function!

a = -5, b = 5
g: [a, b] -> N
g(x) = x - a

g can be anything, but this is a working example - subtraction/addition!

Now, from the look of it, what you're performing seems similar to a well-known technique called "memoisation" (or "memoization").
A more general implementation may use a Map object:

const result = new Map;
...
result.set(-1, f(-1));
...

I have another group of consecutive numbers: y: -2, -1, 0, 1, 2, 3 and a new function f(x, y).

Again, the easiest way to save the results of the functions is to use a 2-dim array with indices the numbers themselves:

result[-5][-2] = f(-5, -2);
result[-5][-1] = f(-5, -1);
// ...
result[-4][-2] = f(-4, -2);
// ...
result[0][-2] = f(0, -2);
// ...
result[4][-2] = f(4, -2);
// ...
result[5][-2] = f(5, -2);
result[5][-1] = f(5, -1);
// ...

Even here I would suggest addition/subtraction.

Another idea is to use modulo, or even Array#at, provided that order isn't relevant, but just uniqueness; for example, given the integers {-1, 0, 1}, one could have

x ∈ {-1, 0, 1}

g(x) = x (mod 3)

-1 mod 3 = 2
0 mod 3 = 0
1 mod 3 = 1

And... it occurs to me that array.at(x) does not allow writing to indexes.

Mathematically, x mod y = x - y × floor(x ÷ y), in JavaScript:

const { floor } = Math;

const modulo = (x, y) => x - y * floor(x / y);

result[modulo(-1, 3)] = f(-1);
result[modulo(0, 3)] = f(0);
result[modulo(1, 3)] = f(1);

But again, in my opinion it seems out of place for MDN's documentation.

[ghost]

The idea is to proxify an array. Arrays are exotic objects that observe assignments to length and indices. We just need to observe assignments to negative indices as well, and increment length accordingly. The "interesting" part is that Array.isArray() is the only method known to tear proxies apart, so even that would work with our array proxy.

This seems odd / overkill, and quite ill-performant. If anything, I would suggest an aggregate structure that uses two arrays

write(k, v) {
 const array = [this.non_negatives, this.negatives][Number(k < 0)];
 array[Math.abs(k)] = v;
}

@GHNewbiee Why do you specifically need arrays? I believe more details are warranted...

[Josh-Cena]

Ah, just for clarity, backlinking from the discourse discussion as well: https://es.discourse.group/t/negative-indices-in-array/1418

I think what we can do on that page is:

1. tell people not to assume the index has any semantics: it's just a sequence, not a keyed collection.
2. Still, we can illustrate how a proxy mimics an array by having reactive length, because that's how Array Exotic Objects work under the hood.

[GHNewbiee]

@phosra

@GHNewbiee Why do you specifically need arrays? I believe more details are warranted...

I just need the simplest and most natural way to work with.

@Josh-Cena

tell people not to assume the index has any semantics

This is misleading and contrivance. Either we write:

• console.log(example[0]) or console.log(example[-3])
• for (let i = 0; ... or for (let i = -3; ...

both indices 0 and -3 has not any actual semantics. What changes is the sense and feeling we have of the things in general.

In addition and the most important is that ES/JS mainly supports two types of numbers: Floating point numbers and Integer numbers. Integers and natural numbers (positive integers) are of same semantics. Due to unlucky initial design/decision (or in favor of convenience), Array supports only natural numbers, a subset of integers.

Moreover, if you, in general, believe that index has a semantics when we use -3 instead of 0, then it would be really fair, honest and accurate to declare Positive Indexed Collections or Natural Indexed Collections and not just Indexed Collections.

[Josh-Cena]

It doesn't have semantics. When you do arr.unshift("foo"), all the other elements' indices would have shifted. This is a fundamental feature of arrays: the elements don't have any correlation to the index—they just "happen to" occupy a particular index. Only their order matters. This is also why sparse arrays don't make sense.

[teoli2003]

I may be wrong, but my understanding is:

Arrays are not maps. They are more like stacks and queues (they implement the methods to act as such), and lists (with the help of an external index or the next() method of the iterator protocol). They can be (and are) used as maps for positive consecutive integers (starting at 0), as long as there are no gaps, no deletion (That's a very common use case)

But they are not maps for any value, even any Number objects. That's why there is a Map object in JS (and no Stack, List or Queue).

[Josh-Cena]

Yep—that's correct.

and no Stack, List or Queue

To be fair, those (where List means LinkedList I assume) would still be very welcomed in JS. Especially queues, since addition/deletion can easily be unnecessarily $\mathcal{O}(n)$ with arrays.

[teoli2003]

Yes, complexity guarantees would be great.

[GHNewbiee]

@Josh-Cena

... the elements don't have any correlation to the index

Then why do we call them Indexed Collections and not just (Natural) Ordered Collections? Because you need a mechanism to read the ordered elements, you need an index which will be 1-1 correlated to each element! Surprise!

The elements DO have a kind of slack correlation to the index. As you already have written,index does show the order of the element in an array. Hence, element with index = -3 comes before the element with index = 5. This is what Array has only to understand. So, elements just "happen to" occupy the particular indices -3, -2, etc. Without being in the knowledge of Array, I just secretly correlate the indices with the elements in my convenience. So simple and natural! This is called simplicity and common practice!

This is also why sparse arrays don't make sense.

Sparse arrays can be used to describe actual situations and problems.

Stack, List (LinkedList) or Queue

Which one is sub-set of the other, including Array?

[Josh-Cena]

"Indexed" means you can index-access them. Doesn't mean index has anything special in it—otherwise it becomes a keyed collection. It's not "just" an ordered collection, since that would be something like a stack/queue/linked list which can't be index-accessed.

What you understand to be an array doesn't necessarily correspond to what it's designed for. When you figure out it doesn't do what you need, it means you are using the wrong data structure.

Sparse arrays can be used to describe actual situations and problems.

Sparse arrays are widely regarded to be a mistake; you don't get these in other languages. Arrays on a metaphysical level are always densely populated. What you want is a Map<number, unknown>.

Which one is sub-set of the other, including Array?

They are all orthogonal. As I said above, Array is the only one of these that supports random access of index. These are all ordered collections, but there's probably no common abstract interface that they share.

[GHNewbiee]

@Josh-Cena

When you figure out it doesn't do what you need, it means you are using the wrong data structure.

No necessarily! It means find out an easy way to overcome the design weakness of the data structure and make it works for you.

[Josh-Cena]

Sure, I've seen people using strings as arrays, using arrays as stacks... Not saying that doesn't work, but every data structure has its inherent properties and you'll just shoot yourself in the foot if you try to stretch it.

[teoli2003]

Unless there is an actual concrete proposal for enhancing our docs, I think we should close this issue.

[Josh-Cena]

I do think we should explain how it's a bad idea to assign semantics to the numeric indices, at the bare minimum.

[Rumyra]

Hey folks - as the length of this thread is very long, I'm going to convert it to a discussion. Once a clear task is defined from the conclusion, pls open an issue with the task itself - thanks!

[Josh-Cena]

@Rumyra I'm very confused. I thought we did reach some sort of agreement on what to do in mdn/content#19051 (comment) (well actually, everyone else was not really willing to make changes, but since we have an issue, I decided to elaborate on that anyway). But since it seems the team is not motivated overall to address this issue, I guess I personally would not work on it at the end of the day.

[Rumyra]

Sorry @Josh-Cena - the thread was long and it was difficult to determine what action or task was to be taken