反覆運算元教學課程

wiki

演算法

我們可以撰寫自己的反覆運算元，以便由 for 陳述呼叫。以下 Lua 偽程式碼說明 for 陳述如何使用反覆運算元。

-- Equivalent to "for var1, ���, varn in explist do block end"
do
  local iterator, state, var1 = explist
  local var2, ... , varn
  while true do
    var1, ..., varn = iterator(state, var1)
    if var1 == nil then break end
      -- for block code
  end
end

狀態和目前的關鍵值會傳遞至反覆運算元。反覆運算元會傳回新的關鍵值和其他任何值，例如，由反覆運算元產生的值。如果傳回 nil，則 for 迴圈會終止。

簡單範例

以下反覆運算元會傳回一個平方值序列。當我們不傳回任何值（例如，n>=state），Lua 會傳回 nil，使反覆運算終止。請注意，反覆運算元會在指定反覆運算的下一值。我們會使用 state 來維持我們希望執行的反覆運算次數。

> function square(state,n) if n<state then n=n+1 return n,n*n end end

以下是呼叫反覆運算元的 for 陳述

> for i,n in square,5,0 do print(i,n) end
1       1
2       4
3       9
4       16
5       25

我們可以將上面的範例包裹起來（例如 pairs()），並提供一個 squares(nbvals) 的反覆運算元建構函數。例如，

> function squares(nbvals) return square,nbvals,0 end  -- iterator,state,initial value

現在，我們可以像呼叫 pairs() 那樣來呼叫它

> for i,n in squares(5) do print(i,n) end
1       1
2       4
3       9
4       16
5       25

複雜範例

以下反覆運算元類似於 ipairs，但允許多個表格反覆使用。

function ipairs(...)
  local t = {...}
  local tmp = {...}
  -- if nothing to iterate over just return a dummy iterator
  if #tmp==0 then
    return function() end, nil, nil
  end
  local function mult_ipairs_it(t, i)
    i = i+1
    for j=1,#t do
      local val = t[j][i]
      if val == nil then return val end
      tmp[j] = val
    end
    return i, unpack(tmp)
  end
  return mult_ipairs_it, t, 0
end

local t1 = {'a', 'b', 'c', 'd', 'e'}
local t2 = {'A', 'B', 'C', 'D', 'E', 'F'}

for k,v1,v2 in ipairs(t1, t2) do
  print(k,v1,v2)
end

數論範例

此反覆運算元會產生其引數質數除數。它依賴於明顯的事實，即不為零整數大於 1 的最小正除數必定是質數。

primdiv = function (n)
   assert(n ~= 0)
   if n < 0 then n = -n end
   local f = function (s,v) -- s not used
                   local p
                   if n == 1 then return end
                   while n%v > 0 and v*v < n do
                    if v == 2 then v = 3
                    else v = v + 2 end
                   end -- while
                   if n%v == 0 then
                    n = n/v; return v
                   end
                   if v*v > n then
                    p = n
                    n = 1; return p
                   end
                 end -- function
     return f,nil,2
    end -- function

 for p in primdiv(84) do io.write(p," ") end --> 2 2 3 7

RiciLake 說：我忍不住改寫它

function primdiv(n)
  assert(n ~= 0)
  if n < 0 then n = -n end
  local function f(_, v)
    if n > 1 then
      while n%v > 0 do
        v = v + (v == 2 and 1 or 2)
        if v*v > n then v = n end
      end -- while
      n = n / v
      return v
    end -- if
  end -- function
  return f,nil,2
end -- function primdiv

for p in primdiv(84) do io.write(p," ") end --> 2 2 3 7

GavinWraith 說：這樣好很多。但我仍認為使用 function primdiv(n) 就等同於程式設計語言癮君子身上的美沙酮。

其他範例

Lua 中的 ipairs

function ipairs(t)
  local function ipairs_it(t, i)
    i = i+1
    local v = t[i]
    if v ~= nil then
      return i,v
    else
      return nil
    end
  end
  return ipairs_it, t, 0
end

Lua 中的 Reverse ipairs

function ripairs(t)
  local max = 1
  while t[max] ~= nil do
    max = max + 1
  end
  local function ripairs_it(t, i)
    i = i-1
    local v = t[i]
    if v ~= nil then
      return i,v
    else
      return nil
    end
  end
  return ripairs_it, t, max
end

-- from the end backwards
function ripairs(t)
  local function ripairs_it(t,i)
    i=i-1
    local v=t[i]
    if v==nil then return v end
    return i,v
  end
  return ripairs_it, t, #t+1
end

-- traversing the whole 'array'
function ripairs(t)
  idx={}
  for k,v in pairs(t) do
    if type(k)=="number" then idx[#idx+1]=k end
  end
  table.sort(idx)
  local function ripairs_it(t,_)
    if #idx==0 then return nil end
    k=idx[#idx]
    idx[#idx]=nil
    return k,t[k]
  end
  return ripairs_it, t, nil
end

t1 = {'a', 'b', nil, 'd', 'e', nil}
for k,v in ripairs(t1) do print(k,v) end
--> 5 e
--> 4 d
--> 2 b
--> 1 a