Words about Arrays and Tables

> Lua combines arrays and dicts into "tables", which are usually indexed from 1 but can be indexed by any type as a dict.

I think it's more accurate to just call them hash tables ("dicts") that happen to support some very limited array-like functionality. "Appending" still looks like key insertion if you don't use a named method (https://stackoverflow.com/questions/27434142); `ipairs` misses those non-integer keys but also misses non-contiguous keys, or even a zero key (https://stackoverflow.com/questions/55108794); the `#` operator is not well defined once you add those non-contiguous keys (https://stackoverflow.com/questions/2705793) (so you can't actually cleanly override the choice to "start from 1"); slicing etc. aren't provided as operators (https://stackoverflow.com/questions/24821045); etc.

C and C++ do have multidimensional arrays [0], in the sense that they are arrays of arrays where the inner arrays all have the same fixed size, encoded into the multidimensional array type. Likewise in Go and Rust. This is different from, say, Java, where if you have an array of arrays, the inner arrays can all have different sizes, and there is no array type that could express that they shouldn’t.

Being able to express slices across arbitrary dimensions natively is another matter.

[0] https://en.cppreference.com/w/cpp/language/array.html#Multid...

> Go and Rust

The trade-offs are way too severe for people to agree to any implementation in a low level language like Rust or one that wants to be low level like Go.

We could get them in something like Python.

Rather than attempt to autocorrect it should just throw the submission back to the user for reconsideration instead of trying to autocorrect it. "2000 words about" is genuinely not that helpful of a title starter, but I'm not sure the autocorrection is any better.

> I only know of two languages, Pascal and Haskell, that are sufficiently flexible.

Julia, Fortran, some BASICs allow custom integer ranges.

Ada allows you to use any discrete range (integer, character, enums).

https://en.wikipedia.org/wiki/Comparison_of_programming_lang... - A more comprehensive list

The two columns of interest are "Specifiable index type" and "Specifiable base index".

> When is the last time you wish you could define an array where the indices are from a custom finite set, perhaps a range 100 to 200, perhaps an enum?

> ...

> The lack of this ability makes programmers use more general hash maps by default and therefore leave performance on the table.

You can simulate this in any language by hash-mapping the custom set elements to indices. (And in the general case, you won't be able to determine the indices faster than a hash table lookup.)

In fact, I imagine there are languages and implementations where hash table lookup is the fastest way to map 'a':'z' to 0:25.

In fact, let me try a (surely totally bogus) micro-benchmark right now:

  $ python -m timeit --setup 'lookup = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))' '[lookup[x] for x in "abcdefghijklmnopqrstuvwxyz"]'
  500000 loops, best of 5: 884 nsec per loop
  $ python -m timeit '[ord(x) - 97 for x in "abcdefghijklmnopqrstuvwxyz"]'
  200000 loops, best of 5: 1.21 usec per loop

Huh.

...And surely if you use the hash map directly, instead of using it to grab an index into another container, overall performance only gets better (unless maybe you need to save per-instance memory, and you have multiple containers using the same custom index scheme).

Hash tables are a pretty neat idea.

That sounds more like a linked list than an array.

In C, an array is just contiguous bytes, and you reach an index through math (starting location + (index * size)).

Pretty sure lots of languages still do this to some degree, as your lookup times are effectively zero, though altering the number of elements is way more complex/expensive than in a linked list.

> So what would be the value of having or using indexes other than Integers to index Arrays?

It removes a level of indirection, wasted space, and mental overhead. Suppose you have some table of 'a'..'z' -> whatever. What are your options?

- Switch/case. This may be optimized and fast, but that's not guaranteed across all languages and compilers.

- Hash map. This introduces memory overhead even if it is technically O(1) for access times.

- If in C, you could do:

  T* table = (T*)malloc(sizeof(T) * 26) - 'a'

So that the characters can be used naturally without later modification (not a feature in every language, though).

- Manually calculate each offset every time:

  table[c - 'a'] = ...

With language appropriate type conversions, if needed.

Or you can allow any custom range to work, and do the math in that last option automatically because it's trivial for a compiler to figure it out and it removes unnecessary mental overhead from the program reader and writer.

  table['a']

Just works.

> You can also define integer-valued named constants, and use those if you prefer.

Because everyone wants to see `lower_case_a = 0` and the 25 other cases in their code along with all other possible constants. At least use an enum, sane languages even make them type-safe (or at least safer).

> The characteristic feature of Arays is that all but the last element have their next element and all but the first element have their previous element.

Where are you getting that from? That's not the characteristic feature of Arrays, that's the characteristic feature of Doubly Linked Lists.