Re: Definition of table.insert

[Frank Siebenlist <frank.siebenlist@...>]

Sorry for jumping-in late into this discussion, which seems to have taken me thru 100s of messages about some interesting details about the Lua internals that I didn't know about...

What could help decide on the proper interface end associated semantics, is first to agree what the abstract data type is that you want to model/implement.

As I understand it, Lua does not really define the array/list/sequence-like personality of its table-type in any strict terms, and much of the confusion is centered around that ambiguity.

There are many options, and each of those has a different semantics associated with it - ... and you get what you want even if you didn't realize what you wanted ;-)

So, what would you want the array/list/sequence-like personality of the table to be:

an array?
semantics describes an access by index
insert/remove where all indices change above the change-point is not very array-like
immutability to the first order? meaning that if I do not change an array element explicitly, its value will remain the same...which would exclude insert/remove as a primitive array-operation but a user could explicitly implement it if needed (but then she would know why the index-value changed) - very nice property to have when you iterate as the number&position of elements doesn't change
fixed size? of flexible size?
For an array I can see a nil value useful to indicate not-assigned - if not, you can only define an array with known values, and setting/changing values would be subject to a non-nil test - or maybe a more generic value-type-enforcement, which is almost the same

or a list?
semantics is more sequential - first, next, rest, last - indices can be used as a nice shortcut but with the caveat that the associated value may change.
insert&remove make more sense for a mutable list-like structure - which would imply no guarantees about index-value binding - and removing while iterating could be interesting if you walk the index but is less error-prone if you use next/prev (if the underlying iterator-implementation would re-fix the next/prev bindings of the removed element...indices may not be the right vehicle in that case).
nil values could be allowed or not, but again it would be more a general value-type enforcement for list-value inclusion.
I can see applications for nil values in map-like functions where the result-values that fill the list are undefined for some predicate/transform, which would yield lists with possible nil values who's positions have to be preserved.

or tuple? or queue? or stack?

In all cases for those higher level data abstractions, it's difficult to find the semantics where inserting would fill "holes" instead of moving everything up...or everything down. It would be kind of mixing an array- and list-abstraction, a split-personality that makes my head spin. But then you would have to define the "everything" that has to be moved...the size of the (sparse-)array/list and that was another interesting looong thread on the mailing list without clear conclusions.

In short, it may not be possible to decide on the right interface and semantics if you have not pinned-down the details of the underlying abstraction you want ... choose and define one, and everything should fall into place.

-Frank.



> On 08.01.2011 16:28, David Kastrup wrote:
> 
> insert(t,n,somefunction(...))
> where somefunction may decide not to return a value.
> 
> Currently, if that function returns no value, table.insert(t, n) would insert 'n' as the last element of 't'. So, your proposal would change more than just a small case of 'nil' value.
> However, it would be really nice to have the thing you're talking about with any number of values returned by 'somefunction', not just 1 or 0. Here's how I'd like 'insert' to work:
> table.insert(table, pos, ...)
> 
> Inserts values '...' at position 'pos' in 'table', shifting up other elements to open space, if necessary. Returns number of elements inserted (i.e. the number of parameters passed as '...'. Alternatively, it could be made to return index of the last inserted element).
> So, this is backwards incompatible with |table.insert(t,x). There's| no special case for 'nil'. 1) The natural use case is when many elements must be inserted. Currently this can be done with a custom implementation or by inserting elements 1 by 1, thus slowly.
> 2) Here's another use case I really like:
> local t = {}
> t.n = table.insert(t, 1, f())
> 
> Example:
> function f()  return nil, nil  end
> -- =>  t = {n = 2}
> 
> 
> IMO, it's good the way it is. Less checks mean more code and
> documentation elegance.
> 
> Care to explain?
> 
> It's good when logic of a function is simple, like "table.inset(t, n, x) inserts x at position n in t". It's perfectly easy to explain and remember. In current implementation there is a special case of 'table.inset(t, x)' and turns out both of us forgot about it. I for one just found it in the manual while thinking about 'insert' with variable number of values. Your suggestion about a special treatment of 'nil' is similar in thatsense. It complicates the logic of 'insert' and would be rarely used. A suggestion to throw an error in case of 'nil' adds little complication to the logic and detects a potential error. The error should be rear, but not consistently reproduced, so I'm in a bit of a doubt. Note that table.insert is also capable of creating holes when 'n' is non-integer or a big negative value.
> --
> Best regards,
> Sergey Rozhenko                 
> mailto:sergroj@mail.ru