← Contents · Runnable Specifications by Eric Normand · Work in progress · Comments
177
177
Supplement
Composition Lens
In this supplement, we detail various algebraic properties that
are commonly found in operations in real-world domains. Prop-
erties are common compositional structures that we analyze
from domains. For each property, we indicate its mathematical
notation and a notation in code, and an example property-based
test.
You can use this supplement in two ways. Firstly, you can
use it as a reference for the compositional structures to look for
when analyzing a domain. And, secondly, you can use the prop-
erties within as inspiration for your own properties, since the
real-world oen deviates from the clean, mathematical proper-
ties algebraists appreciate. Feel free to modify these properties
as needed.
Properties
Closure Property: nest operations 150
Associative Property: rebalance the call tree 152
Commutative Property: reorder the arguments 154
Mutual commutativity: apply functions in any order 156
Inverse: undo operations 158
Zero or terminal value: stop a calculation early 160
Identity or initial value: where to start a calculation 162
Idempotence: don’t need to keep track of calls 164
Last write wins: forget the past 166
First write wins: ignore the future 168
178 Chapter 6
Closure Property: nest operations
The closure property means that a function returns the same
type as it accepts as arguments. We say a function is closed over
that type. When you have several functions that are closed over
the same type, you can nest them arbitrary. This gives you huge
amounts of expressivity.
Example in math
Many functions in math have the closure property, including ad-
dition and multiplication of integers. However, it is certainly not
all of them. The closure property is what lets you nest arithmetic
expressions:
7a + 8b + c(3 + x) + d(4 + 5y + (2 + zw))
We want to tap into that same expressivity. To do that, you have
to nd a powerful type with good t, organize the domain oper-
ations into layers, and ensure the operations are closed over that
type.
Addition and multiplication close over numbers. Since they
both take numbers as arguments and they return numbers, we
can nest multiplications and additions (and numbers) arbitrarily.
Nesting is a powerful kind of composition because it adds a sec-
ond dimension to sequential composition. Achieving multiple op-
erations closed over the same type will enhance expressivity.
+
+
×
d
c
+
a
b
×
e f
Math notation
f : (A) => A
g : (A, A) => A
Property-based test
This property is not testable. It
is based solely on the types of
the arguments and return val-
ue.
179Composition Lens
Examples in code
In the Composition Lens chapter, we developed the idea of a pre-
senter. The presenter represented anything we could display on
the GUI, from a small component, all the way to the full GUI itself.
We then had operations that combined presenters into composite
presenters, and we built the GUI up by combining basic elements
like images and text.
Presenters
function image(state) //=> HTML
function text(state) //=> HTML
Functions closed over presenters
function frame(presenter) //=> Presenter
function horizontal(presenters) //=> Presenter
function vertical(presenters) //=> Presenter
We could then build GUIs by composing these functions in a nest-
ed way:
let GUI = vertical([
horizontal([
frame(text("Top Left")),
frame(text("Top Right"))
]),
horizontal([
frame(text("Bottom Left")),
frame(text("Bottom Right"))
])
]);
Top Le Top Right
Bottom RightBottom Le
180 Chapter 6
Associative Property: rebalance the call tree
The associative property gives you the exibility to change the or-
der of operations. We cant always control the order. For instance,
if we’re running things in parallel, its hard to control when things
run. If there’s any property that will change your game, its the
associative property.
Example from math
The associative property for addition looks like this:
a + (b + c) = (a + b) + c
Notice that the parentheses change, but the order of a, b, and c do
not. Changing the order of the arguments is the commutative
property.
a
b c
a
b
c
=
associativity makes
these two equivalent
a (b c) (a b) c
Math notation
a (b c) = (a b) c
f(a, f(b, c)) = f(f(a, b), c)
Property-based test
let a = anyString();
let b = anyString();
let c = anyString();
assert(
a + (b + c) ===
(a + b) + c
);
Quick note
Anything with the associative
property has the closure prop-
erty because it has to return
the same type it takes as argu-
ments.
If an operation is associative
and it has an identity, mathe-
maticians call it a monoid.
181Composition Lens
Examples in code
Here are some example operations that have the associative
property:
String concatenation
"Hello" + (", " + "World!") === ("Hello" + ", ") + "World!";
The parentheses don’t matter, but the order of the strings really
does! Because of the associative property, we usually dont write
the parentheses at all:
"Hello" + ", " + "World!"
Combine AddIns
We might make an operation that takes two sets of add-ins and
combines them into one. Here’s the signature:
function combineAddIns(addIns, addIns) //=> AddIns
And here’s the statement of the associative property:
let a = anyAddIns();
let b = anyAddIns();
let c = anyAddIns();
assert(_.isEqual(a.combineAddIns(b).combineAddIns(c),
a.combineAddIns(b.combineAddIns(c))));
associativity lets us rebalance call trees. these two trees
calculate the same thing.
a
b
d
c
a (b (c d))
c
a
b
d
(a b) (c d)
=
182 Chapter 6
Commutative Property: reorder the arguments
Commutativity is a very common property. It’s one that you likely
learned in high school. It means the order of arguments doesn’t
matter.
Why we use it
The commutative property gives us the exibility to change the
argument order while still getting the same answer. There are
many situations where we cant control the order or we want the
order not to matter.
Example in math
One of those situations is when we’re adding numbers. Here is a
statement of the commutativity of addition:
a + b = b + a
a
b
b
a
a b b a
=
Note
Here we’re using inx notation
(where the operation goes be-
tween the arguments) for clari-
ty. We will switch between pre-
x (f(x, y)), inx (x
y), and
dotted notation (x.f().g()),
depending on which one illu-
minates the pattern better.
Math notation
a b = b a
f(a, b) = f(b, a)
Property-based test
let a = anyNumber();
let b = anyNumber();
assert(f(a, b) ===
f(b, a));
183Composition Lens
Example in code
We can write a similar property in JavaScript:
let a = anyNumber();
let b = anyNumber();
assert(a + b === b + a);
We can assert this of any function. Let’s do it for a function called
f() that takes two numbers.
let a = anyNumber();
let b = anyNumber();
assert(f(a, b) === f(b, a));
In our contacts syncing scenario from the Operation Lens chap-
ter, we couldnt control the order that devices connected to the
internet. Regardless of the order, we want to have the same result
at the end. We can express the commutative property like this:
let a = anyContact();
let b = anyContact();
assert(isSameContact(syncContacts(a, b), syncContacts(b, a)));
{
name: "Patricia",
phone: "444-4444"
}
{
name: "Patricia",
phone: "444-4444"
}
{
name: "Patricia",
phone: "444-4444"
}
{
name: "Patricia",
phone: "222-2222"
}
{
name: "Patricia",
phone: "222-2222"
}
old number
new number
syncContacts()
setPhone(patricia, "444-4444")
184 Chapter 6
Mutual commutativity: apply functions in any order
There’s another property called mutual commutativity. It means
that two operations can be called in any order.
Why we use it
Like with the commutative property, we want the exibility to
apply operations in any order. We can’t always control when they
happen (as in what sequence the customer asks for add-ins) but
we want the result to be the same.
Example in math
We can add and subtract numbers in any order and theyll always
come out to the same number. The two operations are plus and
minus.
1 + 3 - 4 - 3 + 2 = 3 - 3 + 2 + 1 - 4
Reordering it gives us the exibility to add and subtract the num-
bers in a convenient order.
Here is the more general formula:
f(g(x)) = g( f(x))
=
f(g(x))
f
x
g
g( f(x))
g
x
f
Property-based test
let x = anyNumber();
assert(f(g(x)) ===
g(f(x)));
Math notation
f(g(x)) = g( f(x))
185Composition Lens
An example in code
Lets start with a simple case:
let coffee = anyCoffee();
let size = anySize();
let roast = anyRoast();
let coffeeSizeFirst = coffee.setSize(size).setRoast(roast);
let coffeeRoastFirst = coffee.setRoast(roast).setSize(size);
assert(sameCoffee(coffeeSizeFirst, coffeeRoastFirst));
We can set the size rst or the roast rst. It doesnt matter.
setSize() and setRoast() are mutually commutative.
We see a special case of this property when were dealing
with the same function with dierent arguments. For example,
we know in our coee order domain, the order we add add-ins
doesn’t matter. We can enforce that with a property:
let coffee = anyCoffee();
let addInA = anyAddIn();
let addInB = anyAddIn();
let coffeeAFirst = coffee.addAddIn(addInA).addAddIn(addInB);
let coffeeBFirst = coffee.addAddIn(addInB).addAddIn(addInA);
assert(sameCoffee(coffeeAFirst, coffeeBFirst));
This may seem very dierent, but it is just another form of the
same property. We can always dene:
let f = coffee => coffee.addAddIn(addInA);
let g = coffee => coffee.addAddIn(addInB);
assert(isSameCoffee(f(g(coffee)), g(f(coffee))));
The assert() has the same form as the mathematical notation above.
I will use dot notation to make it
easier to read
add the add-ins in reverse order
186 Chapter 6
Inverse: undo operations
Some operations “undo” another operation. In that case, we say
that they are inverses. Inverses give you the exibility to go back
and forth, either undoing an operation or moving between rep-
resentations.
Example in math
Increment and decrement are inverses of each other:
a + 1 - 1 = a
a - 1 + 1 = a
We say that two operations are inverses of each other when:
f(g(x)) = x and g(f(y)) = y
But inverses can be one-sided. For example, with integers, divi-
sion is the inverse of multiplication. But multiplication is not the
inverse of division.
3 × 2 = 6, 6 / 2 = 3 but 3 / 2 = 1, 1 × 2 = 2
That is, for integer operations:
i × j / j = i but not i / j × j = i
That’s why we have to check both sides of the inverse, if they exist.
=
f(g(x))
f
x
g
x
x
=
y
y
g( f(y))
g
y
f
Math notation
f(g(x)) = x
g(f(y)) = y
Property-based test
let c = anyCoffee();
let a = anyAddIn();
assert(
_.isEqual(
c.addAddIn(a)
.removeAddIn(a),
c
)
);
Deep question
Is stringify the inverse of
parse? Write out the test for
that. Try to nd cases where
the test passes and cases where
the test fails.
187Composition Lens
Example in code
JSON.parse() is the inverse of JSON.stringify():
let object = anyObject();
let asString = JSON.stringify(object);
let parsed = JSON.parse(asString);
assert(_.isEqual(object, parsed));
In the coee shop orders, removeAddIn() is the inverse of
addAddIn():
let coffee = anyCoffee();
let addIn = anyAddIn();
assert(_.isEqual(coffee.addAddIn(addIn).removeAddIn(addIn),
coffee));
Does the reverse hold? is addAddIn() the inverse of
removeAddIn()? Lets write the test:
let coffee = anyCoffee();
let addIn = anyAddIn();
assert(_.isEqual(coffee.removeAddIn(addIn).addAddIn(addIn),
coffee));
If we can nd a single test case where this doesnt hold, the prop-
erty doesn’t hold. What if coee has no add-ins?
let coffee = { size: "mega", roast: "burnt", addIns: {}};
Now when you remove an add-in, its a no-op (it does nothing).
But when you add the add-in aerwards, then it will have it. The
result will be:
{ size: "mega", roast: "burnt", addIns: { almond: 1 }}
When the coee does not have the add-in, the property does not
hold. But it does hold when it does have the add-in. This means we
can write a partial property:
let coffee = anyCoffee();
let addIn = anyAddIn();
if(coffee.hasAddIn(addIn))
assert(_.isEqual(coffee.removeAddIn(addIn)
.addAddIn(addIn),
coffee));
else assert(true);
We prefer total properties, but
this is probably as good as
you can get for this property.
Another option is to allow for
negative add-ins, which would
allow you to go below zero.
However, I don’t recommend
this because the resulting cof-
fee isn’t meaningful anymore.
What does it mean to have -3
soy milks?
188 Chapter 6
That is, if I have a long list of numbers to multiply, if my interme-
diate result is ever 0, I can stop. There’s no point in continuing
because no matter what I multiply aer a zero, the answer will
still be zero.
5 × 45 × 9 × 7 × 0 × 7 × 2 × 4 × 3 × 100 × ...
z
b
d
c
z (b (c d))
z
=
z
b
d
c
((d c) b) z
z
=
Zero or terminal value: stop a calculation early
Some operations have an end. That is, a value where you know
you can stop.
Example in math
Multiplication has a value that means it’s the end of the calcula-
tion. You know it, but you might not have thought about it as such.
The zero value of multiplication is the number called zero.
Math notation
Le: z a = z
Right: a z = z
Le: f(z, a) = z
Right: f(a, z) = z
Property-based test
// Left
let a = anyNumber();
assert(isNaN(NaN + a));
// Right
let a = anyNumber();
assert(isNaN(a + NaN));
Le zero
0 × a = 0
Right zero
a × 0 = 0
189Composition Lens
Examples in code
JavaScript uses oating point numbers, which have the value
NaN (Not a Number). Once you get a NaN, every operation re-
turns NaN.
let n = anyNumber();
assert(isNaN(NaN + n));
assert(isNaN(n + NaN));
Thats kind of a weird case. Lets try the cartesian product, which
makes pairs of values from two arrays:
function cartesianProduct(as, bs) { //=> Array<Pair<a, b>>
let ret = [];
for(let a of as)
for(let b of bs)
ret.push([a, b]);
return ret;
}
If either of the two arguments is an empty array, then the return
value will also be an empty array:
cartesianProduct([], [1, 2, 3, 4, 5]) //=> []
cartesianProduct([1, 2, 3, 4, 5], []) //=> []
T he emp t y a r r ay is t he le a nd r i g h t z e ro of cartesianProduct():
Le zero
let a = anyArray();
assert(_.isEqual(cartesianProduct([], a), a));
Right zero
let a = anyArray();
assert(_.isEqual(cartesianProduct(a, []), a));
190 Chapter 6
Identity or initial value: where to start a calculation
The identity is an interesting property. It gives you a value to start
with, before youve begun the work. For example, an empty add-
ins set would be the initial value, before you start adding the add-
ins to an order.
Example in math
Where do you start counting or summing from? That is, before
you have begun, what number do you initialize with? Zero, which
is the identity for addition.
The identity, like inverse, has two sides, le and right.
Math notation
Le: i a = a
Right: a i = a
Le: f(i, a) = a
Right: f(a, i) = a
Property-based test
// Left
let a = anyString();
assert("" + a === a);
// Right
let a = anyString();
assert(a + "" === a);
Le identity
0 + a = a
Right identity
a + 0 = a
0 is the identity of addition. What is the identity of multiplication?
Le identity
1 × a = a
Right identity
a × 1 = a
If an operation is associative
and it has an identity, mathe-
maticians call it a monoid.
i
a
i a
a
=
a
i
a i
a
=
191Composition Lens
Le identity
let a = anyString();
assert("" + a === a);
Right identity
let a = anyString();
assert(a + "" === a);
We can use identities to return empty values. For instance, in-
stead of returning null to mean “no answer, we could return
the empty array, which still works ne with the append function.
Identities let you safely and easily represent empty values.
Let’s say you have a billion coee orders to analyze. You want to
know how many coees had soy milk, but there are too many to
go through on one machine. You split up the work among 100 ma-
chines, each machine taking a fraction of the orders. Most ma-
chines will have some soy milk orders, but some, by chance, will
have none. The identity of counting (or adding) is zero, so those
machines with no soy milk orders can return zero, which can
easily be added up like any other number.
It may seem obvious, but we oen forget to account for an identity
when developing our own operations. We might rely on null to
reprsent an empty value, but then the null is not a valid input to
our other operations. Use this property to nd an identity, be-
cause it will simplify your code.
i
b
ic
i (b (c i))
=
b c
b c
Example in code
What is the identity of string concatenation? It is the empty string.
It is both the le and right identity.
192 Chapter 6
Idempotence: don’t need to keep track of calls
Idempotence means that calling a function once yields the same
value as calling it twice or more in composition. For example,
sorting a list twice is the same as sorting it once. The rst time is
important, the second time is a waste.
Idempotent functions give you the exibility to not keep track
of whether youve already called the function. Its safe to call it
again any way.
Example in math
Absolute value, written as |x|, gives you the distance of a number
from zero. But calling it twice is the same as calling it once.
|x| = | |x| |
Dening it this way also means that three or more calls do the
same thing, too.
|x| = | | | x | | |
We can replace the | |x| | with |x| because they are equivalent,
which gives us:
| x | = | | x | |
We can do this with any number of calls to absolute value, reduc-
ing it down to the original equation.
=
f(f(x)) f(x)
f
x
f
x
f
Math notation
f(a) = f(f(a))
Property-based test
let n = anyNumber();
assert(
Math.abs(n) ===
Math.abs(Math.abs(n))
);
193Composition Lens
Example in code
In our coee shop order example, setting the size to a particular
size twice is the same as setting it once:
let coffee = anyCoffee();
let size = anySize();
assert(_.isEqual(coffee.setSize(size),
coffee.setSize(size).setSize(size)));
In practical terms, it allows the barista the exibility to hit the
size button twice without a problem. This is an example of idem-
potency of a calculation.
Imagine another scenario where we need to send emails to our
customers, telling them that the next seasonal avor is coming
out next week. We don’t want to send the same email twice to the
same person. We have several lists:
Our customer list
Our loyalty member list
Our newsletter
We could develop an algorithm to gure out the list of unique
email contacts. However, another option is to use a data structure
that already has an idempotent add operation—the set. When we
add the same value to a set twice, only the rst value is added.
All we have to do then is loop through all of our lists, blindly
calling set.add() for each email in the list. When we’re all done,
we will have a collection of all of our contacts with no duplicates.
194 Chapter 6
Last write wins: forget the past
Last write wins is so common in soware that it is considered the
default. We dont even notice it is there. Every mutable variable
has a last write wins policy: The last value you assign to the vari-
able is the one that it keeps. Values you assign before the last one
are forgotten.
Example in math
Last write wins is similar to idempotency. You could call it a vari-
ation on it. But whereas idempotency calls the same function
twice with the same arguments, last write wins calls the same
function twice but with dierent arguments. The call that hap-
pens second is the one that is kept.
I couldn’t actually think of an example from math, but here’s
how you would express the property:
f(f(a, x), y) = f(a, y)
Notice that the second call (with y as the argument) is the one
thatwins.”
f
a
y
f(a, y)
=
f
y
f(f(a, x), y)
f
a x
Math notation
f(f(a, x), y) = f(a, y)
Property-based test
let v = undened;
let rst = anyNumber();
let last = anyNumber();
v = rst;
v = last;
assert(v === last);
195Composition Lens
Example in code
All of the coee attributes have a last write wins discipline. Here
is the size as an example:
let coffee = anyCoffee();
let rstSize = anySize();
let lastSize = anySize();
assert(_.isEqual(coffee.setSize(rstSize).setSize(lastSize),
coffee.setSize(lastSize)));
You can try it for roast as well.
Because this property is so common, it might be helpful to see
when the property doesn’t hold. It certainly doesnt hold for add-
ing add-ins:
let coffee = anyCoffee();
let rstAddIn = anyAddIn();
let lastAddIn = anyAddIn();
// these are denitely different
coffee.addAddIn(rstAddIn).addAddIn(lastAddIn);
coffee.addAddIn(lastAddIn);
196 Chapter 6
First write wins: ignore the future
We can play with another variation on idempotency called rst
write wins. This is an uncommon one, but its fun to see how far
we can take it. In this variation, the rst time you call a function
is what counts forever. No matter how many times you call that
function on the value later, it has no eect.
Example in math
When you compose a function with itself but with dierent argu-
ments