I think I’m going to start on restrict today. There are some issues around atoms.

Atoms are the base items in our sets, the bottom-level things that can be in elements and scopes. I’m thinking they are strings and numbers. So far, I’ve only used strings, I believe.

The restrict operator that we’ve talked about selects elements from a set A, given a set B, such that A:intersect(B) equals B. Informally, this means that all the fields of b, element of B, are found in a, element of A, with the same values. It follows that it can’t ever select an element consisting of an atom, because they don’t contain anything.

I think I can implement the first version of restrict fairly simply, but there is the issue of what will happen if we turn it loose on a set that isn’t a set of sets. One position we could take is “don’t do that”, which is not entirely unreasonable, just mostly unreasonable.Anyway I think that’s another bridge that we’ll burn when we get to it.

Getting Started

I guess we’ll just begin with a test. We need a couple of sets containing records, i.e. other sets.

Even just thinking about this makes me want a better way to create sets. Typing all those addAt calls gets tedious. I guess I’ll do this one longhand, and see if I get an idea for shorthand.

I’ve got this much and you can see at the end that I’ve added one shorthand thing, the ability to do several addAt calls in a row. That will fail with someone not understanding addAt.

Hmm, no, it failed saying

7: Restrict -- Tests:115: attempt to index a nil value (field 'contents')

I forgot the () on ricia’s XSet call. Again:

7: Restrict -- Tests:95: attempt to index a nil value

Yes. If it were smarter, Codea would have said “a nil value addAt”. Make that work:

function XSet:addAt(element, scope)
    if self.locked then error("set is locked") end
    if not self.contents[scope] then
        self.contents[scope] = {}
    end
    self.contents[scope][element] = true
    return self
end

I expect this test to run. And it does. We have a set of records with cardinality 3. Woot. Now a selecting set:

            local pinckney = XSet():addAt("Pinckney","city")
            local B = XSet():addAt(pinckney,NULL)
            _:expect(B:card()).is(1)

I expect this to run. It does. So far so good. Now we’re ready to do some work:

            local C = A:restrict(B)
            _:expect(C:card()).is(2)

I’m not sure how to test the contents. I expect that I’ll print it at first. But this is enough to fail and I’m going to make it pass without faking it.

7: Restrict -- Tests:100: attempt to call a nil value (method 'restrict')

Restrict is a double loop. Let’s try by intention …

function XSet:restrict(anXSet)
    local result = XSet()
    self:iterate(checkEachElement)
end

OK, what is checkEachElement? it receives an element (a record) and a scope (NULL in this case) and checks it against the input set anXSet to see if the intersection of anXSet against the element is equal to anXSet.

So I expand to this:

function XSet:restrict(B)
    local result = XSet()
    local function checkEachElement(e,s)
        if B:intersectMatch(e) then
            result:addAt(e,s)
        end
    end
    self:iterate(checkEachElement)
end

The function, with input a record e and scope s, asks the other set, now named B, whether it has an “intersect match” with e in it. I think that’s right and we now need a new method on XSet, intersectMatch:

Note that the function above doesn’t return the result, one of my canonical errors. I fix that. Here’s what I’ve got:

function XSet:restrict(B)
    local result = XSet()
    local function checkEachElement(e,s)
        if B:intersectMatch(e) then
            result:addAt(e,s)
        end
    end
    self:iterate(checkEachElement)
    return result
end

function XSet:intersectMatch(aRecord)
    local flag = true
    local function checkRecForMatch(f,s)
        if aRecord:hasAt(f,s) then flag = true end
    end
    local function checkEachForMatch(bRecord,s)
        self:iterate(checkRecForMatch)
    end
    self:iterate(checkEachForMatch)
    return flag
end

That last step is a big one. And wouldn’t it be a good idea to init the flag to false? Perhaps but now:

7: Restrict  -- Actual: 0, Expected: 2

It didn’t find any. That intersectMatch thing needs at least one test.

Take a Breath

That’s a big patch of code. Let’s take a breath here. The fact that I need three local functions to do this is telling me that the iterate capability is pretty weak. There’s a fairly straightforward double loop way to do this but embedding it into these functions is tricky.

Let’s defer making this test run and write one that shows us comparing two records. What we’re checking is, for two records a and b, does a:intersect(b) equal b. We’re going to do it, however, not by performing the intersect but by checking, for each element of b, whether it appears in a. Same answer, different code.

        _:test("intersectMatch", function()
            local ron = XSet()
            ron:addAt("Jeffries","last")
            ron:addAt("Ron","first")
            ron:addAt("Pinckney","city")
            local pinckney = XSet():addAt("Pinckney","city")
            _:expect(ron:intersectMatch(pinckney)).is(true)
            local denver = XSet():addAt("Denver","city")
            _:expect(ron:intersectMatch(denver)).is(false)
        end)

