Demystifying monads in Rust through property-based testing
In programming pedagogy, monads have a place as a mystical object from the functional programming world that’s hard to understand and even harder to explain. The stereotype about monad explanations is that they fall into two buckets: either comparisons to some kind of food item , or throwing complex mathematical jargon at you, what’s the problem? But monads aren’t esoteric or magical at all, nor do they only occur in functional programming. In essence, a monad is a design pattern that allows you to chain together operations within a framework. Noticing monadic design can be quite helpful for programmers in any environment, particularly because it’s often undesirable ! In many situations, monads have observable tradeoffs, and sometimes (as here) we can even collect concrete data to back this up. I’m going to try and explain monads in a way that is: In other words, I’m going to try and write the monad tutorial that I personally would have appreciated when I was younger. And I’m going to start at a place that’s unconventional: through property-based testing , where monads have profound performance characteristics. Note: While this article’s primary goal is to explain monads, it also serves as a practical introduction to property-based testing and fault injection techniques. If you’re new to these, you’ll find an introduction to both alongside the monad explanation. This post consists of five sections: Testing is fundamentally about building models for how your code should behave, at just the right level of complexity: they should match the scope of what you’re testing, without going overboard and reinventing the whole system a second time. The best explication of this general idea I’ve seen is in this piece by the great Argentinian writer Jorge Luis Borges : …In that Empire, the Art of Cartography attained such Perfection that the map of a single Province occupied the entirety of a City, and the map of the Empire, the entirety of a Province. In time, those Unconscionable Maps no longer satisfied, and the Cartographers Guilds struck a Map of the Empire whose size was that of the Empire, and which coincided point for point with it…” —On Exactitude in Science , Jorge Luis Borges Nothing quite exemplifies testing-as-modeling like property-based testing—an approach where instead of specifying exact examples, you define models in terms of properties , or invariants, that your code should satisfy. Then, you test your models against randomly generated inputs. Let’s take a simple example of a sort function, say , defined over a slice of integers: How should we go about testing it? The most common way to do this is to list out a bunch of inputs and ensure they are correctly sorted, through example-based tests . Example-based tests are quite valuable, because they are easy to write and quite direct about what happens. But even in a simple example like sorting, it’s easy to imagine cases where your examples don’t quite cover every edge case. How can more edge cases be covered? Well, one way to do so is to step back and ask, what is the sort trying to do? The goal of a sort function is to ensure that all the elements are in ascending order. Can we test that directly? The first thing we’d need is to get some inputs to test with. All we care about is a list of numbers here, which seems like it should be easy to generate using a random number generator. So maybe we write something like: We now have a model of sorting that we’ve written down in code form: any pair of values must be in ascending order. (In this view, example-based tests are also simple models: for input X, the output should be Y.) Now, we run the test, and… Whoops, looks like the function has a bug. (Scroll the above example to the right!) This example is quite unhelpful and hard to understand! It is possible to use this as an input to debug with, but it is quite painful. If we could use automation to turn this test case into a much smaller one that can still reproduce the bug, debugging becomes significantly easier. The process of doing so is called test case shrinking or reduction . To recap—property-based testing consists of two components: What counts as “smaller”? For a list of numbers, ideally we’d be able to minimize both the number of items in the list and the integers themselves. This suggests an algorithm for how to write a shrinker by hand: First, try and minimize the size of the list using a binary search algorithm. For example: Once the list has been shrunk, start shrinking the elements within the list, applying binary search to each element. After you’re done writing this algorithm, you’re well on your way towards creating the original property-based testing library, QuickCheck . This approach has you write two functions: a generator and a shrinker . With this, you can get much more reasonable-looking output: And for relatively simple cases like lists of integers, this kind of shrinking works quite well! But we’re not here to test simple cases. We’re here for the difficult ones. Most real-world sort implementations don’t just work over a list of integers. They’re written to be polymorphic over anything which can be sorted. In Rust parlance, this means anything that implements the trait; and even if not, a custom comparator function can be provided. But can be written by hand, and custom comparators are virtually always written by hand. One immediate consequence is that it’s possible that the comparator function says two elements are equal, but they are actually different. In that case, should the order of elements be preserved? Unstable sorts tend to be faster than stable ones, and there are valid reasons for preferring each at different times. (The Rust standard library has separate implementations for stable and unstable sorts.) Additionally, hand-written implementations mean users can make mistakes ! A production-grade sort algorithm must behave reasonably in the face of arbitrary user input, not just in the actual elements being sorted but also in the comparator function (full credit to Lukas Bergdoll for his extensive research here): Ord safety: Users can write a comparator that’s simply incorrect. An easy way is to introduce a difference between ordering and equality, for example by returning for two elements that are actually equal. Users could also return different answers for the same comparison when called at different times 1 . Panic safety: The comparator can panic in the middle of execution. Since panics can be caught , the input should be in some kind of valid state afterwards. Observation safety: If any of the inputs are mutated by the comparator, those mutations must be carried through to the final output. (With Rust, mutation through shared references is possible via interior mutability , as seen in or ). In these cases, completing the sort successfully becomes impossible. But it’s important that we leave the input in a reasonable state. How do we go about testing this? Trying to think of all the different failure modes seems really hard! But property-based testing can address this need through randomized fault injection . Let’s focus on Ord safety for now, with a comparator that flips around the result 20% of the time: To generate a : And to test this: Our original approach continues to work well—that is, right until the test finds a bug and we need to shrink a failing input. How does one go about writing a shrinker for ? Doing so seemed relatively straightforward for a list of integers. But this is a list where the elements are pairs of an integer and another list . Also: We’ve just tested Ord safety so far—once we’ve added fault injection for other kinds of safety, the complexity seems endless. And even more importantly, there isn’t a great way to compose smaller shrinkers together to form larger ones. Writing shrinkers is a lot of work already, and what’s the point if you have to keep doing all of it over and over? The practical result is that most of the time, writing a shrinker for types like is quite difficult. And writing one is also technically optional, since: All in all, given the choice of writing a shrinker by hand or just moving on with their lives, most developers tend to choose the latter 2 . Because of this, most modern property-based testing frameworks, like proptest in Rust, try and take care of shrinking for you through some notion of integrated shrinking . The idea behind integrated shrinking is: When you generate a random input, you don’t just generate the value itself. You also generate some context that is helpful for reducing the size of the input. The proptest library comes with many different kinds of strategies that can be composed together to create more complex ones. To generate an instance of , we’re going to use two strategies: To generate , we’re going to use , as well as: You might be wondering where all the shrinking code is. It’s actually implemented on the corresponding value trees for each strategy: You can see how the base strategies get turned into successively larger ones through combinators like . It’s very similar to , where you can keep calling , , and so on over and over 3 . In my experience, composability across different scales is where this model shines. You can build bigger strategies out of smaller ones, up to a surprising amount of complexity. This means that your team can invest in a library of ever-more-complex strategies, and continue to derive value out of that library across everything from the smallest of unit tests to large integration tests. But there is one massive wrinkle with integrated shrinking. And that wrinkle is exactly what monads are about. In the previous few sections, we’ve built up all the context we need. We’re now going to look at the fundamental operation that introduces monadic composition to proptest: . In the example above, there’s a function called , which we use to turn a tuple of components into a value. What happens when you try and shrink a value through a ? It’s very simple: So is just a conduit that values pass through: it simply maps a value to another value, and does not change the structure of the value tree in any way. Now let’s say we want to test out pairs of instances, where the way the second is generated depends on the first. This is a situation where we don’t just want to map a value to another value—we need to generate a whole new strategy based on a value. This is a fundamental shift : This is monadic composition in action. The result of one operation controls, at runtime, the entire shape of the next operation. For example, here’s one way to go about generating pairs of s, where the second value is always greater than the first: Your first reaction might be: wow, this seems really powerful . And you would be right! You can write whatever you like in the body of a : In a real and quite rigorous sense, is maximally powerful. Every combinator we’ve talked about, and in fact most of the proptest library, can be written in terms of . So why do all these combinators exist? Why don’t we just use everywhere? The function actually works reasonably well in practice. It generates random values with the right shape, and shrinks them correctly on a failing input. Shrinking is really, really slow. Exponentially slow. Why is that the case? Consider what happens when we want to shrink a value through a . As before: Because generates brand new value trees each time it’s called, shrinking has to be started again, from scratch, each time! This is the essence of monadic composition: powerful, unconstrained, and fundamentally unpredictable . We can measure the impact of monadic composition quite directly, along two related axes: the amount of time it takes to complete iterations, and the number of iterations the shrink completes in. For this post I wrote a small Rust program which collects metrics about shrinking for: With this program, I collected 512 samples on my workstation and analyzed the data. (I ran the program with set to 1 , to mimic typical dev builds in larger Rust projects 4 ). First, the amount of time it took to shrink values down, by key percentile : In this table, p50 represents the median completion time, while p75 and p90 show the times that 75% and 90% of the samples completed within. With , the amount of time scales somewhat linearly as we go from pairs to triples. But with just one additional level of , the performance degrades dramatically, going from under 20 milliseconds to almost 2 seconds! That’s over 100x slower. The difference in the number of iterations is even more striking: From hundreds of iterations to almost a million! And we’re working with pretty simple structures here, too. Just one more level of would make shrinking quite noticeably slow, and another one after that would be disastrous. The data here spans several orders of magnitude. A good way to visualize this kind of data is via a CDF plotted on a logarithmic scale. In these graphs, the x-axis shows the time or iterations, and the y-axis shows the cumulative probability. Curves that are further to the right are worse, and the logarithmic scale reveals that the differences are in orders of magnitude. What makes monadic composition so difficult to deal with? It has to do with the fact, mentioned above, that you can write whatever you like inside the . Because a can contain arbitrary computation inside of it, and that computation returns brand-new strategies, determining how a value will shrink through it is fundamentally unpredictable without actually executing it. In other words, the callback is quite opaque. Why is that? It’s because the callback is written in Rust, which is a powerful, Turing-complete language. It is impossible to fully analyze the semantics of Turing-complete languages 5 . (You might know this as the halting problem , or as Rice’s theorem .) But the fact that some analysis requires solving the halting problem is merely the start of the discussion, not the end of it! There is a rich literature on how to find approximate solutions for problems that are otherwise insoluble due to Rice’s theorem. For shrinking, here are a few approaches that are known to work. One option is to place limits on how long shrinking is done for. Note that has no issues while generating values, just while shrinking them 6 . The proptest library itself sets limits on shrink iterations, particularly across instances . This ensures that shrinking operations finish in a reasonable amount of time, even if they don’t produce minimal values. A better option is to rewrite generators to not use monadic composition . For the example above, it’s not hugely difficult 7 : But this can be quite challenging as complexity goes up! The proptest library comes with a number of helpers to write non-monadic strategies, particularly and . But there are real situations, particularly with large and complex data structures (for example, randomly-generated programming language syntax trees), where none of those options suffice and you have to use the full power of . Last but not least, there’s a set of approaches that I’m going to put into the bucket of rediscovering structure across flat maps. Key to these is understanding that when you generate a random value, you’re turning an RNG, which is a random stream of bits, into concrete, structured values. Can we somehow be clever about looking at the RNG bitstream? One option is to instrument the test , for example by using a fuzzer . Fuzzing is all about generating random data, looking at the branches explored, and tweaking the random data to ensure other branches are taken. It’s a great fit for peering past the black box of monadic composition. Another option is to be clever with random number generator . A random number ultimately generates a sequence of ones and zeroes. Can we poke at this sequence, possibly with the help of some hints from the strategies themselves? This is implemented by the Hypothesis framework for Python ; see this excellent paper about it . Both of these approaches are heuristic and quite complex. But that’s what you need to put together some structure again, after it’s been through the blender of monadic composition. In this article, we looked at monads as a design pattern : a way for a user to compose operations within a framework. We looked at both monadic functions like , and non-monadic ones such as and . Finally, we saw how in the context of property-based testing, monadic composition has a performance impact measured in orders of magnitude. With this knowledge in mind, you can now spot monadic composition in all kinds of other places: Futures in Rust, where is monadic, but futures are awaited sequentially. To run futures concurrently, you have to use non-monadic operations like . Some build systems , where individual build nodes can generate more nodes, making it impossible to generate a dependency graph without running the build. (Cargo is thankfully non-monadic.) And even with iterators, where returns an iterator with the same length as before, and returns an iterator with the same or a smaller length, but the length of is unbounded. , , and all happen to be monadic operations as well, though they’re all simple enough that they don’t have any practical downsides. The common thread through all of these examples is that within a framework, monadic composition is not just from value to value . It is from value to a further instance of that framework . The return value of can result in more futures being spawned, monadic build nodes can generate more build nodes, and turns individual values into iterators. This freedom is what makes monads both the most flexible kind of composition, and the hardest to predict the behavior of. This is part of a general observation throughout programming, whenever there’s an interaction between two parties or two sides. The more restrictions there are on one side, the freer the other side is to do what it likes. Monadic composition is an extreme version of that: the most powerful and least constrained form of composition for the user, but the most difficult to deal with for the framework. Whether you’re a user or a library designer, pay close attention to situations where your operations are monadic. They can provide a great deal of power, perhaps too much in some circumstances. If non-monadic operations are sufficient to help you achieve your goal, prefer them. And when they aren’t enough: well, now you know what you’re getting into! Thanks to Fiona and Cliff Biffle for reviewing drafts of this post. Any mistakes in it are my own. Updated 2025-02-20: Clarified note about Turing completeness to indicate that it is not the composition itself that’s Turing-complete—it’s the language used to write the callback in that’s at issue. This section contains some jargon, but it’s mostly here to satisfy the pedants who will inevitably Ctrl-F for “monad laws”. Please ignore this section if you didn’t get here through a search for that string. Formally speaking, monads are any kind of structure with two operations return and bind , where these operations obey three monad laws . For , these functions would be: For strategies, return is , and bind is . Here are the three monad laws expressed in terms of proptest: Left identity: for any , should be the same as . That is indeed the case, both for generation and for shrinking. Since does not do any shrinking, the pathological behavior doesn’t take effect. Right identity: for any , should be the same as . That is also the case. Every time is shrunk, has to discard the state returned by the dependent strategy. But is a trivial strategy that doesn’t have any state, so it’s effectively a no-op. Associativity: if you have a chain of two s, you can apply the second one either “inside” or “outside” the first one. More specifically, for any , with the definitions: this law requires that and are the same. That’s true as well, both for generation and for shrinking, though the latter is slightly harder to see. One might object by pointing out that in Rust, the above operations result in different types even if they have the same behavior. That is true, but also not particularly relevant, since you can always call to erase the type. One might also point out that we haven’t talked about a typeclass or trait here. That’s a distraction! Monadic composition exists everywhere in programming, regardless of whether the language lets you express as a reified type. You can express in modern versions of Rust via GATs , but there really isn’t much utility to it. Some of these examples might seem far too adversarial to ever be seen in the real world. But an implementation that can handle adversarially bad inputs can also handle inputs that are bad in more benign ways. For production-grade sort functions, it makes sense to design for the worst possible inputs. ↩︎ This is not a moral failing on the part of those developers, because free will doesn’t exist . It’s completely fine, and worth embracing! Integrated shrinking is altering the environment in action. ↩︎ Just like with iterators, the type signatures also become quite long! ↩︎ The default value of , 0, is fine for , but infeasible for with triples. ↩︎ The problem is not specific to Turing-complete languages—it even exists in non-Turing-complete ones. For example, if the callback were written in a language that only had for loops, no while loops , the framework would still not be able to peer past the shrinker. ↩︎ I think this is the key insight that many monad tutorials miss. When writing about monads, it’s tempting to focus on simple examples like , where the monadic behavior doesn’t have significant practical implications. Here, too, if we restrict ourselves to generating values, there’s nothing wrong with . It’s only during shrinking that monadic composition rears its ugly head. If you’re explaining monads to an audience, consider emphasizing not just what monads are, but when their unconstrained power becomes a liability rather than an asset. ↩︎ If you’re playing close attention, you might notice that while this function meets the requirement we set out, the random distribution generated is somewhat different. In this case, it’s possible to get a distribution equivalent to the example through the use of . ↩︎ Geared towards Rust developers , with code samples in Rust, though I hope any sufficiently curious programmer can follow along Free of jargon: no mathematical formalism whatsoever Without analogies of any kind, and grounded in real programming problems Non-trivial: focusing on a production-worthy example with objectively measurable implications Practical: with advice all of us coders can use Property-based testing goes over the basics Drawing the rest of the owl talks about a complex scenario: using property-based testing to inject faults Integrated shrinking shows how to reduce inputs of challenging complexity to smaller sizes Monads, finally is where we introduce monads in this context, and provide data for how costly they can be Rediscovering structure discusses some ways to mitigate the tradeoffs of monads in property-based testing Test case generation using a source of randomness. On failing a test, shrinking it down to a smaller, more understandable size. First, try and minimize the size of the list using a binary search algorithm. For example: Try the first half of the list against the function. If that exhibits an error, attempt to recursively shrink this half. If that doesn’t work, try it with the last half of the list. If neither work or if the list has 1 or fewer elements, move on to the next step. Once the list has been shrunk, start shrinking the elements within the list, applying binary search to each element. A sort implementation which preserves the order is called a stable sort . An implementation which does not is called an unstable sort . Ord safety: Users can write a comparator that’s simply incorrect. An easy way is to introduce a difference between ordering and equality, for example by returning for two elements that are actually equal. Users could also return different answers for the same comparison when called at different times 1 . Panic safety: The comparator can panic in the middle of execution. Since panics can be caught , the input should be in some kind of valid state afterwards. Observation safety: If any of the inputs are mutated by the comparator, those mutations must be carried through to the final output. (With Rust, mutation through shared references is possible via interior mutability , as seen in or ). We’ve just tested Ord safety so far—once we’ve added fault injection for other kinds of safety, the complexity seems endless. And even more importantly, there isn’t a great way to compose smaller shrinkers together to form larger ones. Writing shrinkers is a lot of work already, and what’s the point if you have to keep doing all of it over and over? If the test passes, shrinkers are never invoked. Simply write correct code, and shrinking just isn’t an issue! If the test fails, developers can debug using the original input. It’s painful but possible. In proptest, this combined value and context is called a value tree . Any implementation that accepts a random number generator and turns it into a value tree is called a strategy . The strategy , which “just” returns a single value. The strategy , which generates values from one of a possible list of strategies, where each choice has a given probability. (A function that takes one or more strategies as input, and produces a strategy as its output, is called a combinator .) A range strategy such as , which generates values within the range uniformly at random. The combinator , which accepts a strategy for elements and a size parameter. Range strategies use binary search to make values smaller. The strategy doesn’t do any shrinking, since it just returns a single value. The combinator shrinks towards the beginning of the choices: in this case, is shrunk into . The combinator implements roughly the algorithm in Implementing a manual shrinker above. Attempt to get a smaller value from the underlying value tree. Call the map function on the value. As above, transforms a value into another, but preserves the original structure. This new method, , goes well beyond that. Based on the value generated, it creates a brand new strategy with a structure all of its own. You can conditionally return one strategy or another, reimplementing . You can first generate a size and then return a vector with those many elements, reimplementing the combinator. You can call again, as many times as you like. We would attempt to get a smaller value from the underlying value tree. And then, because we would call the callback to generate a new strategy, we would throw away the previously-generated value tree entirely . The implementations for pairs above, and a non-monadic implementation with (see below) The same for triples: a non-monadic implementation with , and a monadic one with two levels of . One option is to instrument the test , for example by using a fuzzer . Fuzzing is all about generating random data, looking at the branches explored, and tweaking the random data to ensure other branches are taken. It’s a great fit for peering past the black box of monadic composition. Another option is to be clever with random number generator . A random number ultimately generates a sequence of ones and zeroes. Can we poke at this sequence, possibly with the help of some hints from the strategies themselves? This is implemented by the Hypothesis framework for Python ; see this excellent paper about it . Futures in Rust, where is monadic, but futures are awaited sequentially. To run futures concurrently, you have to use non-monadic operations like . Some build systems , where individual build nodes can generate more nodes, making it impossible to generate a dependency graph without running the build. (Cargo is thankfully non-monadic.) And even with iterators, where returns an iterator with the same length as before, and returns an iterator with the same or a smaller length, but the length of is unbounded. , , and all happen to be monadic operations as well, though they’re all simple enough that they don’t have any practical downsides. Left identity: for any , should be the same as . That is indeed the case, both for generation and for shrinking. Since does not do any shrinking, the pathological behavior doesn’t take effect. Right identity: for any , should be the same as . That is also the case. Every time is shrunk, has to discard the state returned by the dependent strategy. But is a trivial strategy that doesn’t have any state, so it’s effectively a no-op. Associativity: if you have a chain of two s, you can apply the second one either “inside” or “outside” the first one. More specifically, for any , with the definitions: this law requires that and are the same. That’s true as well, both for generation and for shrinking, though the latter is slightly harder to see. Some of these examples might seem far too adversarial to ever be seen in the real world. But an implementation that can handle adversarially bad inputs can also handle inputs that are bad in more benign ways. For production-grade sort functions, it makes sense to design for the worst possible inputs. ↩︎ This is not a moral failing on the part of those developers, because free will doesn’t exist . It’s completely fine, and worth embracing! Integrated shrinking is altering the environment in action. ↩︎ Just like with iterators, the type signatures also become quite long! ↩︎ The default value of , 0, is fine for , but infeasible for with triples. ↩︎ The problem is not specific to Turing-complete languages—it even exists in non-Turing-complete ones. For example, if the callback were written in a language that only had for loops, no while loops , the framework would still not be able to peer past the shrinker. ↩︎ I think this is the key insight that many monad tutorials miss. When writing about monads, it’s tempting to focus on simple examples like , where the monadic behavior doesn’t have significant practical implications. Here, too, if we restrict ourselves to generating values, there’s nothing wrong with . It’s only during shrinking that monadic composition rears its ugly head. If you’re explaining monads to an audience, consider emphasizing not just what monads are, but when their unconstrained power becomes a liability rather than an asset. ↩︎ If you’re playing close attention, you might notice that while this function meets the requirement we set out, the random distribution generated is somewhat different. In this case, it’s possible to get a distribution equivalent to the example through the use of . ↩︎
Programming
Open Source
Git
AI
JSON
Database
Rust
Testing
C#
JavaScript
Culture
Python
Tutorial
Philosophy
Shell
Java
C++
Career
Hardware
DevOps
Backend
Scala
Go