Re: Set operators in Lua

[Luis Carvalho <carvalho@...>]

>    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