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

Defining type-checked functions in Sanctuary

In our previous post, we looked a little about how Sanctuary’s type system works, and created a simple type. We then added that type to Sanctuary’s env, so that it could use our type while type checking.

In order to confirm that everything was working, we tried adding a custom type, FirstType, to the number 42, using Sanctuary’s S.add function. And this was the result:

const x = 42
const s = "dokidoki"

S.add(x)(s)
TypeError: Invalid value

add :: FiniteNumber -> FiniteNumber -> FiniteNumber
                       ^^^^^^^^^^^^
                            1

1) "dokidoki" :: String, FirstType

The value at position 1 is not a member of ‘FiniteNumber’.

Based on the above response, we know two things:

  1. Sanctuary knows about our type, FirstType, as it’s listed in the error message.
  2. S.add ‘s type signature is FiniteNumber -> FiniteNumber -> FiniteNumber

On Type Signatures

If this is your first time encountering this syntax for type signatures, don’t panic! It’s actually pretty easy. The signatures are a list of types separated by arrows. The last item on the list is the return type of the function. Every other type listed is the type of one argument to the function.

Looking back at the signature for S.add:

FiniteNumber -> FiniteNumber -> FiniteNumber

We can see that S.addtakes two FiniteNumbers as arguments, and returns a third FiniteNumber as a result.

Note: Sanctuary’s functions are curried, so saying that S.add takes two arguments is incorrect, strictly speaking. If you’re unfamiliar with this, that’s ok! Go look up “function currying” if you’re curious. It’s not that hard to get your head around. For now though, let’s not get too into the weeds on this.

Bang Bang

While Sanctuary has a swell selection of functions available for us to use, we might want to leverage its typechecker for our own custom functions, just like we were able to do with custom types. For this, we’ll also be using sanctuary-def, just as we did when we made our custom types:

const $ = require('sanctuary-def')

const def = $.create({
  checkTypes: true,
  env: $.env
})

The first thing to do is create a def function. This is a utility function that accepts an environment of types and lets us define custom functions that can typecheck against those types. For our example, we’re going to use sanctuary-def‘s default environment.

As a simple example, let’s define a function that will accept a String, and replace every character in that string with the character !:

const bangBang =
  def ('bangBang')
      ({})
      ([$.String, $.String])
      (xs => {
        return xs
                 // convert the string to an array of chars
                 .split('')
                 // throw away the char and replace it with '!'
                 .map( _x => '!' )
                 // put the array back together into a string
                 .join('')
      })

def takes four arguments:

  1. The name of the function (in this case, bangBang), which will be used when printing type errors to the screen. This doesn’t have to be the same as the name of the variable that you assign the function to.
  2. This object contains any type-variable constraints that you want to impose on your types. This is outside of the scope of this particular article, so for now, we’ll just pass in an empty object.
  3. This is an array of types which essentially serves as our function signature. The signature in a more traditional format would be String -> String. Recall that the last type in a signature is the return type, and everything else is one argument. Our function takes one string as an argument, and returns a string as a result.
  4. Finally, this is the function implementation. For details on how we’re doing the actual character replacement, check out the comments in the code above.

Let’s give a quick test of our function to make sure it’s working correctly:

> console.log(bangBang("all the exclamations"))
!!!!!!!!!!!!!!!!!!!!

Looks good. But we also need to make sure that Sanctuary will typecheck for us. Since our function is expecting a string, let’s pass in a boolean value instead:

> console.log(bangBang(true))
Thrown:
TypeError: Invalid value

bangBang :: String -> String
            ^^^^^^
              1

1)  true :: Boolean
The value at position 1 is not a member of ‘String’.

Sanctuary points to the first type in bangBang‘s type signature, where a String is expected. Instead, it tells us, that we’ve given it a Boolean value, which won’t work. We’ve confirmed that Sanctuary is now doing the heavy lifting of typechecking any argument that we pass in to our function.

One more thing…

We saw above that Sanctuary will typecheck any arguments that we pass to our function. But what happens if our implementation is wrong? What if we tell Sanctuary that we’re going to return a String, but return a Boolean instead? Let’s change our implementation:

const bangBangBad =
  def ('bangBangBad')
      ({})
      ([$.String, $.String])
      (xs => true)

We’re throwing away the String argument xs, and just returning true. And when we try to run this function:

> bangBangBad("hello")
Thrown:
TypeError: Invalid value

bangBangBad :: String -> String
                         ^^^^^^
                           1

1)  true :: Boolean

The value at position 1 is not a member of ‘String’.

Sure enough, now the typechecker is pointing to second type in the signature, where it expects our return value to be of type String, but is instead seeing a Boolean.This tells us that Sanctuary will check both how we use our functions and how we implement them.

Summary

Just as we can define our own types in Sanctuary, we can also define functions and ask the typechecker to make sure our usage and implementations of those functions align with the types we specify.

