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

☞ Reification

☞ Interpreter

But we’re missing &&:

Add && method + ☞ Reification

☞ Interpreter

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! ☝︎