I’m not sure whether this will be useful, but Bill Wake gets the credit if it is.

My plan here is to write a short article implementing the fold function on XSet. Fold is also known as reduce in FP lore. It’s the general function for summing and such. As we’ll see. I’m sure it can replace some or all of exists and every and any other such functions as I may have. You’ll recall that I had elementsDo for a while, which FP folks call map.

Anyway let’s get to it.

I begin by moving XSet to its own tab: I originally wrote it in the same tab as the tests, which is my usual starting style, but it’s time that it got its own place to live. Run the tests. Commit: XSet gets own tab.

I actually started this article yesterday, and wrote down to about here, at which point I realized that I needed to do some reading and experimentation. I don’t think I’ve done enough of either but let me share what I’ve got so far.

I wrote a toy program on my other iPad, which I’ll show in just a moment. In advance, I want to apologize for the cryptic names. On the other iPad, in the TV room, I type with one finger with the iPad on my lap, and I am really bad at one-finger typing. So I do very little of it, and that’s why there are names like tt in there.

Here’s my experiment.

Experiment

-- Reduce

-- Use this function to perform your initial setup
function setup()
   local s = Set{"jeffries@last", "ron@first", "mike@first"}
   local n = s:eproj("last")
   print(n)
   local f = s:eproj("first")
   print(f)
   local t = Set{"1@n","2@n","3@n"}
   local tt = t:map(function(r,k,v)
       print(r)
       return r:add((v+1).."@"..k)
   end)
   print("tt",tt)
   for k,v in pairs(tt.t) do
       print(k,v)
   end
end

Set = class()

function Set:init(t)
   self.t = t or {}
end

function Set:add(e)
   table.insert(self.t,e)
   return self
end

function Set:reduce(first, f)
   local result = first
   for _x,p in pairs(self.t) do
       v,k = p:match("^(.-)@(.*)$")
       result = f(result,k,v)
   end
   return result
end

function Set:map(f)
   return self:reduce(Set(),f)
end

function Set:eproj(scope)
   local found = false
   return self:reduce(nil, function(r,k,v)
       if not found and k==scope then
           found=true
           return v
       elseif found and scope==k then
           return nil
       else
           return r
       end
   end)
end

What we see above is an experiment with a tiny class called Set, on which I wrote and manually tested a function reduce, which is also often called fold or foldl. The essence of reduce is really like this, written in some kind of meta-Lua sort of language:

function Set:reduce(first, f)
   local result = first
   for element in self do
       result = f(result, element)
   end
   return result
end

Many readers are already familiar with reduce, as many modern languages offer reduce, and its friends map and filter. For a little light reading, I found this article to be both interesting and useful.

Once I had reduce working, I implemented map, using reduce. Map takes an input set and produces an output set by applying a function to each element of the input. You’d use map to produce the squares of {1,2,3,4,5} by providing a function like return x*x.

So that was nice. Then, because I really want to use this idea in XSets, I was reading an article on Extended Set Theory, as one does, and found the operation “Element Projection”, which is a function on a set. The function takes a scope value (think “field name”) and returns the element at that scope if and only if there is exactly one such element.

The “purpose” of the operator is presumably to provide a way, given an XSet with a result record in it, to get the field values back into your program. Whether it’s useful for that, I couldn’t say, but anyway I implemented it using reduce.

So that’s my report on my experiment. What have I learned, and what do I wonder?

Learnings and Wonderings

Well. I certainly learned quite a bit about how to implement reduce and how to use it to implement other operations. It seems that it may be a good way to do some kinds of set manipulations, but I’ll have to try them to be sure.

I’m not so sure about the deeper functional programming aspects of reduce and its friends. I’m pretty sure that reduce, or fold, as it is often called, is “universal” in the sense that it can be used to define any other traversing function. In my experiment I did use it to define map and it’s clear that it can do filter.

As for exists and every, well, yes, I can define those in terms of reduce but the implementations we have now do an early out as soon as the answer is known. I don’t think there’s a standard way to early-out a reduce. My reading suggests that you just can’t.

And there’s a lot of functional programming stuff about combining functions. That’s beyond my thinking right now, and I suspect it’ll stay that way for a while.

My plan is to implement reduce in XSets because I anticipate that it will be useful. That’s a bet that I am making, that an investment of some time will pay off in the future. It could be a bad bet, except that we’re here to learn, so even the most stupid ideas I have pay off in laughs and learning.

XSet Reduce

Begin with a test.

        _:test("Reduce", function()
            local s = XSet():addAt("1","pay"):addAt("20","pay"):addAt("300","tip")
            local income = s:reduce(0, function(r, e,s) return r+e end)
            _:expect(income).is(321)
        end)

