Re: filter an array in place

[Michal Kottman <k0mpjut0r@...>]

On Fri, 2011-01-14 at 11:37 +0000, liam mail wrote:

> On 14 January 2011 09:33, Axel Kittenberger <axkibe@gmail.com> wrote:
> I find this interesting. Why are the results from table.remove
> different from table[index]=nil?

When you set table[index]=nil, you remove the element at 'index' from
the table, but do not touch any other elements - thus creating a "table
with holes".

table.remove() on the other hand shifts every element after index one
position, so the actual indexes of them change.

To demonstrate: imagine a table t = {1, 2, 3, 4, 5}. When you want to
remove the '3' (at index 3), when you do t[3] = nil, you actually get
this table: {1, 2, nil, 4, 5}. When you table.remove() the 3, you get:
{1, 2, 4, 5}. Notice that indexes of values 4 & 5 are 4, 5 in the first
case, and 3, 4 in the second.

> I realise that after removing an element from an array it then has
> holes so it either needs fixing up or iterating with pairs but from
> the docs do state it is valid to remove an element whilst iterating.

> local tab = {"a", "a", "c", "a", "d", "a" }
>
> for index, val in ipairs(tab) do
>  if val == "a" then -- could be any other complex condition
>    --table.remove(tab, index)
>    tab[index]=nil
>  end
> end
> 
> for _,value in pairs(tab) do print(value) end

Yes, it is valid to "remove" an element from the table, but in this case
the "removing" is meant as assigning it to nil. Your latter example
really shows that the "a" is missing, however you did not print their
indexes to show what is really going on. If you print the result, you'll
actually get this:

> for key,value in pairs(tab) do print(key, value) end
3	c
5	d

That is not a table you can pass to ipairs() and get relevant results.
With table.remove() instead, you get this:

tab = {"a", "a", "c", "a", "d", "a" }

-- for loop ignores modifying the loop variable, it has to be
-- rewritten as a 'while' loop
local i=1
while i<=#tab do
 if tab[i] == "a" then
  table.remove(tab, i)
  -- do not increment the index here, retry the same element
 else
  i = i + 1
 end
end

for key,value in ipairs(tab) do -- notice that ipairs works
 print(key, value)
end

> for key,value in ipairs(tab) do print(key, values) end
1	c
2	d

Overall, when working with sequences/lists, it is much better to use a
library designed to work with them then trying to implement your own.
Examples of these include Penlight [1] and Underscore [2]. Filtering in
these looks like:

Penlight: List(tab):filter(function(x) return x ~= "a" end)
Underscore: _.select(tab, function(x) return x ~= "a" end)

Maybe this should go to the "Lua gotchas" list? :)


[1] http://penlight.luaforge.net/
[2] http://mirven.github.com/underscore.lua/