Schrödinger's Monad: A Maybe type experiment for Go

October 2018
Reading time: 9 minutes

In the mid 1930’s, physicist Erwin Schrödinger published a thought experiment to critique the seeming-paradoxes in the new science of quantum mechanics.

The “Schrödinger’s Cat” problem imagines a cat locked in a box with a device that might or might not release a poison gas depending on a quantum effect, such as radioactive decay of an atom. According to quantum theory, the atom exists in a “superposition” of decayed and non-decayed states simultaneously until “observed”. Therefore, the cat must be both alive and dead until the box is opened, thus “collapsing” the superposition of possibilities to a single outcome.

To this day, Schrödinger’s Cat continues to illuminate different interpretations of quantum theory, but it also happens to be a great analogy for understanding the Maybe monad.

Monads without jargon 🔗︎

Monads have a reputation as an arcane programming art, partly due to the heavy functional programming jargon that comes with them. For this article, it’s sufficient to know the following:

  • A monad wraps a “context” (e.g. one or more values)
  • A monad can consume a function that operates on the context and returns a new monad. This is often called “binding”.

The Maybe monad represents a computation that might or might not succeed. It’s just like Schrödinger’s box! You put a cat in the box. Things happen to the cat. Eventually, you peek in the box and the cat is either alive or dead.

The trick is this: instead of checking the health of the cat before every operation, you provide a function that assumes a healthy cat, but returns a Schrödinger’s box. If the function succeeded, it puts a new healthy cat in a new box, otherwise it returns the dead-cat box. If the cat was already dead, the function is never applied: once a dead-cat box, always a dead-cat box.

The Maybe monad in Go 🔗︎

Here’s a trivial Maybe monad in Go:

1
2
3
4
5
6
7

package maybe

// X implements the Maybe monad for an empty interface.
type X struct {
	just interface{}
	err  error
}

You can see that the X type has space for a value or an error. Following Maybe monad convention, we call the valid value just and use the empty interface to hold a value of any type.

Let’s give it some constructors:

 8
 9
10
11
12
13
14
15
16

// JustX constructs a valid X from a given empty interface.
func JustX(x interface{}) X {
	return X{just: x}
}

// ErrX constructs an invalid X from a given error.
func ErrX(e error) X {
	return X{err: e}
}

One of the constructors sets the just value, the other the err value. That raises an interesting question: what do we do about the zero value object, where both just and err are nil? It seems natural to conclude that the zero value is invalid, and we can define a method to encapsulate that logic:

17
18
19
20

// IsErr returns true for a zero-value X or an X with an error.
func (m X) IsErr() bool {
	return m.just == nil || m.err != nil
}

Now that we have a way to encapsulate a context and determine validity, let’s look at a binding method to apply a function to the context and get back a new Maybe monad:

21
22
23
24
25
26
27

// Bind applies a function that takes an interface and returns an X.
func (m X) Bind(f func(x interface{}) X) X {
	if m.IsErr() {
		return m
	}
	return f(m.just)
}

If the monad already has an error, Bind shortcuts and returns it rather than applying the function. Otherwise, the function is invoked on the value.

Now that we have a way to construct a Maybe object and mutate it with Bind, we need a way to “open the box” and see if our Maybe cat is alive or dead:

28
29
30
31
32
33
34

// Unbox returns the underlying empty interface value or error.
func (m X) Unbox() (interface{}, error) {
	if m.just == nil && m.err == nil {
		return nil, errors.New("zero-value")
	}
	return m.just, m.err
}

Focusing on the happy path 🔗︎

I was inspired to experiment with the Maybe monad for Go after reading Martin Kühl’s article “Error Handling in Go: Rob Pike Reinvented Monads” and the original Rob Pike article it cited, “Errors are values”.

In short, the Maybe monad provides a technique for avoiding Go’s verbose error handling.

Make no mistake, I think Go’s explicit error handling – returning error values instead of throwing exceptions that unwind the stack – is a good thing and leads to better, safer designs. Unfortunately, checking errors is verbose. Sometimes, verbosity is an acceptable cost for explicit code, but when this verbosity repeats in short sequence, it becomes clutter that obscures the “happy path” of the code and makes it less readable as a result.

Let’s consider an example. Here’s a function that consumes an io.Reader and reads, splits, validates and converts the input to integers before processing it. Each step is factored out to a function, and each could possibly error. For reference, I’ve highlighted the error handling code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func doWork(r io.Reader) error {
    var err error

    in, err := readInput(r)
    if err != nil {
        return fmt.Errorf("error reading input: %s", err.Error())
    }
    xs, err := splitOnWhitespace(in)
    if err != nil {
        return fmt.Errorf("error parsing input: %s", err.Error())
    }
    err = validateData(xs)
    if err != nil {
        return fmt.Errorf("invalid input: %s", err.Error())
    }
    ys, err := convertToInt(xs)
    if err != nil {
        return fmt.Errorf("error transforming data: %s", err.Error())
    }

    // do stuff with ys ...

    return nil
}

