

20180720 20:57 GMT+02:00 William Ahern < [hidden email]>:
> I wish people (myself included) would keep in mind the symmetry that Lua
> tries to maintain between the language and the C API. Aside from making the
> C API incomparably superior to other language implementations, the
> constraint keeps Lua honest and careful. If a feature can be elegantly
> expressed and implemented for *both* the language and the C API, that's
> strong evidence it's a quality choice. If it can't be, it suggests to keep
> searching.
One place where the symmetry currently is broken is concatenation.
The C API function lua_concat respects metamethods, the table.concat
function does not.


> One place where the symmetry currently is broken is concatenation.
>
> The C API function lua_concat respects metamethods, the table.concat
> function does not.
The fair comparison is lua_concat vs the concatenation operator: both
respect metamethods.


20180723 11:55 GMT+02:00 Luiz Henrique de Figueiredo < [hidden email]>:
>> One place where the symmetry currently is broken is concatenation.
>>
>> The C API function lua_concat respects metamethods, the table.concat
>> function does not.
>
> The fair comparison is lua_concat vs the concatenation operator: both
> respect metamethods.
The problem with the concatenation operator is that it concatenates
just two values. If I concatenate everything in a table, respecting
metamethods, by the algorithm [1]
local s = ''
for k,v in ipairs(tbl) do s = s..v end
it takes O(n²) time, where n=#tbl, not to mention the memory problems.
To write an efficient pure Lua routine is possible, but quite challenging.
[1] The present implementation of 'lub.join' in the LuaRock 'lub' does
just that. I became aware of the problem when using the LuaRock
'xml' which depends on 'lub.join'. For that application, the workaround
lub.join = table.concat is possible, but there may be lub applications
that rely on metamethods being used.


> To write an efficient pure Lua routine is possible, but quite challenging.
an O( n * log( n ) ) one:
""" function _concat( t, p, n ) if n > 1 then local n2 = n // 2 return _concat( t, p, n2 ) .. _concat( t, p + n2, n  n2 ) end return t[ p ] end
function concat( tbl ) return _concat( tbl, 1, #tbl ) end """ For lua < 5.3 use math.floor( n / 2) or math.ceil, or round or whatever, it doesn't matter.


On 23/07/18 14:26, Axel Kittenberger wrote:
>> To write an efficient pure Lua routine is possible, but quite challenging.
>
> an O( n * log( n ) ) one:
> """
> function _concat( t, p, n )
> if n > 1 then
> local n2 = n // 2
> return _concat( t, p, n2 ) .. _concat( t, p + n2, n  n2 )
> end
> return t[ p ]
> end
>
> function concat( tbl )
> return _concat( tbl, 1, #tbl )
> end
> """
> For lua < 5.3 use math.floor( n / 2) or math.ceil, or round or whatever, it
> doesn't matter.
How about:
function concat(list, sep, i, j)
i = i or 1
j = j or #list
local tmp = {}
for i=1,#list do
tmp[i] = tostring(list[i])
end
return table.concat(tmp, sep, i, j)
end
Which would just be O(n)?
Might be able to improve with table.pack/unpack, maybe.
Scott


On 23/07/18 15:07, Scott Morgan wrote:
> How about:
>
> function concat(list, sep, i, j)
> i = i or 1
> j = j or #list
>
> local tmp = {}
> for i=1,#list do
> tmp[i] = tostring(list[i])
> end
> return table.concat(tmp, sep, i, j)
> end
>
> Which would just be O(n)?
>
> Might be able to improve with table.pack/unpack, maybe.
And I notice the mistake in the loop, doh!
Should be `for k=i,j do` etc. etc.
Scott


On 23 July 2018 at 15:10, Scott Morgan < [hidden email]> wrote:
> On 23/07/18 15:07, Scott Morgan wrote:
>> function concat(list, sep, i, j)
>> i = i or 1
>> j = j or #list
>>
>> local tmp = {}
>> for i=1,#list do
>
> And I notice the mistake in the loop, doh!
>
> Should be `for k=i,j do` etc. etc.
it should actually work as is, just the second use of `i` shadowing
the first one on the loop's scope, without affecting the final use.
of course, lintlike tools would bark at you for this

Javier


On 23/07/18 15:21, Javier Guerra Giraldez wrote:
> it should actually work as is, just the second use of `i` shadowing
> the first one on the loop's scope, without affecting the final use.
>
> of course, lintlike tools would bark at you for this
Yeah, the scoping would have been fine, just the `i,j` instead of the
inefficient `1,#list` bit was the problem.
Scott


> The problem with the concatenation operator is that it concatenates
> just two values.
Yes, but it is associative and "a..b..c..d" generates a *one*
instruction, not *three*.


20180723 16:47 GMT+02:00 Luiz Henrique de Figueiredo < [hidden email]>:
>> The problem with the concatenation operator is that it concatenates
>> just two values.
>
> Yes, but it is associative and "a..b..c..d" generates a *one*
> instruction, not *three*.
It's perfect in an actual expression like that.
But a function join(...) that just concatenates all its arguments,
respecting metamethods, is so easy to provide in the API and
so hard to do in pure Lua.


20180723 16:07 GMT+02:00 Scott Morgan < [hidden email]>:
> On 23/07/18 14:26, Axel Kittenberger wrote:
>>> To write an efficient pure Lua routine is possible, but quite challenging.
>>
>> an O( n * log( n ) ) one:
>> """
>> function _concat( t, p, n )
>> if n > 1 then
>> local n2 = n // 2
>> return _concat( t, p, n2 ) .. _concat( t, p + n2, n  n2 )
>> end
>> return t[ p ]
>> end
>>
>> function concat( tbl )
>> return _concat( tbl, 1, #tbl )
>> end
>> """
>> For lua < 5.3 use math.floor( n / 2) or math.ceil, or round or whatever, it
>> doesn't matter.
>
> How about:
>
> function concat(list, sep, i, j)
> i = i or 1
> j = j or #list
>
> local tmp = {}
> for i=1,#list do
> tmp[i] = tostring(list[i])
> end
> return table.concat(tmp, sep, i, j)
> end
You are not entitled to assume that obj1..obj2 is defined as
tostring(obj1)..tostring(obj2). You are not even entitled to
assume that the result of concatenation is stringvalued.
For example, concat may mean list concatenation.
obj{1,2,3}..obj{4,5} > obj{1,2,3,4,5}

