In this article we are going to take a step beyond natural numbers, and derive a type-level encoding of (positive) rational numbers in Scala. We’ll show how we can leverage natural number arithmetic to perform arithmetical operations on our new type-level rationals, all at compile-time. We’ll start with a quick refresher of how the naturals can be encoded at the type-level, before jumping deeper into some arithmetic using the new rational number types!

Shapeless Nat

Those familiar with the Scala library shapeless may well have come across or used the type Nat , which encodes at the type-level a representation of the…

“Contrariwise,” continued Tweedledee, “if it was so, it might be; and if it were so, it would be; but as it isn’t, it ain’t. That’s logic.” — Lewis Carroll, Through the Looking Glass

As a long-time fan of logic, and a more recent fan of type-level programming, I thought it only proper that I combine the two, and that’s exactly what we’re going to do!

The aim of this project is to codify boolean logic at the type-level in Scala, thus allowing us to evaluate the truth of expressions, and show whether boolean functions are satisfiable or tautological, all at compile-time. And if any of this logical terminology is unfamiliar to you, I hope you will have a better idea by the end.

Getting the language

First, we will build our language of logical expressions. The…

Jack Wheatley

Scala developer and proponent of functional programming

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store