Re: New array type? (was: 'table' as fallback for tables)

[Dirk Laurie <dirk.laurie@...>]

2016-07-08 11:51 GMT+02:00 Thomas Jericke <tjericke@indel.ch>:
> On 07/08/2016 09:07 AM, Dirk Laurie wrote:
>>
>> 2016-07-08 4:01 GMT+02:00 William Ahern <william@25thandclement.com>:
>>
>>> I can't think of a scenario where relying on the #t+1
>>> guarantee alone is either more concise or more performant.
>>
>> Suppose you have coroutines 'producer' and 'consumer' accessing
>> the same table. 'consumer' has some capricious way of choosing
>> an item and removing it. 'producer' has no way of knowing what
>> 'consumer' has been doing and now needs to put a new item in.
>>
>>      t[#t+1] = newitem
>>
>> seems to me to be unbeatably concise, and needs only O(log n)
>> time, but with the present Lua documentation is unsound code.
>> You can make it sound by sacrificing both conciseness and
>> performance:
>>
>>     local k=#t+1; while t[k] do k=k+1 end; t[k]=newitem
>>
>> which may take O(n) time.
>>

> Why not use a binary search in your example code?

Actually, #t does.

> Also, while I think your example is legit, I don't think it's such a common
> use case that it deserves its own operator.

It happens to _have_ its own operator, but that feature is no
longer documented.

> The current implementation of # could easily just be moved to
> a function of the table library.


Darn! These long threads let things slip under the carpet.

About 30 messages ago, I posted this:

~~~
1. Make the intuitive Lua 5.0 behaviour (to use the largest numeric
key of tbl as #tbl) the default. No presently documented property of
the # operator is violated.

2. Instead of 'n', which offends some people, use a secret key
which a modified 'next' (and therefore 'pairs') will not show.

3. New table functions:

table.frontier(tbl[,k])  Returns the k-th frontier of tbl, that is,
an integer n>=0 such that t[n+1] is nil but either n=0 or t[n]
is not nil. If k is omitted, any frontier of t may be returned.

table.getlength(tbl)  Returns the value, if any, to be returned
by #tbl when no __len metamethod has been specified.

table.setlength(tbl,n) Sets n as the value to be returned by
#tbl when no __len metamethod has been specified.

The current O(log n) but nondeterministic #t is obtained by

   setmetatable(tbl,table.frontier)
~~~

So I agree with you on this point :-)