Practical Lensing I

Let's write a lens for flags represented as binary registries.

If you don't know what is a Lens – start here and come back once you get the idea (not necessary all the details).

Wait, what's a Registry? – An efficient way to store boolean flags. Actually the most efficient way you can imagine. A single flag is represented by a single bit(!) (not even byte).

The downside is that your database need to support binary operations if you want to query by flags. Redis allows that and probably some others. Not every programming case is related to DB though.

So while you can store your flags (or tags) as:

{tags: ["foo", "baz"]} // no "bar" and no "qux", get is O(n)

or better as:

{tags: {foo: true, bar: false, baz: false, qux: false}} // get is O(1)

for huge datasets this is A LOT of memory and storage to spend.

We can create named accessors:

const FLAGS1 = {foo: 0x1, bar: 0x2, baz: 0x4, qux: 0x8} // mask-based
const FLAGS2 = {foo: 0, bar: 1, baz: 2, qux: 3}         // offset-based

And use them like:

let rs = {tags: 0b0101} // the registry equivalent to above

console.log(rs.tags & FLAGS1.foo) // 1 -- meh
console.log(rs.tags & FLAGS1.bar) // 0
console.log(rs.tags & FLAGS1.baz) // 4 -- not so good
console.log(rs.tags & FLAGS1.qux) // 0

Add Boolean:

console.log(Boolean(rs & FLAGS1.foo)) // true
console.log(Boolean(rs & FLAGS1.bar)) // false
console.log(Boolean(rs & FLAGS1.baz)) // true
console.log(Boolean(rs & FLAGS1.qux)) // false

Not bad. Arguably it's simple enough. Why bother with lenses?

console.log(Boolean(rs & FLAGS1.quz)) // false @_@ -- see the typo?

Now this is a problem. Because & will implicitly coerce undefined to zero. And there is no way to prevent it except to wrap in accessor:

let getFlag = (key, rs) => {
  return FLAGS2[key] === undefined ? undefined : Boolean(rs & FLAGS2[key])
}

console.log(getFlag("qux", rs)) // false
console.log(getFlag("quz", rs)) // undefined

It works, but it seems we're starting to invent our own ad-hoc "lensing".

Something we were going to avoid... And we didn't even touch the setter part!

So let's see how "Ugly" the real lens will be. We will use novel but already awesome Partial.Lenses library. It's much more powerful then Ramda lenses I used before. Actually it's rather a full-blown Optics library because it comes with Traversals, Transformers and other advanced stuff you might never heard of.

For every new datastructure you need to describe a lens (a lens constructor). It consists of getter and setter. The constructor may accept any number of arguments you want. For our registry we need only one – an index. So it may look like:

let L = require("partial.lenses")

let reg = (i) => L.lens(getReg(i), setReg(i))

Now let's implement getReg and setReg:

let R = require("ramda")

let getReg = R.curry((i, rs) => {
  if (Number.isInteger(i)) {
    return Number.isInteger(rs) ? Boolean(rs & (1 << i)) : undefined
  } else {
    return undefined
  }
})
let setReg = R.curry((i, x, rs) => {
  rs = Number.isInteger(rs) ? rs : 0
  if (Number.isInteger(i)) {
    return x ? (rs | (1 << i)) : (rs & ~(1 << i))
  } else {
    return undefined
  }
})

Remember two options to describe flags we named above as FLAGS1 and FLAGS2? In case you need this explanation - the binary ops we used in setter and getter come from this equivalency:

rs & 0 == rs & (1 << 0)
rs & 1 == rs & (1 << 1)
rs & 2 == rs & (1 << 2)
rs & 4 == rs & (1 << 3)

// =>

rs & FLAGS1.foo == rs & (1 << FLAGS2.foo)
rs & FLAGS1.bar == rs & (1 << FLAGS2.bar)
rs & FLAGS1.baz == rs & (1 << FLAGS2.baz)
rs & FLAGS1.qux == rs & (1 << FLAGS2.qux)

Time for tests:

console.log(L.get(["tags", reg(FLAGS2.foo)], xs)) // true
console.log(L.get(["tags", reg(FLAGS2.bar)], xs)) // false
console.log(L.get(["tags", reg(FLAGS2.baz)], xs)) // true
console.log(L.get(["tags", reg(FLAGS2.qux)], xs)) // false
console.log(L.get(["tags", reg(FLAGS2.quz)], xs)) // undefined

Now compare this to the "dead simple" classic approach:

console.log(rs.tags && Boolean(rs.tags & FLAGS1.foo)) // true
console.log(rs.tags && Boolean(rs.tags & FLAGS1.bar)) // false
console.log(rs.tags && Boolean(rs.tags & FLAGS1.baz)) // true
console.log(rs.tags && Boolean(rs.tags & FLAGS1.qux)) // false
console.log(rs.tags && Boolean(rs.tags & FLAGS1.quz)) // false

The classic one is not only vulnerable to typos in flag names. With those tags being repeated (and we are still ONLY one level deep) our expressions feel terribly fragile.

Let's move further. Our current implementation does not support boundaries. So with hardcoded indexes (though not recommended) it will return false.

console.log(L.get(["tags", reg(42)], xs)) // false

As far as I can tell it's not possible in JS to limit a number to N bits (maybe in WebAssembly...). So our next option is to pass boundary as an argument. With currying it's just +1 line:

let reg = R.curry((size, i) => L.lens(getReg(size, i), setReg(size, i)))
// ... reimplement getter and setter

// drop-in boundaries
reg = reg(0x0000)

// then
console.log(L.get(["tags", reg(42)], xs)) // undefined

Test setters:

// {tags: 0b0101} -> {tags: 0b0100}
console.log(L.set(["tags", reg(FLAGS2.foo)], false, rs)) // {tags: 4}

// {tags: 0b0101} -> {tags: 0b0111}
console.log(L.set(["tags", reg(FLAGS2.bar)], true, rs)) // {tags: 7}

Fine. Let's compare it one-to-one with the classic approach:

console.log(L.set(["tags", reg(FLAGS1.bar)], 1, xs)) // set
console.log(L.set(["tags", reg(FLAGS1.foo)], 0, xs)) // unset

console.log(xs.tags && R.assoc("tags", xs.tags | FLAGS2.bar, xs))  // set
console.log(xs.tags && R.assoc("tags", xs.tags & ~FLAGS2.foo, xs)) // unset

So lensed one is not just shorter. It's value agnostic. You set 1 or 0 in the same way. The classic approach is much more imperative – implementation details continue to emerge and bother us.