Re: Filtering Iterator

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

On 22/12/2012, Kevin Martin <kev82@khn.org.uk> wrote:
> Hi,
>
> I need an iterator wrapper/decorator I can use with for that allows me to
> skip values that don't match a specified predicate. I've done a bit of
> searching, but haven't been able to find one. I've written the below code
> and it works for the simple example given, but I'm struggling to convince
> myself it's correct. Can anyone see anything wrong with it, or does it look
> ok?
>
> Thanks,
> Kevin
>
> ----------------------------------------------
>
> function iterfilter(filter, iter, state1, var1)
> 	return function(state2, var2)
> 		while true do
> 			local t = table.pack(iter(state2, var2))
> 			if t[1] == nil then return nil end
> 			if filter(table.unpack(t)) then
> 				return table.unpack(t)
> 			end
> 			var2 = t[1]
> 		end
> 	end,
> 	 state1, var1
> end
>
> local t = {}
> for k=1,100 do
> 	t[k] = tostring(k)
> end
>
> local function div3(x)
> 	return x % 3 == 0
> end
>
> local function div5(x)
> 	return x % 5 == 0
> end
>
> for _,v in iterfilter(div3, iterfilter(div5, pairs(t))) do
> 	print(v)
> end
>
>
>

I've written this some time ago:

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

Just by comparison, I'd say yours is correct (of course mine is
stateful and only care about one return value).

However, all that packing and unpacking is bound to have a performance
hit. If that is a problem, you should consider making a less generic
solution, like an 'iterfilter2' that saves two return values of the
generating function in locals or an 'iterfiltermaker' that takes an
integer N that compiles (and memoizes) an iterfilterN (so, something
like a macro).