[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

• Subject: Re: Set operators in Lua
• From: Luis Carvalho <carvalho@...>
• Date: Wed, 30 Jul 2008 10:14:53 -0400

```>    Has anyone created Set operators for tables in Lua?

No, but it shouldn't be hard. Here's a simple take at it:

-- Set.lua
local pairs, setmetatable = pairs, setmetatable
local mt -- metatable
mt = {
__add = function(s1, s2) -- union
local s = {}
for e in pairs(s1) do s[e] = true end
for e in pairs(s2) do s[e] = true end
return setmetatable(s, mt)
end,
__mul = function(s1, s2) -- intersection
local s = {}
for e in pairs(s1) do
if s2[e] then s[e] = true end
end
return setmetatable(s, mt)
end,
__sub = function(s1, s2) -- set difference
local s = {}
for e in pairs(s1) do
if not s2[e] then s[e] = true end
end
return setmetatable(s, mt)
end
}

local card = function(s) -- #elements
local n = 0
for k in pairs(s) do n = n + 1 end
return n
end

Set = setmetatable({elements = pairs, card = card}, {
__call = function(_, t) -- new set
local t = t or {}
local s = {}
for _, e in pairs(t) do s[e] = true end
return setmetatable(s, mt)
end
})

module "Set"

Test:

\$ lua -lSet
Lua 5.1.2  Copyright (C) 1994-2007 Lua.org, PUC-Rio
> S1 = Set{1,2,3}
> S2 = Set{2,5}
> for k in Set.elements(S1 + S2) do print(k) end
1
2
3
5
> for k in Set.elements(S1 * S2) do print(k) end
2
> for k in Set.elements(S1 - S2) do print(k) end
1
3
> print("S1", Set.card(S1), "S2", Set.card(S2))
S1      3       S2      2

With a little bit more of effort you can implement __len using userdata
through newproxy and a weak-keyed cache table where t[userdata] = set_table,
but I guess it's easier to wait for Lua 5.2 when __len will be honored for
tables. :)

Cheers,
Luis.

--
A mathematician is a device for turning coffee into theorems.
-- P. Erdos

--
Luis Carvalho
Applied Math PhD Student
Brown University

```