I expected this to fail, because the restrict failed, but in fact this passes. So the bug is elsewhere.

Grr. I tried some stuff and lost the thread. I wish I had a revert point after writing the tests. I’m going to delete both methods and begin again, from intersectMatch first

8: intersectMatch  -- Actual: nil, Expected: true
8: intersectMatch  -- Actual: nil, Expected: false

Write intersectMatch. This function checks two sets a and b and returns true if every element of b is in a.

function XSet:intersectMatch(b)
    -- return true if every element of b is in self
    local flag = true
    local function selfHas(e,s)
        if not self:hasAt(e,s) then
            flag = false
        end
    end
    b:iterate(selfHas)
    return flag
end

The intersectMatch test passes. Now let’s do restrict.

function XSet:restrict(B)
    -- return all elements of self that match some element of B
    local result = XSet()
    local function matchesSomeB(a,s)
        if B:hasMatchFor(a,s) then
            result:addAt(a,s)
        end
    end
    self:iterate(matchesSomeB)
    return result
end

That seems credible and should demand hasMatchFor:

7: Restrict -- Tests:204: attempt to call a nil value (method 'hasMatchFor')

function XSet:hasMatchFor(a,s)
    -- return true if self has a record matching a
    local flag = false
    local function checkMatch(b,s)
        if b:intersectMatch(a) then
            flag = true
        end
    end
    self:iterate(checkMatch)
    return flag
end

Test fails Doesn’t find any records.

I’m iterating the wrong set, I think. I freely grant that I am fully in debugging mode now. That’s not good. But I feel so close …

OK. Here’s the code that works. I think there may be two parameter reversals in there:

function XSet:restrict(B)
    -- return all elements of self that match some element of B
    local result = XSet()
    local function matchesSomeB(a,s)
        if B:hasMatchFor(a,s) then
            result:addAt(a,s)
        end
    end
    self:iterate(matchesSomeB)
    return result
end

function XSet:hasMatchFor(a,s)
    --return true if self has a record matching a
    a:display("has match for ")
    local flag = false
    local function checkMatch(b,s)
        b:display("b record")
        if a:intersectMatch(b) then
            flag = true
        end
    end
    self:iterate(checkMatch)
    return flag
end

function XSet:intersectMatch(b)
    -- return true if every element of b is in self
    self:display("imatch ")
    local flag = true
    local function selfHas(e,s)
        if not self:hasAt(e,s) then
            flag = false
        end
    end
    b:iterate(selfHas)
    return flag
end

What I changed was the call to intersectMatch, which used to say

b:intersectMatch(a)

Honestly I think that’s backward and in any case too complex to understand.

My tests are green, so I can commit this and then improve it without losing my notch forward. Commit: initial restrict test passing.

Again …

OK, we are implementing

A:restrict(B)

The definition of that is that

A:restrict(B) is all the records a of A such that there exists a record b in B such that b:intersect(a) equals b.

Can we just write that in code? I think I’ll remove all those ne methods and try again.

function XSet:restrict(B)
    -- return all elements (a) of self such that
    --  there exists a record (b) in B such that
    --      b:intersect(a) equals b 
    local result = XSet()
    local function doesBexist(a,s)
        if B:doesIntersectMatchExist(a,s) then
            result:addAt(a,s)
        end
    end
    self:iterate(doesBexist)
    return result
end

