Implementing Boolean algebra in Sanctuary with nullary types

In a couple of previous posts, I’ve used “nullary types”, and sort of hand-waved away any explanation of what that actually means.

When we’re dealing with types, some are simply a set of concrete values. Consider the classical Int, Bool, or Char; you have all the information you need to use those types just based on their definitions.

On the other hand, if I had an Array, and in particular if I asked you to start operating on the contents of that array, your first question would probably be “An array of… what, exactly?”

That’s because you’re a good programmer and you recognize that the concept of an array needs to be supplemented with the type of its elements before you can really think meaningfully about it. For example, what if I gave you an array of integers? Well, you could take the summation with a fold, or map them to their string equivalents, or any number of other things that make sense to do with integers.

So we can say that for some types, they are self-complete, like with Int, Bool, and Char. While for other types, they require additional type information before they become whole, like going from talking about Array to talking about Array<Int>.

That’s the difference between Nullary and Unary types. A nullary type requires zero new information to be a complete type. A unary type requires one piece of new information to be a complete type; in our example above, that information is the type of the array elements.

Now that we’re all exhausted…

In order to better demonstrate nullary types (and eventually make our way up to unary types!), let’s consider how we would go about implementing the basic operations of Boolean algebra, from scratch, using Sanctuary.

There are two components to this. First, we’ll need to define the data type itself. Second, we’ll define some functions that operate on that type.

Data Type

If we were working in a statically typed language like Haskell, we might begin by defining a type like this:

data MyBool = T | F

Which is to say our custom Boolean type can have one of only two values, T or F.

The same operation in Sanctuary is somewhat verbose, since it’s a type system built on top of JavaScript. Actually, “frighteningly verbose” would be more accurate:

const MyBool = $.NullaryType
  ('dokidoki-types/MyBool')
  ('http://dokidokidriven.com/types/MyBool')
  ([])
  ((x) => x === 'T' || x === 'F')

Recall that the last argument to the NullaryType function is a function that accepts a value and determines whether that value is part of the type being defined. In our case, the only two available values for MyBool are the strings "T" and "F".

Function signatures

A few functions should be sufficient to emulate the basic operations of Boolean algebra: conjunction (AND), disjunction (OR), and negation (NOT). First, let’s look at the type signature for conjunction as it would look in Haskell:

myAnd :: MyBool -> MyBool -> MyBool

This function will take two Boolean values as arguments, and return a third Boolean value.

In order to say the same thing in Sanctuary, we can use def:

const _myAnd =
  def ('myAnd')
  ({})
  ([MyBool, MyBool, MyBool])

Couple of things to note about this:

• def actually takes a fourth argument that contains the implementation of our function. Since I want to separate our type definitions from our implementations, I’ve leveraged partial application to omit that. We’ll add it later.
• I’ve prepended the name of this variable with an underscore to make it distinct from the eventual implementation. This is admittedly an ad hoc way of doing things, but hey, we’re in JS land. Gotta work with what we’ve got.

Let’s add the two remaining function signatures for disjunction and negation. First in Haskell:

myOr  :: MyBool -> MyBool -> MyBool
myNot :: MyBool -> MyBool

And then in JavaScript:

const _myOr =
  def ('myOr')
  ({})
  ([MyBool, MyBool, MyBool])

const _myNot =
  def ('myNot')
  ({})
  ([MyBool, MyBool])

In case the above is unclear, the disjunction operation (OR) takes two Boolean values and returns a third, while negation (NOT) only needs a single Boolean value, which it negates and returns.

Function implementation

Now for the good stuff. Recall that the rules for Boolean algebra go a little something like this:

// AND
T && T = T
otherwise F

// OR
F || F = F
otherwise T

// NOT
~T = F
~F = T

Because in Haskell we have access to pattern matching, the implementation is nice and clean and we can use it as a reference implementation for when we work in JS. Beginning with conjunction:

myAnd T T = T
myAnd _ _ = F

Because we only have one possible pair of arguments (T and T) for which the result is true, we can define that single case first. The second case then can use the underscore to represent any other value for both arguments; you can think of this pattern, then, as encapsulating the cases T and F; F and T; F and F. For all of these cases, the result is F.

Now for disjunction and negation:

myOr F F = F
myOr _ _ = T

myNot F = T
myNot T = F

And we can run a few quick tests to make sure everything looks sensible:

 > myAnd T F
=> F
 > myOr T F
=> T
 > myNot F
=> T

Cool, that’s Haskell out of the way. Let’s have a look at how we’d define the same three functions using Sanctuary:

const myAnd = _myAnd
  ( a => b => {
    return a === 'T' && b === 'T' ? 'T' : 'F'
})

Recall that above, we used def to create an ad hoc type signature for _myAnd, omitting the final argument / implementation. Now we make the last application of _myAnd to add our actual implementation.

Also recall that we had defined the members of our NullaryType to simply be the single-character strings "T" and "F". For myAnd‘s implementation, then, we simply check if both arguments that have been passed in are "T", and if so, we also return "T". If not, we return "F".

Implementations for myOr and myNot are similar:

const myOr = _myOr
  ( a => b => {
    return a === 'T' || b === 'T' ? 'T' : 'F'
})
const myNot = _myNot
  ( a => {
    return a === 'T' ? 'F' : 'T'
})

And we can fire up a REPL to make sure this has all gone as planned:

> myAnd('T')('T')
'T'
> myOr('F')('F')
'F'
> myNot('T')
'F'

As well as verifying that Sanctuary is checking for values which are not part of our defined type, my trying to negate "W":

> myNot('W')
Thrown:
TypeError: Invalid value

myNot :: dokidoki-types/MyBool -> dokidoki-types/MyBool
         ^^^^^^^^^^^^^^^^^^^^^
                   1
1)  "W" :: String

The value at position 1 is not a member of ‘dokidoki-types/MyBool’.

Which is indeed what we’d expect, since we didn’t include "W" in our set of possible values for MyBool.

Summary

We’ve now got a firm hold of what it means when we’re saying something is a “nullary type”: it is a set of concrete values that requires no additional type information. Example of this are things like Int, Bool, or Char.

We’ve also been able to flex our Sanctuary muscles a bit by re-implementing some Boolean algebra using its nullary type implementation.

Errata

Versions used in this post:

• sanctuary: 2.0.0
• sanctuary-def: 0.20.0
• GHCi, version 8.6.5

Gist for the code in this post