Re: 'table' as fallback for tables

[Philipp Janda <siffiejoe@...>]

Am 25.06.2016 um 23:57 schröbte Tim Hill:
> > On Jun 25, 2016, at 2:38 PM, Philipp Janda <siffiejoe@gmx.net> wrote:
> >
> > The more interesting question is: Should the rest of the table
> > library work on the kind of tables returned by `table.pack()`? Most
> > functions respect `_len` (and `__(new)index`), but in case of
> > `table.insert()`, `table.remove()`, and `table.move()` you have to
> > *update* the length, which isn't possible with `__len` alone.
> > Originally intended or not, the `table.pack()` tables are now a
> > prototype for potentially sparse arrays in Lua. Is this a more
> > useful format for arrays in Lua than sequences? Should Lua
> > encourage using `t.n` tables instead of sequences for most/all
> > array needs?
>
> Hence my earlier post. Of course, *every* Lua table is a sparse
> array, though in many cases its empty.

If you allow `nil` values in arrays, it's not that simple. Consider 
`local t = {}`. This could be an empty table, or a sparse array 
consisting of a single `nil` value, ..., or a million `nil` values.

> That is, unless you *define* a sparse array as a table having an “n”
> key

Bingo! I'd say an `n` key with an integer value greater than or equal to 
0, but let's not nitpick. I also think this would have been a viable 
alternative to the sequence concept we now have, because it has some 
useful properties:

*  It can hold `nil` values.
*  There's no undefinedness or inconsistency regarding length and 
contents of the table.
*  "Calculating" the array length is O(1).
*  Resizing is O(1) (although you probably would want to clear integer 
keys that fell out of the new array range).
*  *Checking* whether a table is an array is O(1) (which is much better 
than what we have now).
*  The table library could be adapted to this protocol without problems.
*  You can still have mixed tables (with hash and array elements).
*  It fits nicely with the world view that tables are mappings from 
arbitrary keys to the default value `nil` -- with a few explicit exceptions.

Downsides:
*  Modifying an array range would be a two step process; you couldn't 
shrink an array just by assigning `nil` to `t[#t]`, or grow it by 
assigning to `t[#t+1]`. I suppose most people would start using the 
table library functions for this (if they don't do that already).
*  Counting elements in table literals is cumbersome (Lua could help 
with that, though).

> (and hope no-one uses this perfectly normal key for something
> else…).

It doesn't matter as long as you don't pass this table to one of the 
array processing functions. If you do anyway, Bad Things(TM) will 
happen, but this is no different than what happens with sequences now.
`n` has a tradition since Lua 5.0, it is conveniently short, and 
`table.pack()` already uses it, but I don't care much about the name.

> So what use is # or “.n”
> anyway? Primarily, it gives an upper bound for iteration, sorting
> etc.

I'd say it defines the end of the range you are interested in.

> —Tim

Philipp