Errata

Versions used in this post:

  • sanctuary: 1.0.0
  • sanctuary-def: 0.19.0

Gist for the code in this post

Defining Custom Types in Sanctuary

Sanctuary is a functional programming library for JavaScript that provides typechecking and compatibility with the Fantasy Land spec. If all that is a bit unfamiliar to you, never fear! Sanctuary’s docs provide a less esoteric way of describing the library:

Sanctuary promotes programs composed of simple, pure functions. Such programs are easier to comprehend, test, and maintain – they are also a pleasure to write.

Sanctuary lovingly wraps JavaScript in a run-time type system, with support for the usual suspects like Boolean, Int, String, etc. It also has a couple of ADTs like Maybe and Either.

The more I used Sanctuary, the more I started to bump into mentions of the ability to add your own custom types to its type system. Fluture, for example, has a separate repository for this.

I was intrigued. Could I, too, add my own twisted creations to Sanctuary and make it typecheck for me?

Buttering up

A common gripe with vanilla JavaScript is that it’s… a little too nice when it comes to type coercion. For example, I can do this:

const result = 42 + "butter"

and JavaScript will gleefully add a string and an integer value. The result, if you’re morbidly curious, is the string "42butter". This is admittedly a neat trick, and hey, maybe your application’s entire purpose is to add integers to butter! Who am I to get in the way of your business requirements?

The problem is this sort of flexibility can easily lead to unintended consequences as your app begins to get more complicated. Here’s a more subtle example:

const someUser = {
  id: 3,
  name: "Eric",
  email: "me@dokidoki.whatever"
}

const someProduct = {
  id: 123,
  name: "Exciting consumer item!"
}

const updateProductName = 
  (product, newName) => {
    return Object.assign(
      {}, 
      { ...product },
      { name: newName }
    )
}

// pass in user instead of product...
// ... aaaand it works. Kind of.

const newProduct = updateProductName(
  someUser,
  "Suggestive Refrigerator Magnet"
)

What happens here? Well, you end up with an object that looks like this:

{
  id: 3,
  name: 'Suggestive Refrigerator Magnet',
  email: 'me@dokidoki.whatever'
}

So you either have a user who’s profile name is "Suggestive Refrigerator Magnet", or (arguably worse) you’ve got a product with an email field and in incorrect value for id that will almost certainly cause some hard-to-find errors further down the line.

This is where a library like Sanctuary can really help us out, by leveraging a type system to prevent such silly mistakes.

Base type system

Before we get too crazy, let’s look at how Sanctuary’s base type system works. Revisiting our earlier "42butter" example, we will swap out the standard JavaScript + operator for Sanctuary’s S.add function.

// In the Node REPL
> const S = require('sanctuary')
> S.add(42)("butter")

TypeError: Invalid value
 add :: FiniteNumber -> FiniteNumber -> FiniteNumber
  ^^^^^^^^^^^^
  1

 1) "butter" :: String
 The value at position 1 is not a member of ‘FiniteNumber’.

It turns out that “butter”, much as it may want to, cannot become a number. Programming is rife with disappointments.

But this is good news from a type perspective! Whereas the native + operator is unaware of our intentions and so must play fast and loose with types, resulting in weird behavior, S.add will only let us use it if we play by the rules of the type system and give it FiniteNumbers as operators.

FiniteNumber?

Our error message above, in addition to saving us from trying to add numbers to butter, has also given us a peek into one of the types that Sanctuary uses: FiniteNumber. Digging through the source on the Sanctuary repo itself yields references to this only in type signatures and the like. To see the definition itself, we’ll have to look at another repository: sanctuary-def.

sanctuary-def is where the type system itself lives, and where FiniteNumber and friends are actually defined. So in our quest to write our own types, it may be instructive. This is the definition for FiniteNumber:

var FiniteNumber = NullaryTypeWithUrl (
    'sanctuary-def/FiniteNumber',
    function(x) { return ValidNumber._test (x) && isFinite (x); });

That NullaryTypeWithUrl bit looks suspicious. Looking through more of the source, it turns out that’s just a convenience wrapper for the NullaryType function, which shows up in the documentation with the following type signature:

NullaryType :: String -⁠> String -⁠> (Any -⁠> Boolean) -⁠> Type

So FiniteNumber, our type, is created via this NullaryType function. Our arguments to this function are:

  1. String: The name of the type. This is for printing to the console for errors and such.
  2. String: The url of the types documentation
  3. (Any -> Boolean): A function that determines whether or not a value belongs to this type. For example, if this were a type for positive numbers, we would check whether the value was greater than zero and return true if so, or false otherwise.

So really the meat of the thing is the third argument, which is going to allow the type system to tell us whether or not the values we’re using are of the type that it expects.

Defining Our Own Nullary Type

Without getting into the weeds about what exactly is Nullary about this Type, we should be able to use the formula above to create our own type, and get it added to Sanctuary.

