Codea FP: A Trap
Today, for your delectation, I offer: the Library Trap!
There are many libraries out there, with useful capabilities. It has always seemed to me that they offer too much. They are often complicated, and at best offer a long list of capabilities of which I only need one or two. One reason for this is inherent in the situation: it’s unlikely that any given user will need all the features of the library, and only those. So the library that will fit our needs is nearly certain to offer something that we don’t need.
Another reason, of course, is that the library creator wants to be sure to offer enough, to ensure that most possible users will find what they need. To accomplish this, they must add things that only a few will need.
Yet another reason exists, and I’m calling it the Library Trap. We add capabilities to our library because it is what we are working on, we have ideas, and so we put them in because we can.
Today, for your delectation, I propose to demonstrate the Library Trap before your very eyes, by adding things to our little FP library, simply because I can. Will I go too far? Perhaps, but I think that in this case, the things we add are so atomic that they’ll add to the list of things we can do, but will not add much to complexity. Each function should pretty much stand alone: use it if you wish, ignore it if you wish. Nothing to learn but what you need, as nearly as we can manage it.
We’ll see. Let’s get to work. Well, to play, but it looks like work, only fun.
Reduce
We should write a test showing that reduce can create a table. I’m sure that it can, but the test can serve as a bit of documentation.
The trick is to think of a problem. Let’s do this:
Given a table of numbers, produce a table of tables, each inner table consisting of the starting number and its square.
_:test("reduce builds a table", function()
local square = function(result,value)
table.insert(result, {value, value*value})
return result
end
local input = {1,3,5}
local squares = ar.reduce(input,{},square)
local mid = squares[2]
_:expect(mid[1]).is(3)
_:expect(mid[2]).is(9)
end)
Now in fact this particular thing is better done with map. Let’s demonstrate that fact with another test:
_:test("map builds the table better", function()
local square = function(v) return {v, v*v} end
local input = {1,3,5}
local squares = ar.map(input,square)
local mid = squares[2]
_:expect(mid[1]).is(3)
_:expect(mid[2]).is(9)
end)
OK, good. Commit: new tests for documentation.
Wrappers
That wasn’t too much, and I think that wrappers won’t be too much either. I play to implement two functions, Array and Dictionary, that set up our fp tables as the metatables for the input tables in question, allowing us to send them messages rather than call functions on them. This is because I program mostly in an OO style and therefore want that capability.
It’s a customer request. Begin with a test:
_:test("Array function adds metatable", function()
local sum = function(result, value) return result+value end
local input = Array{2,4,6}
local total = input:reduce(0,sum)
_:expect(total).is(12)
end)
Test will fail looking for Array. And it does:
8: Array function adds metatable -- Main:133: attempt to call a nil value (global 'Array')
Implement:
function Array(tab)
setmetatable(tab,ar)
return tab
end
ar.__index = function(t,k)
return ar[k]
end
Test runs. Commit: Array function adds ar as metatable.
We need the same thing for Dictionary. I don’t love that name much, it’s kind of long. But it’ll do for now.
_:test("Dictionary function adds metatable", function()
local square = function(v) return v*v end
local input = Dictionary{two=2, three=3}
local squares = input:map(square)
_:expect(squares.two).is(4)
_:expect(squares.three).is(9)
end)
Should fail looking for Dictionary.
9: Dictionary function adds metatable -- Main:140: attempt to call a nil value (global 'Dictionary')
Implement:
function Dictionary(tab)
setmetatable(tab,kv)
return tab
end
kv.__index = function(t,k)
return kv[k]
end
Test runs. Commit: Dictionary function adds kv as metatable.
So far so good. Those are the first two “stories” from yesterday’s article. The final story from that list is
- Add some additional functions such as
existsandevery.
Additional Functions
Unless something interesting happens, I’ll just list the new functions’ test and implementation. I do expect to get bored making sure that I have the ar/kv duplicates very soon. First time, in fact. Here goes:
_:test("exists", function()
local cond = function(v) return v==2 end
local no = Array({1,3,5})
local yes = Array{15,31,2,96}
_:expect(no:exists(cond)).is(false)
_:expect(yes:exists(cond)).is(true)
end)
ar.exists = function(t,pred)
for k,v in pairs(t) do
if pred(v) then return true end
end
return false
end
And then, boring …
_:test("exists kv", function()
local cond = function(v) return v==2 end
local no = Dictionary({1,3,5})
local yes = Dictionary{15,31,2,96}
_:expect(no:exists(cond)).is(false)
_:expect(yes:exists(cond)).is(true)
end)
kv.exists = ar.exists
Both tests work. Commit: exists function.
I am becoming bored with the duplicate tests, which there may be no way around, and bored with the little line that copies the function from the ar table to the kv table.
I propose a better design. I propose that we have a common table, fp for the functions that are the same across array and key-value form, and use tables ar and kv only for the ones that are unique to the one or the other. We’ll tell our users to always use ar or kv whichever they mean. The fp table will be our little secret.
I propose to do this by making fp the metatable for both ar and kv.
This is a refactoring, and so the existing tests should tell us that we have it right (or, on the off chance, that we get something wrong).
Here goes:
Meta-meta-table
Here’s the basic setup:
local fp = {}
fp.__index = function(t,k)
return fp[k]
end
ar = {}
setmetatable(ar,fp)
kv = {}
setmetatable(kv,fp)
New table, local to make it a secret. Looks up things in itself if invited to. And set as metatable in ar and kv. Now if, say, ar doesn’t have something, its new metatable’s __index will look in fp.
Now all that should be necessary is to move a definition from ar or kv into fp. The idea will be to move all the ones that are the same across both ar and kv. That’s most of them, but I’ll proceed one at a time.
fp.exists = function(t,pred)
for k,v in pairs(t) do
if pred(v) then return true end
end
return false
end
That replaces the ar and kv ones. Tests run. Continuing ..
filteris different, leave it;mapmoves tofp;- ‘reduce’ moves.
That’s all we have so far. Nice, removes a tiny bit of duplication and a few lines of code. More important, perhaps, is that it may make it a bit more difficult to forget to copy a function. Let’s get back into the Library Trap.
More New Functions …
We have exists, need every:
_:test("every", function()
local even = function(v) return v%2==0 end
local no = Array{2,4,6,7,8}
local yes = Dictionary{two=2,four=4,six=6}
_:expect(no:every(even)).is(false)
_:expect(yes:every(even)).is(true)
end)
fp.every = function(t,pred)
for k,v in pairs(t) do
if not pred(v) then return false end
end
return true
end
OK, one more, a cute one this time, partition. This one will take an input table and a condition and return two tables, the first with all the elements that meet the condition and the second that do not.
_:test("partition KV", function()
local even = function(v) return v%2==0 end
local input = Dictionary{1,2,3,four=4,five=5,six=6}
local yes,no = input:partition(even)
_:expect(yes[1]).is(nil)
_:expect(yes[2]).is(2)
_:expect(yes.four).is(4)
_:expect(yes.six).is(6)
end)
Here, I’m doing the KV version, so there should be no entry for [1] in the output. We could check that more extensively and will, but this is enough to drive out the implementation:
kv.partition = function(t,pred)
local yes = {}
local no = {}
for k,v in pairs(t) do
if pred(v) then
yes[k] = v
else
no[k] = v
end
end
return yes,no
end
Test runs. Let’s make it more complete.
_:test("partition KV", function()
local even = function(v) return v%2==0 end
local input = Dictionary{1,2,3,four=4,five=5,six=6}
local yes,no = input:partition(even)
_:expect(yes[1]).is(nil)
_:expect(yes[2]).is(2)
_:expect(yes.four).is(4)
_:expect(yes.six).is(6)
_:expect(no[1]).is(1)
_:expect(no[3]).is(3)
_:expect(no.five).is(5)
end)
Runs. Commit: kv partition tested.
If we’re going to check whole tables, we should find an easier way to do it. I’ve fiddled with it a bit and don’t have a good idea. Let’s move on and do the array version:
_:test("partition array", function()
local even = function(v) return v%2==0 end
local input = Array{1,2,3,4,5,6}
local yes,no = input:partition(even)
_:expect(yes[1]).is(2)
_:expect(yes[2]).is(4)
_:expect(yes[3]).is(6)
_:expect(no[1]).is(1)
_:expect(no[2]).is(3)
_:expect(no[3]).is(5)
end)
Fails as expected with no partition function for array.
ar.partition = function(t,pred)
local yes = {}
local no = {}
for k,v in pairs(t) do
if pred(v) then
table.insert(yes,v)
else
table.insert(no,v)
end
end
return yes,no
end
Tests run. Commit: Array partition.
I’m tempted to do some more, like subset and maybe even equal. But … let’s not fall too deep into the Library Trap. I do intend to see whether these capabilities are useful in the XST program or maybe even in Dung. We’ll have time to do more if we need to, and now’s a good time to pause. Let’s sum up.
Summary
This whole exercise has gone smoothly, far more smoothly than most things I do here. I don’t think it’s just because this is easy, but the essential ideas are rather atomic and simple, requiring a sort of local kind of thinking, but there’s essentially no interaction between the various functions, which makes our job simpler (and, OK, easier).
There’s a bit of deep or semi-deep knowledge required to do the metatable trick, but I think that has paid off in the ability to treat Lua tables a bit more like first-class objects. We’ll see in upcoming articles whether that simplifies some code, but I suspect it will.
All in all, a perfect exercise. Just enough to fill the mind and keep out the demons for a while, easy enough not to create demons of its own.
Works for me, might work for you. Take care, stay safe, drop in next time!
Update
I took a quick look at XSet2, the extended set theory app I’ve been working on. To my dismay, there really aren’t that many opportunities to use this new capability. There are some tests that look to have promising bits, but most of the code uses both the k and v values of input tables, and as such, the current operations don’t help, because they either ignore the indexes entirely, as in the array operations, or deal with them implicitly.
This is disappointing, because I was hoping for some cool applications of the functional programming stuff. It does kind of prove the “Library Trap” notion, though.
I’ll report more when I know more …