That’ll fail looking for doesIntersectMatchExist (and for the other intersect check which I may need.

7: Restrict -- Tests:191: attempt to call a nil value (method 'doesIntersectMatchExist')
8: intersectMatch -- Tests:110: attempt to call a nil value (method 'intersectMatch')

One thing at a time. I think I want intersect match. It has to iterate the smaller set, the restricting set. Here’s the test for that:

        _:test("intersectMatch", function()
            local ron = XSet()
            ron:addAt("Jeffries","last")
            ron:addAt("Ron","first")
            ron:addAt("Pinckney","city")
            local pinckney = XSet():addAt("Pinckney","city")
            _:expect(ron:intersectMatch(pinckney)).is(true)
            local denver = XSet():addAt("Denver","city")
            _:expect(ron:intersectMatch(denver)).is(false)
        end)

I think that’s the reverse of what we want, so:

        _:test("intersectMatch", function()
            local ron = XSet()
            ron:addAt("Jeffries","last")
            ron:addAt("Ron","first")
            ron:addAt("Pinckney","city")
            local pinckney = XSet():addAt("Pinckney","city")
            _:expect(pinckney:intersectMatch(ron)).is(true)
            local denver = XSet():addAt("Denver","city")
            _:expect(denver:intersectMatch(ron)).is(false)
        end)

I think that’s what felt backward before. Anyway make that test run:

function XSet:intersectMatch(a)
    -- return whether the intersection of this record (b) and the record (a) is (b)
    -- this is true if all elements of self are found in a
    flag = true
    local function hasNoMatch(b,s)
        if not a:hasAt(b,s) then
            flag = false
        end
    end
    self:iterate(hasNoMatch)
    return flag
end

This makes the test run and is, I hope, a bit more clear.

There is an issue: this function does not early-out on finding a false. It has to iterate all the way through all its fields even if one does not match. Hopefully that’s not a terrible issue.

We have a similar issue at the restrict level, in that we check all the match records even if one has matched. Anyway the match test runs, and we still need the other method:

7: Restrict -- Tests:204: attempt to call a nil value (method 'doesIntersectMatchExist')

function XSet:doesIntersectMatchExist(a)
    -- return true if some element b of this set 
    --    has an intersect match with a 
    --    i.e. b:intersect(a) == b
    local flag = false
    local function checkIntersects(b,s)
        if b:intersectMatch(a) then
            flag = true
        end
    end
    self:iterate(checkIntersects)
    return flag    
end

The tests all run. Commit: improved restrict implementation.

Let’s reflect.

Reflection

This was tricky. Part of the problem is that we have to iterate over all the elements (a) of the “big” set (A), and for each one, we have to iterate over all the elements (b) of the “little” set (B), and we have to check each a,b pair to see whether b:intersect(a) equals b … and we do that in a tricksy way, by looking into a to see if each element of b is in there.

Why didn’t I just do a:intersect(b) and check for equality? Well, mostly because I don’t have a check yet for set equality, and because checking for equality is a bit tricksy in itself.

Two sets A and B are equal iff for every a in A, a is also in B, and for every b in B, b is also in A. (And the scopes have to match as well.)

So there is an implicit double loop in there. So I wanted to avoid doing that.

Perhaps that was wrong. Perhaps I should just go ahead and implement it correctly.

Let’s remove all this stuff and do it again. This time I’ll remove the intersectMatch test, and replace it with an equality test.

        _:test("set equality", function()
            local one = XSet():addAt("Ron","first"):addAt("Jeffries","last")
            local two = XSet():addAt("Ron","first"):addAt("Perlman","last")
            _:expect(one:equals(one)).is(true)
            _:expect(one:equals(two)).is(false)
        end)

Should fail not knowing equals:

8: set equality -- Tests:107: attempt to call a nil value (method 'equals')

So:

function XSet:equals(B)
    return self:findsAllIn(B) and B:findsAllIn(self)
end

function XSet:findsAllIn(other)
    local flag = true
    local function find(e,s)
        if other:hasntAt(e,s) then
            flag = false
        end
    end
    self:iterate(find)
    return flag
end

And I implemented hasntAt, since I’ve needed it a lot:

function XSet:hasntAt(e,s)
    return not self:hasAt(e,s)
end

The equality test passes.

Now let’s record restrict to use it.

function XSet:doesIntersectMatchExist(a)
    -- return true if some element b of this set 
    --    has an intersect match with a 
    --    i.e. b:intersect(a) == b
    local flag = false
    local function checkIntersects(b,s)
        if b:intersect(a):equals(b) then
            flag = true
        end
    end
    self:iterate(checkIntersects)
    return flag    
end

The operative line change is:

        if b:intersect(a):equals(b) then

Now I can get rid of this:

function XSet:intersectMatch(a)
    -- return whether the intersection of this record (b) and the record (a) is (b)
    -- this is true if all elements of self are found in a
    flag = true
    local function hasNoMatch(b,s)
        if not a:hasAt(b,s) then
            flag = false
        end
    end
    self:iterate(hasNoMatch)
    return flag
end

So I think that’s better, we have at least one fewer weird methods. And it was all weird just because I was trying to optimize the code.

Let’s commit and then do even better. Commit: XSet:equals implemented and used in restrict.

There’s another useful definition of set equality. Two sets are equal if each is an (improper) subset of the other. It’s like saying two numbers are equal if each is less than or equal to the other. In set theory, the term “subset” includes improper (the equal case) and we say “proper subset” if we want to exclude it.

Let’s recast in terms of subset.

function XSet:equals(B)
    return self:isSubset(B) and B:isSubset(self)
end

function XSet:isSubset(other)
    local flag = true
    local function find(e,s)
        if other:hasntAt(e,s) then
            flag = false
        end
    end
    self:iterate(find)
    return flag
end

So that’s nice. I think we’ve done well for today, and in fact we could argue that our story, implementing restrict is done. There’s some learning to be had.

Summary

OK, story done. That’s good.

It took three tries to make restrict work, and about three more to get it factored reasonably well. So this tells us that our objects weren’t helping us enough. And since we’re implementing set theory, it probably tells us that our objects aren’t doing enough set theory, or doing it well enough.

We’ve made some progress on that.

The iterate capability, as amusing as it is, is tricky to use. I think there are a couple of reasons and that we can perhaps do something about some of them.

One issue is that we have to provide a function to iterate. In an ordinary Lua loop, we just say

for e,s in pairs(set) do
  blah...
end

So if our sets could work with pairs that would probably let us write clearer code. And we might not have to do so much flag setting, and could probably do some early returns for efficiency.

I’ll have to study how to do that. It’s not terribly tricky but I can’t just type it in.

There are also two math notions that might help, “there exists” and “for every”. We could have used “there exists” today, since the definition of restrict includes that notion:

A:restrict(B) is all the records a of A such that there exists a record b in B such that b:intersect(a) equals b.

I’m not sure quite how we’d express it, but we’re certainly doing it so it seems worth thinking about.

What we should probably do is work with Lua syntax to decide a better form for what we’d like to say, and then see how to do it. It might be straightforward.

Temptation …

I am quite tempted to try it right now. I’m probably too close to tired, but if I just do it in a test, how bad could it be? Let’s go for it.

Exists

        _:test("exists", function()
            local ron = XSet()
            ron:addAt("Jeffries","last")
            ron:addAt("Ron","first")
            ron:addAt("Pinckney","city")
            local chet = XSet()
            chet:addAt("Hendrickson","last")
            chet:addAt("Chet","first")
            chet:addAt("Atlanta","city")
            local ricia = XSet()
            ricia:addAt("Hughes","last")
            ricia:addAt("Ricia","first")
            ricia:addAt("Pinckney","city")
            local A = XSet():addAt(ron,NULL):addAt(chet,NULL):addAt(ricia,NULL)
            local function check1(a,s)
                return a:hasAt("Pinckney", "city")
            end
            local function check2(a,s)
                return a:hasAt("Denver","city")
            end
            local yes = A:exists(check1)
            local no = A:exists(check2)
            _:expect(yes).is(true)
            _:expect(no).is(false)
        end)

We still have to pass in a boolean function. The implementation is this:

function XSet:exists(booleanFunction)
    for scope,elements in pairs(self.contents) do
        for element, _true in pairs(elements) do
            if booleanFunction(element, scope) then
                return true
            end
        end
    end
    return false
end

We could simplify this if we had an iterator for the XSet, which I’ll look into later today or tomorrow.

Now that we have exists, we should be able to use it. First commit: XSet:exists added.

Can we fit it into restrict?

function XSet:restrict(B)
    -- return all elements (a) of self such that
    --  there exists a record (b) in B such that
    --      b:intersect(a) equals b 
    local result = XSet()
    local function doesBexist(a,s)
        if B:doesIntersectMatchExist(a,s) then
            result:addAt(a,s)
        end
    end
    self:iterate(doesBexist)
    return result
end

It can’t go there, at least I don’t see how.

function XSet:doesIntersectMatchExist(a)
    -- return true if some element b of this set 
    --    has an intersect match with a 
    --    i.e. b:intersect(a) == b
    local flag = false
    local function checkIntersects(b,s)
        if b:intersect(a):equals(b) then
            flag = true
        end
    end
    self:iterate(checkIntersects)
    return flag    
end

Here, I think we can use it.

function XSet:doesIntersectMatchExist(a)
    -- return true if some element b of this set 
    --    has an intersect match with a 
    --    i.e. b:intersect(a) == b
    local function checkIntersects(b,s)
        return b:intersect(a):equals(b)
    end
    return self:exists(checkIntersects)
end

Yes. Tests run. Commit: doesIntersectMatch uses exists.

Summary Summary

OK, good enough. We have restrict working, plus three new and useful operations, exists, equals and isSubset.

A nice day’s work and the code’s not too awful. We’ll see tomorrow what’s next.