Re: Removing holes from a list

["Gary V. Vaughan" <gary@...>]

> On 26 Sep 2015, at 19:58, Dirk Laurie <dirk.laurie@gmail.com> wrote:
> 
> 2015-09-26 17:44 GMT+02:00 Luiz Henrique de Figueiredo <lhf@tecgraf.puc-rio.br>:
>> 
>> Try this:
>> 
>> list=table.pack(1,2,3,nil,4,5,nil,nil,6,7)
>> 
>> local n=0
>> for i=1,list.n do
>>        if list[i]~=ni then
>>                n=n+1
>>                list[n]=list[i]
>>        end
>> end
>> list.n=n
>> 
>> for k,v in ipairs(list) do print(k,v) end
> 
> This is a little like one of my solutions, but neater. Thanks.
> 
> However, #list is still 10. One needs, before resetting list.n,
> 
> for i=n+1,list.n do list[i]=nil end
> 

Here’s a (non-destructive) functional solution:

  function id (...) return ... end
  
  function collect (r, predicate, n, x, ...)
    if n == 0 then return r end
    r[#r + 1] = predicate (x) and x or nil
    return collect (r, predicate, n - 1, ...)
  end

  function filter (predicate, ...)
    return collect ({}, predicate, select ("#", ...), ...)
  end

  r = filter (id, 1, 2, 3, nil, 4, 5, nil, nil, 6, 7)

or, if you prefer:

  r = filter (id, (table.unpack or unpack) (list))

Thanks to tail-call elimination it’s actually reasonably fast too.

The slow `r[#r + 1]` part could be mitigated with a (premature! ugly!) optimisation:

  function collect (r, i, predicate, n, x, ...)
    if n == 0 then return r end
    if predicate (x) then
      i = i + 1
      r[i] = x
    end
    return collect (r, i, predicate, n - 1, ...)
  end

  function filter (predicate, ...)
    return collect ({}, 0, predicate, select (“#”, ...) ...)
  end

But it all boils down to keeping track of two indices, n and i, in any case :)

Cheers,
Gary