Free Boolean Algebras: Boolean Logic for Free!

Adam Rosien @arosien
Inner Product LLC

2 Apr 2019


My favorite test output


true is not false


(╯°□°)╯︵ ┻━┻

Boolean expressions are everywhere

How do you encode them?

How do you reuse them?

How do you document them?

It’s a mess

What can we do?

Let’s do some refactoring!

Boolean Functions



But we’re missing &&:

Add && method + Reification


Factor Out the Boolean Algebra

How to interpret this algebra?

Structual Recursion

How do we interpret Pure?

Make it the caller’s problem

What did we do?

  • Reify boolean functions into an algebraic data type. Write an interpreter.
  • Add boolean operators: AND, OR, NOT.
  • Separate boolean algebra from domain-specific logic: pure: A => FreeB[A]
  • Augment the boolean algebra with a domain-specific evaluator: run: FreeB[A] => (A => Boolean) => Boolean

FreeB[A] is a boolean algebra for all A!

This is why it is called the Free Boolean Algebra.

Abstracting to Other Boolean Algebras

Can we evaluate an expression to something other than Boolean?

Type Classes

Typelevel algebra provides algebra.lattice.Bool:

FreeB itself has a Bool instance:

We can evaluate FreeB[A] => FreeB[A]!

Other Interpreters

Pretty Printer


Partial Evaluation

And more!

We can evaluate FreeB[A] expressions to:

  • documentation
  • matchers for tests
  • etc.

Take Aways

We can separate boolean expressions from their evaluation with the Free Boolean Algebra.

This a mechanical process. It works for generating other “free” structures: Applicative, Monad, etc.

Once “free”, we can reuse expressions in many different ways.

Thank You!

Adam Rosien @arosien

Inner Product LLC

Hire us to teach your team! ☝︎