The function provided to a reduce always includes the “summing” value and the element. In our case, we provide both e and s because that’s how XSets work.

Test fails looking for reduce:

26: Reduce -- Tests:369: attempt to call a nil value (method 'reduce')

That was the easy part.

function XSet:reduce(first,f)
    local result = first
    for e,s in self:elements() do
        result = f(result, e,s)
    end
    return result
end

That’s the hard part, and it worked the first time. Well, OK, the second time, after I remembered to return the result.

Are you surprised that I could just add those strings into the result? Well, this isn’t JavaScript, but Lua will do that.

So reduce works. Let’s try a more complex function.

        _:test("Reduce", function()
            local s = XSet():addAt("1","pay"):addAt("20","pay"):addAt("300","tip")
            local income = s:reduce(0, function(r, e,s) return r+e end)
            _:expect(income).is(321)
            local sumPayOnly = function(r,e,s)
                if s=="pay" then
                    return r+e
                else
                    return r
                end
            end
            local pay = s:reduce(0,sumPayOnly)
            _:expect(pay).is(21)
        end)

This is why you like your tips in cash, they don’t show up on your taxes. But I digress. Let’s see about producing an output set with just the pay in it.

        _:test("Reduce", function()
            local s = XSet():addAt("1","pay"):addAt("20","pay"):addAt("300","tip")
            local income = s:reduce(0, function(r, e,s) return r+e end)
            _:expect(income).is(321)
            
            local sumPayOnly = function(r,e,s)
                if s=="pay" then
                    return r+e
                else
                    return r
                end
            end
            local pay = s:reduce(0,sumPayOnly)
            _:expect(pay).is(21)
            
            local selectPay = function(r,e,s)
                if s=="pay" then
                    r:addAt(e,s)
                end
                return r
            end
            local payItems = s:reduce(XSet(),selectPay)
            _:expect(payItems:card()).is(2)
            local checkSum = payItems:reduce(0, function(r,e,s) return r+e end)
            _:expect(checkSum).is(21)
        end)

There it is and the sum convinces me that it has the right records. I decide to be more explicit:

            local payItems = s:reduce(XSet(),selectPay)
            _:expect(payItems:card()).is(2)
            _:expect(payItems:hasAt("1","pay")).is(true)
            _:expect(payItems:hasAt("20","pay")).is(true)
            local checkSum = payItems:reduce(0, function(r,e,s) return r+e end)
            _:expect(checkSum).is(21)

OK, I’d say it’s pretty clear that reduce is solid. Commit: implement XSet:reduce().

Mini Retro

OK, we have reduce. We have implemented it iteratively. Formally, I think that it’s supposed to be defined recursively, but I am a bit concerned about that. I do think that Lua has tail recursion, so it would probably be OK to iterate even a very long set recursively, but we don’t really have a decent way to get “the rest” of an XSet.

It might be fun to look into that. For now, we’ll let this ride.

I do think we can implement some of our other operations using reduce. For example, select:

function XSet:select(predicate)
    local result = XSet()
    for e,s in self:elements() do
        if predicate(e,s) then result:addAt(e,s) end
    end
    return result:lock()
end

This becomes:

function XSet:select(predicate)
    return self:reduce(XSet(), function(r,e,s)
        return predicate(e,s) and r:addAt(e,s) or r
    end)
end

Nice. Tests run. Commit: select uses reduce.

The select function is also called filter in FP talk. I chose select because of the SELECT term in SQL. We’re kind of doing database stuff here.

We could also implement map but we don’t have a test for that. I’m not sure what we might even do with it at this point. Much as I’d like to do it, I think we’d better not.

And anyway, breakfast and our standard Sunday morning Sunday Morning is about to start. Let’s sum up.

Summary

I freely grant that I’m putting in reduce speculatively, but it has already simplified select and shown some other interesting capabilities in the test. So that’s good.

There is a thing that should be true. Let me put it in words: I’m not sure how to put it in functions.

In my test that sums “pay”, the function I used checks whether scope is “pay” and sums if it is.

We could get that same result by first selecting all the elements with scope “pay” and then summing all the elements in that result set.

We’re sort of saying, though it’s not quite true as implemented today that

s:reduce(isPay):reduce(sum)
==
s:reduce(isPay·sum)

For some suitable definition of the (·) operator.

Down this path, I think, lies what Bill Wake was tweeting at me about.

I must think about this and explore it. It will be interesting and might be important.

Until then, my friends, stay strong and be happy.