Let’s start simple. I want to make a type whose entire membership is only the string "dokidoki".

const $ = require('sanctuary-def')

const FirstType = $.NullaryType
  ('dokidoki-types/FirstType')
  ('http://dokidokidriven.com/types/FirstType')
  ((x) => x === "dokidoki")

Walking through this:

const $ = require('sanctuary-def'): We need sanctuary-def‘s help with this one, so we’ll require it here. Convention is to assign this to a variable named $.

const FirstType = $.NullaryType: We create our type using the NullaryType constructor and assign it to a variable called FirstType

('dokidoki-types/FirstType'): For debugging purposes, we need a string version of the type name. Similar to the above where Sanctuary sort of namespaces its FiniteNumber type under sanctuary-def, we’ll call ours dokidoki-types/FirstType

('http://dokidokidriven.com/types/FirstType'): This is our (fake) URL for the documentation that we will, no doubt, add at our earliest convenience

((x) => x === "dokidoki"): We create a function that determines whether or not any provided argument is contained in our type. In this case, we only want the string "dokidoki", so the function is just a simple string comparison. If the argument is the string "dokidoki", we return true. Otherwise, we return false.

Again, we stated that our entire type is just a single string literal ("dokidoki"). If we attempt to use any other string, or indeed, any other value, Sanctuary will yell at us.

Adding FirstType to Sanctuary’s Environment

Simply creating the type doesn’t actually get us anywhere, since Sanctuary doesn’t know it exists automatically. We need to add the type to Sanctuary’s environment.

env is where all the types live, sort of like the typechecker’s list of valid types. If we load up Sanctuary and then do console.log(S.env), we’ll see a long list of entries like this:

[
...
_Type {
_test: [Function],
format: [Function: format],
keys: [],
name: 'sanctuary-def/FiniteNumber',
type: 'NULLARY',
types: {},
url: 'https://github.com/sanctuary-js/sanctuary-def/tree/v0.18.1#FiniteNumber' },
...
]

Ah ha! There’s our friend FiniteNumber from before! And it’s part of an array of similar entries. Now the question becomes, how do we get our FirstType added to that list?

It turns out that there are a couple of ways to include Sanctuary in our code. The simple way, which we used earlier, is what you’re probably used to seeing with other modules:

const S = require('sanctuary')

Nothing exciting there. But the documentation also mentions a second method:

const { create, env } = require('sanctuary')

const S = create ({
  checkTypes: true,
  env
})

Instead of requiring Sanctuary directly, we’re including two items from the libary: create and… env! After we’ve included those, we call create with two arguments.

The first argument tells Sanctuary whether or not to do run-time typechecking. We want to do that type-checking for our purposes, but if you’re in a production environment, generally this should be set to false for performance reasons.

The second argument is our new buddy env, which is the same env that we printed out before, with FiniteNumber in it. Chances are, if we’re able to add our FirstType to this env, which we established earlier is just an array, we can convince Sanctuary to typecheck for us. The documentation actually gives as an example of this, using the base concat method:

const $ = require('sanctuary-def')
const { create, env } = require('sanctuary')

const FirstType = $.NullaryType
  ('dokidoki-types/FirstType')
  ('http://dokidokidriven.com/types/FirstType')
  ((x) => x === "dokidoki")

const S = create({
  checkTypes: true,
  env: env.concat ([FirstType])
})

Now let’s print out env again and see if we can find FirstType in the list:

[
...
_Type {
_test: [Function],
format: [Function: format],
keys: [],
name: 'dokidoki-types/FirstType',
type: 'NULLARY',
types: {},
url: 'http://dokidokidriven.com/types/FirstType' }
...
]

There it is! It looks a lot like the definition from FiiniteNumber earlier, so it seems this was a success.

One Small Experiment

If Sanctuary is now aware of our FirstType type, it should be able to typecheck for us, right? Let’s revisit our example from before, when we tried to add 42 and "butter". We know that our FirstType is defined to be only the string "dokidoki", so let’s try doing something with that string and see if Sanctuary freaks out:

// In the REPL, with custom env
> S.add(42)("dokidoki")

TypeError: Invalid value
add :: FiniteNumber -> FiniteNumber -> FiniteNumber
^^^^^^^^^^^^
1
1) "dokidoki" :: String, FirstType
The value at position 1 is not a member of ‘FiniteNumber’.

Looks quite similar to our earlier message, with the only exception being the bit I’ve marked in blue: now Sanctuary is aware that the string "dokidoki" can be either of type String or of type FirstType!

Summary

Sanctuary has a run time typechecker that can help us notice when we’re doing something weird in JS, like adding strings and numbers together.

We can also define and add our own types to this type system, and Sanctuary will typecheck those custom types as well.

Errata

Versions used in this post:

  • sanctuary: 0.15.0
  • sanctuary-def: 0.18.1

Gist for the code in this post