清單推導
 |
||
|
清單推導 |
|
與一些其他方法不同的是，下列的方法將清單推導實作成 Lua 中的純粹函式庫（不補丁或符號過濾器）。它使用一個動態程式碼產生（loadstring）的技巧，並且快取有點類似於 ShortAnonymousFunctions。
此函式庫已併入 [Penlight]。
local comp = require 'comprehension' . new() comp 'x^2 for x' {2,3} --> {2^2,3^2} comp 'x^2 for _,x in ipairs(_1)' {2,3} --> {2^2,3^2} comp 'x^2 for x=_1,_2' (2,3) --> {2^2,3^2} comp 'sum(x^2 for x)' {2,3} --> 2^2+3^2 comp 'max(x*y for x for y if x<4 if y<6)' ({2,3,4}, {4,5,6}) --> 3*5 comp 'table(v,k for k,v in pairs(_1))' {[3]=5, [5]=7} --> {[5]=3, [7]=5}
-- comprehension_test.lua -- test of comprehension.lua -- Utility function for the test suite. -- Returns true/false whether arrays a and b -- are equal. This does a deep by-value comparison (supports nested arrays). local function eqarray(a, b) if #a ~= #b then return false end for i=1,#a do if type(a[i]) == 'table' and type(b[i]) == 'table' then if not eqarray(a[i], b[i]) then return false end else if a[i] ~= b[i] then return false end end end return true end local comp = require 'comprehension' . new() -- test of list building assert(eqarray(comp 'x for x' {}, {})) assert(eqarray(comp 'x for x' {2,3}, {2,3})) assert(eqarray(comp 'x^2 for x' {2,3}, {2^2,3^2})) assert(eqarray(comp 'x for x if x % 2 == 0' {4,5,6,7}, {4,6})) assert(eqarray(comp '{x,y} for x for y if x>2 if y>4' ({2,3},{4,5}), {{3,5}})) -- test of table building local t = comp 'table(x,x+1 for x)' {3,4} assert(t[3] == 3+1 and t[4] == 4+1) local t = comp 'table(x,x+y for x for y)' ({3,4}, {2}) assert(t[3] == 3+2 and t[4] == 4+2) local t = comp 'table(v,k for k,v in pairs(_1))' {[3]=5, [5]=7} assert(t[5] == 3 and t[7] == 5) -- test of sum assert(comp 'sum(x for x)' {} == 0) assert(comp 'sum(x for x)' {2,3} == 2+3) assert(comp 'sum(x^2 for x)' {2,3} == 2^2+3^2) assert(comp 'sum(x*y for x for y)' ({2,3}, {4,5}) == 2*4+2*5+3*4+3*5) assert(comp 'sum(x^2 for x if x % 2 == 0)' {4,5,6,7} == 4^2+6^2) assert(comp 'sum(x*y for x for y if x>2 if y>4)' ({2,3}, {4,5}) == 3*5) -- test of min/max assert(comp 'min(x for x)' {3,5,2,4} == 2) assert(comp 'max(x for x)' {3,5,2,4} == 5) -- test of placeholder parameters -- assert(comp 'sum(x^_1 + _3 for x if x >= _4)' (2, nil, 3, 4, {3,4,5}) == 4^2+3 + 5^2+3) -- test of for = assert(comp 'sum(x^2 for x=2,3)' () == 2^2+3^2) assert(comp 'sum(x^2 for x=2,6,1+1)' () == 2^2+4^2+6^2) assert(comp 'sum(x*y*z for x=1,2 for y=3,3 for z)' {5,6} == 1*3*5 + 2*3*5 + 1*3*6 + 2*3*6) assert(comp 'sum(x*y*z for z for x=1,2 for y=3,3)' {5,6} == 1*3*5 + 2*3*5 + 1*3*6 + 2*3*6) -- test of for in assert(comp 'sum(i*v for i,v in ipairs(_1))' {2,3} == 1*2+2*3) assert(comp 'sum(i*v for i,v in _1,_2,_3)' (ipairs{2,3}) == 1*2+2*3) -- test of difficult syntax assert(eqarray(comp '" x for x " for x' {2}, {' x for x '})) assert(eqarray(comp 'x --[=[for x\n\n]=] for x' {2}, {2})) assert(eqarray(comp '(function() for i = 1,1 do return x*2 end end)() for x' {2}, {4})) assert(comp 'sum(("_5" and x)^_1 --[[_6]] for x)' (2, {4,5}) == 4^2 + 5^2) -- error checking assert(({pcall(function() comp 'x for __result' end)})[2] :find'not contain __ prefix') -- environment. -- Note: generated functions are set to the environment of the 'new' call. assert(5 == (function() local env = {d = 5} setfenv(1, env) local comp = comp.new() return comp 'sum(d for x)' {1} end)()); print 'DONE'
為了來說明執行時期的特徵，請考量下列程式碼
comp 'sum(x^2 for x if x % 2 == 0)'
它會被產生程式碼到這個 Lua 函式
local __in1 = ... local __result = ( 0 ) for __idx1 = 1, #__in1 do local x = __in1[__idx1] if x % 2 == 0 then __result = __result + ( __x^2 ) end end return __result
請注意，並沒有建立任何中間清單。此程式碼有效率地避免了記憶體配置（函式本身的配置除外，但這只會在第一次呼叫時進行，因為快取/記住）。而且，沒有任何全域變數被參照。
從 [github] 下載。
注意：此實作使用 LuaBalanced 模組。
此模組很新，而且可能還有一些漏洞。
一個簡單的擴充方法是提供比較像是數學（或者更像 Haskell）的語法
assert(comp 'sum { x^2 | x <- ?, x % 2 == 0 }' {2,3,4} == 2^2+4^2)
一個充滿說服力的擴充方法（由 Greg Fitzgerald 推薦），是實作由 SPJ 和 Wadler 提議的通用清單推導 [2]。這提供了一些明確的方向，可將此擴充到下一等級，而且與 Microsoft LINQ 相關的工作 [3] 顯示此擴充在實際應用中會呈現什麼樣子。
在清單推導中使用「zip」擴充，利用類似於論文中 Haskell 的符號
[ (x,y,z,w) | (x <- xs | y <- ys), (z <- zs | w <- ws) ] ,
只需要做一些小小的變更。產生該項目的相對應 Lua 函式會像是這樣
local __xs, __ys, __zs, __ws = ... local __ret = {} -- i.e. $list_init for __i=1,__math_min(#__xs, #__ys) do local x, y = __xs[__i], __ys[__i] for __j=1,__math_min(#__zs, #__ws) do local z, w = __zs[__j], __ws[__j] __ret[#__ret+1] = {x,y,z,w} -- i.e. $list_accum(__ret, x, y, z, w) end end return ret
（此處的「$」符號是是用於擴充原始碼的編譯時期巨集的簡寫。）
支援 sort 或 grouped by，例如再次使用論文中的符號
[ the x.name, sum x.deposit | x <- transactions, group by x.name ] ,
可藉由產生函式並像這樣
local __transactions = ... local __groups1 = {} local __groups2 = {} for __i = 1, #__transactions do local x = __transactions[__i] local __key = ( x.name ) -- i.e. $group_by_key __groups1[__key] = ( x.name ) -- i.e. $accum_the(__groups1[__key], $val1) __groups2[__key] = (__groups2[__key] or 0) + ( x.deposit ) -- i.e. $accum_sum(__groups2[__key], $val2) end local __result = {} -- i.e. $list_init for __key in __pairs(__groups1) do __result[__result+1] = {__groups1[__key], __groups2[__key]} -- i.e. $accum_list(__result, __v) end return __result
將此提升到完全發揮它的功能，在稍作研究後似乎相當容易達到，儘管這會對此模組產生重大的擴充（有人要接手嗎？）。
2009-12-01 - 修正 __call 方便操作員未快取（由 Joshua Jensen 在郵件清單中指出）
清單推導也已在 MetaLua（clist）中實作
清單理解也實作於 LuaMacros
Moonscript 有清單理解 -- http://moonscript.org/reference/#comprehensions . Moonscript 編譯成 Lua 程式碼。