Visually, it’s obvious that the bulk of the lines of the function are just handling the “unhappy” path when errors occur. Seeing the “happy path” requires learning to skim over the error handling bits to see the overall flow.

However, if we rewrite this using the Maybe monad, then instead of returning a value and an error to be checked, we only need to return a Maybe monad and keep binding operations to it. At the end, we can see if an error occured anywhere along the chain. Here’s a similar function to the one above, but using a Maybe monad instead of error values. This time, I’ll highlight the “happy path”:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func doWork(r io.Reader) error {
    var err error

    ys, err := readInput(r).
        Bind(splitOnWhitespace).
        Bind(validateData).
        Bind(convertToInt).
        Unbox()

    if err != nil {
        return err
    }

    // do stuff with ys ...

    return nil
}

Now, the “happy path” is the biggest block of code and it’s immediately apparent that doWork is just coordinating a sequence of operations. It’s more readable (at least if you recognize the Maybe monad technique).

Beware the empty interface! 🔗︎

If you were actually reading those code samples, you might have noticed that something went away: the error messages like invalid input: %s. You might also have realized that the binding functions can’t have the same signature or code as in the non-monad example, i.e. validateData in the first examples isn’t the same as validateData in the second example.

The error string isn’t a problem. It just gets pushed into the function and wrapping into a Maybe object there if an error occurs. The bigger problem is the signature:

func validateData(x interface{}) maybe.X

Can you tell this is supposed to consume a slice of strings? Of course not. The empty interface is wonderfully flexible but hides our type information. If we were sure that we’d never call this incorrectly, we could just use a type assertion in it:

func validateData(x interface{}) maybe.X {
    for _, v := range x.([]string) {
        // return maybe.ErrX() if v is invalid
    }
    return maybe.JustX(x)
}

But if we pass in the wrong thing, the function will panic. That’s not good. We could be more defensive and do a type switch on x, with an invalid type also returning a maybe.ErrX(), but we’re losing the simplicity of the binding function.

Using the empty interface for our Maybe monad to work around the lack of generics gives us an unpleasant choice between risk or complexity.

Writing Maybe monads without generics 🔗︎

Without generics or the empty interface, the alternative is to write an explicit Maybe monad for each type we need. For example, a string Maybe:

package maybe

// S implements the Maybe monad for a string
type S struct {
	just string
	err  error
}

// Bind applies a function that takes a string and returns an S.
func (m S) Bind(f func(s string) S) S {
	if m.err != nil {
		return m
	}

	return f(m.just)
}

This is arduous to do by hand for lots of types, but not impossibly so, and it’s a one-time cost for each type to support. It’s also relatively easy to code-generate.

I first experimented with the Maybe monad in Go to simplify some command line processing programs I was writing. These programs read from stdin and emit to stdout. As a result, a lot of my needs revolved around strings, integers and lists of those two types.

One immediate problem I found was type conversion. What if I have a maybe.S and I want to convert it to a maybe.I? (Here, ‘I’ stands for integer.) I really want to overload Bind, but I can’t. Instead, I have to add explicit type conversion methods:

// ToInt applies a function that takes a string and returns an I.
func (m S) ToInt(f func(s string) I) I {
	if m.err != nil {
		return ErrI(m.err)
	}

	return f(m.just)
}

The more I worked with my Maybe library, the more utility methods I found helpful for special cases, such as mapping a function returning a Maybe monad over a slice of values.

Maybe as a Go library 🔗︎

I released my maybe package experiment on GitHub, so if you’re interested, you can read the maybe docs and browse the maybe code.

The README demonstrates a Maybe monad approach to converting slices of strings into slices of non-negative integers. Here are some of the functions that consume typed data and return Maybe monads:

// Function to convert string to maybe.I.  NewI takes a value, err pair.
atoi := func(s string) maybe.I { return maybe.NewI(strconv.Atoi(s)) }

// Function to validate non-negative integer.
validate := func(x int) maybe.I {
	if x < 0 {
		return maybe.ErrI(fmt.Errorf("%d is negative", x))
	}
	return maybe.JustI(x)
}

Given those and a slice of strings, c.data, here’s the monadic conversion:

// Wrap the []string in a maybe type (AoS -> 'Array Of Strings').
strs := maybe.JustAoS(c.data)

// Functionally convert and validate.
nums := strs.ToInt(atoi).Map(validate)

Using the maybe package, the conversion is a declarative series of operations around the “happy path”, still with complete type safety.

Conclusion 🔗︎

Schrödinger’s Cat was a thought experiment – one that posed a ridiculous idea to challenge accepted wisdom.

The Maybe monad for Go is similar. It has some things I like and some drawbacks. You might find it repulsive or you might be intrigued.

Perhaps it needs to wait for the Go generics proposal, or perhaps it’s sufficiently useful already.

Either way, I encourage you to “open the box” and see for yourself.

•      •      •

If you enjoyed this or have feedback, please let me know by or