Re: Map and filter without intermediate tables

[joao lobato <btnfdp.lobato@...>]

On 6/7/12, Geoff Leyland <geoff_leyland@fastmail.fm> wrote:
> Hi,
>
> As far as I can tell, the implementations of map and filter in
> penlight.tablex create intermediate tables of results.  Surely that's
> inefficient?
>
> Now that 5.2 has __pairs (or if you write your own __pairs-aware pairs in
> 5.1), has anyone tried maps and filters that don't use intermediate tables?
>
>
> I did, and it was slower than using intermediate tables (and more
> complicated.  It did save some memory though).  Is it a dead-end idea, or is
> it that my implementation [1] is brain dead?
>
> Cheers,
> Geoff
>
> [1] https://gist.github.com/2886368
>
>
>

Your code looks very convoluted.

When I want to iterate over the (i)pairs of a table without
intermediate tables I use these two guys:

local function map(f,g,t,i)
  local l = g(t,i)
  return function()
    if l == nil then return nil end
    local c = l
    l = g(t,l)
    return f(c)
  end
end

local function filter(p,g,t,i)
  local l = g(t,i)
  return function()
    if l == nil then return nil end
    local c
    repeat
      c,l = l,g(t,l)
    until c == nil or p(c) == true
    return c
  end
end

--

local square = function(n) return n*n end
local evenp = function(n) return n%2 == 0 end

local t = {} ; for i=1,100 do t[i] = i end

for k,v in map(square, ipairs(t)) do print(k,v) end
for k,v in filter(evenp, map(square, ipairs(t) do print(k,v) end