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
_:expect(mid).is(3)
_:expect(mid).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
_:expect(mid).is(3)
_:expect(mid).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 `exists` and `every`.

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 ..

• `filter` is different, leave it;
• `map` moves to `fp`;
• ‘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).is(nil)
_:expect(yes).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  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).is(nil)
_:expect(yes).is(2)
_:expect(yes.four).is(4)
_:expect(yes.six).is(6)
_:expect(no).is(1)
_:expect(no).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).is(2)
_:expect(yes).is(4)
_:expect(yes).is(6)
_:expect(no).is(1)
_:expect(no).is(3)
_:expect(no).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 …