ploeh blog https://blog.ploeh.dk danish software design en-us Mark Seemann Mon, 06 Oct 2025 07:57:54 UTC Mon, 06 Oct 2025 07:57:54 UTC Shift left on x https://blog.ploeh.dk/2025/10/06/shift-left-on-x/ Mon, 06 Oct 2025 07:57:00 UTC <div id="post"> <p> <em>A difficult task may be easier if done sooner.</em> </p> <p> You've probably seen a figure like this before: </p> <p> <img src="/content/binary/continuous-cost-increse-over-time.png" alt="Graph with time along the x-axis and cost on the y-axis. One curve goes from low cost to high cost as time increases."> </p> <p> The point is that as time passes, the cost of doing something increases. This is often used to explain why test-driven development (TDD) or other agile methods are cost-effective alternatives to a waterfall process. </p> <p> Last time I checked, however, there was scant <a href="/2020/05/25/wheres-the-science">scientific evidence</a> for this curve. </p> <p> Even so, it <em>feels</em> right. If you discover a bug while you write the code, it's much easier to fix it than if it's discovered weeks later. </p> <h3 id="3f639ac506f548949c588767f3860ec3"> Make security easier <a href="#3f639ac506f548949c588767f3860ec3">#</a> </h3> <p> I was recently reminded of the above curve because a customer of mine was struggling with security; mostly authentication and authorization. They asked me if there was a software-engineering practice that could help them get a better handle on security. Since this is a customer who's otherwise quite knowledgeable about agile methods and software engineering, I was a little surprised that they hadn't heard the phrase <em>shift left on security</em>. </p> <p> The idea fits with the above diagram. 'Shifting left' implies moving to the left on the time axis. In other words, do things sooner. Specifically related to security, the idea is to include security concerns early in every software development process. </p> <p> There's little new in this. <a href="/ref/writing-secure-code-2e">Writing Secure Code</a> from 2004 describes how <em>threat modelling</em> is part of secure coding practices. This is something I've had in the back of my mind since reading the book. I also describe the technique and give an example in <a href="/2021/06/14/new-book-code-that-fits-in-your-head">Code That Fits in Your Head</a>. </p> <p> If I know that a system I'm developing requires authentication, some of the first automated acceptance tests I write is one that successfully authenticates against the system, and one or more that fail to do so. Again, the code base that accompanies Code That Fits in Your Head has examples of this. </p> <p> Since my customer's question reminded me of this practice, I began pondering the idea of 'shifting left'. Since it's both touted as a benefit of TDD and DevSecOps, an obvious pattern suggests itself. </p> <h3 id="e23188bbc34f4a0099411bf059ed9d08"> Sufficient requirements <a href="#e23188bbc34f4a0099411bf059ed9d08">#</a> </h3> <p> It's been years since I last drew the above diagram. As I implied, one problem with it is that there seems to be little quantifiable evidence for that relationship. On the other hand, you've surely had the experience that some tasks become harder, the longer you wait. I'll list some example later. </p> <p> While we may not have solid scientific evidence that a cost curve looks like above, it doesn't have to look like that to make shifting left worthwhile. All it takes, really, is that the relationship is non-decreasing, and increases at least once. It doesn't have to be polynomial or exponential; it may be linear or logarithmic. It may even be a non-decreasing <a href="https://en.wikipedia.org/wiki/Step_function">step function</a>, like this: </p> <p> <img src="/content/binary/stepwise-cost-increase-over-time.png" alt="Graph with time along the x-axis and cost on the y-axis. A staircase-shaped figure indicates a stepwise increasing function."> </p> <p> This, as far as I can tell, is a sufficient condition to warrant shifting left on an activity. If you have even <a href="https://martinfowler.com/bliki/AnecdotalEvidence.html">anecdotal evidence</a> that it may be more costly to postpone an activity, do it sooner. In practice, I don't think that you need to wait for solid scientific evidence before you do this. </p> <p> While not quite the same, it's a notion similar to the old agile saw: <em>If it hurts, do it more often.</em> Instead, we may phrase it as: <em>If it gets harder with time, do it sooner.</em> </p> <h3 id="fb9cd07bc9174af39d7dd1be92289408"> Examples <a href="#fb9cd07bc9174af39d7dd1be92289408">#</a> </h3> <p> You've already seen two examples: TDD and security. Are there other examples where tackling problems sooner may decrease cost? Certainly. </p> <p> A few, I cover in <a href="/code-that-fits-in-your-head">Code That Fits in Your Head</a>. The earlier you automate the build process, the easier it is. The earlier you treat all warnings as errors, the easier it is. This seems almost self-explanatory, particularly when it comes to treating warnings as errors. In a brand-new code base, you have no warnings. In that situation, treating warnings as errors is free. When, later, a compiler warning appears, your code doesn't compile, and you're forced to immediately deal with it. At that time, it tends to be much easier to fix the issue, because no other code depends on the code with the warning. </p> <p> A similar situation applies to an automated build. At the beginning, an automated build is a simple batch file with one command. <code>dotnet test -c Release</code>, <code>stack test</code>, <code>py -m pytest</code>, and so on. Later, when you need to deal with databases, security, third-party components, etc. you enhance the automated build 'just in time'. </p> <p> Once you have an automated build, deployment is a small step further. In the beginning, deploying an application is typically as easy as copying some program files (compiled code or source files, depending on language) to the machines on which it's going to run. An exception may be if the deployment target is some sort of app store, with a vetting process that prevents you from deploying a walking skeleton. If, on the other hand, your organization controls the deployment target, the sooner you deploy a hello-world application, the easier it is. </p> <p> Yet another shift-left example is using static code analysis or <a href="https://en.wikipedia.org/wiki/Lint_(software)">linting</a>, particularly when combined with treating warnings as errors. Linters are usually free, and as I describe in Code That Fits in Your Head, I've always found it irrational that teams don't use them. Not that I don't understand the mechanism, because if you only turn them on at a time when the code base has already accumulated thousands of linter issues, the sheer volume is overwhelming. </p> <p> Closely related to this discussion is the <a href="/2023/01/23/agilean">lean development notion that bugs are stop-the-line issues</a>. The correct number of known bugs in the code base is zero. The correct number of unhandled exceptions in production is zero. This sounds unattainable to most people, but is possible if you shift left on managing defects. </p> <p> In short: </p> <ul> <li>Shift left on security</li> <li>Shift left on testing</li> <li>Shift left on treating warnings as errors</li> <li>Shift left on automated builds</li> <li>Shift left on deployment</li> <li>Shift left on linting</li> <li>Shift left on defect management</li> </ul> <p> This list is hardly exhaustive. </p> <h3 id="a20b501150c34db585453d9009f582db"> Shift right <a href="#a20b501150c34db585453d9009f582db">#</a> </h3> <p> While it increases your productivity to do some things sooner, it's not a universal rule. Some things <a href="/2025/02/17/in-defence-of-multiple-wip">become easier, the longer you wait</a>. In terms of time-to-cost curves, this happens whenever the curve is decreasing, even if only step-wise. </p> <p> <img src="/content/binary/stepwise-cost-decrease-over-time.png" alt="Graph with time along the x-axis and cost on the y-axis. A staircase-shaped figure indicates a stepwise decreasing function."> </p> <p> The danger of these figures is that they may give the impression of a deterministic process. That need not be the case, but if you have reason to believe that waiting until later may make solving a problem easier, consider waiting. The notion of waiting until <a href="https://blog.codinghorror.com/the-last-responsible-moment/">the last responsible moment</a> is central to <a href="/2023/01/23/agilean">lean or agile software development</a>. </p> <p> In a sense, you could view this is 'shifting right' on certain tasks. More than once I've experienced that if you wait long enough with a certain task, it becomes irrelevant. Not just easier to perform, but something that you don't need to do at all. What looked like a requirement early on turned out to be not at all what the customer or user wanted, after all. </p> <h3 id="383b2c22a408406a91c17a11ed0bdbec"> When to do what <a href="#383b2c22a408406a91c17a11ed0bdbec">#</a> </h3> <p> How do you distinguish? How do you decide if shifting left or shifting right is more appropriate? In practice, it's rarely difficult. The shift-left list above contains the usual suspects. While the list may not be exhaustive, it's a well-known list of practices that countless teams have found easier to do sooner rather than later. </p> <p> My own inclination would be to treat most other things as tasks that are better postponed. After all, you can't do <em>everything</em> as the <em>first</em> thing. Naturally, there has to be some sequencing of tasks. </p> <p> Thinking about such decisions in terms of time-cost curves feels natural to me. I find it an easy framework to consider whether I should shift left or right on some activity. </p> <h3 id="e5d50d3f31474bae91782e6623a48a8f"> Conclusion <a href="#e5d50d3f31474bae91782e6623a48a8f">#</a> </h3> <p> Some things are easier if you get started as soon as possible. Candidates include testing, deployment, security, and defect management. This is the case when there's a increasing relationship between time and cost. This relationship need not be a quantified function. Often, you can get by with a sense that 'if I do this now, it's going to be easy; if I wait, it's going to be harder.' </p> <p> Conversely, some things are better postponed to the last responsible moment. This happens if the relation between time and cost is decreasing. </p> <p> Perhaps we can simplify this analysis even further. Perhaps you don't even need to think of (step) functions. All you may need is to consider the <a href="https://en.wikipedia.org/wiki/Partially_ordered_set">partial order</a> of tasks in terms of cost. Since I'm a visual thinker, however, increasing and decreasing functions come more naturally to me. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/10/06/shift-left-on-x Composing pure Haskell assertions https://blog.ploeh.dk/2025/09/29/composing-pure-haskell-assertions/ Mon, 29 Sep 2025 07:43:00 UTC <div id="post"> <p> <em>With HUnit and QuickCheck examples.</em> </p> <p> A question had been in the back of my mind for a long time, but I always got caught up in something seemingly more important, so I didn't get around to investigate until recently. It's simply this: </p> <p> How do you compose <a href="https://en.wikipedia.org/wiki/Pure_function">pure</a> assertions in <a href="https://hackage.haskell.org/package/HUnit/docs/Test-HUnit.html">HUnit</a> or <a href="https://hackage-content.haskell.org/package/QuickCheck/docs/Test-QuickCheck.html">QuickCheck</a>? </p> <p> Let me explain what I mean, and why this isn't quite as straightforward as it may sound. </p> <h3 id="76d1bda9793e4f5c810f387c09fc8324"> Assertions as statements <a href="#76d1bda9793e4f5c810f387c09fc8324">#</a> </h3> <p> What do I mean by <em>composing</em> assertions? Really nothing more than wanting to verify more than a single outcome of a test. </p> <p> If you're used to writing test assertions in imperative languages like C#, <a href="https://www.java.com/">Java</a>, <a href="https://www.python.org/">Python</a>, or JavaScript, you think nothing of it. Just write an assertion on one line, and the next assertion on the next line. </p> <p> If you're writing impure <a href="https://www.haskell.org/">Haskell</a>, you can also do that. </p> <p> <pre><span style="color:#a31515;">&quot;CLRS&nbsp;example&quot;</span>&nbsp;~:&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:#2b91af;">p</span>&nbsp;<span style="color:blue;">::</span>&nbsp;<span style="color:blue;">IOArray</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;newListArray&nbsp;(1,&nbsp;10)&nbsp;[1,&nbsp;5,&nbsp;8,&nbsp;9,&nbsp;10,&nbsp;17,&nbsp;17,&nbsp;20,&nbsp;24,&nbsp;30] &nbsp;&nbsp;(r,&nbsp;s)&nbsp;&lt;-&nbsp;cutRod&nbsp;p&nbsp;10 &nbsp;&nbsp;actualRevenue&nbsp;&lt;-&nbsp;getElems&nbsp;r &nbsp;&nbsp;actualSizes&nbsp;&lt;-&nbsp;getElems&nbsp;s &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;expectedRevenue&nbsp;=&nbsp;[0,&nbsp;1,&nbsp;5,&nbsp;8,&nbsp;10,&nbsp;13,&nbsp;17,&nbsp;18,&nbsp;22,&nbsp;25,&nbsp;30] &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;expectedSizes&nbsp;=&nbsp;[1,&nbsp;2,&nbsp;3,&nbsp;2,&nbsp;2,&nbsp;6,&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;10] &nbsp;&nbsp;expectedRevenue&nbsp;@=?&nbsp;actualRevenue &nbsp;&nbsp;expectedSizes&nbsp;@=?&nbsp;actualSizes</pre> </p> <p> This example is an <a href="/2018/05/07/inlined-hunit-test-lists">inlined HUnit test</a> which tests the <a href="/2025/09/08/io-is-special">impure cutRod variation</a>. The two final statements are assertions that use the <a href="https://hackage.haskell.org/package/HUnit/docs/Test-HUnit-Base.html#v:-64--61--63-">@=?</a> assertion operator. The value on the left side is the expected value, and to the right goes the actual value. This operator returns a type called <code>Assertion</code>, which <a href="https://hackage.haskell.org/package/HUnit/docs/Test-HUnit-Base.html#t:Assertion">turns out</a> to be nothing but an alias for <code>IO ()</code>. </p> <p> In other words, those assertions are impure actions, and they work similarly to assertions in imperative languages. If the actual value passes the assertion, nothing happens and execution moves on to the assertion on the next line. If, on the other hand, the assertion fails, execution short-circuits, and an error is reported. </p> <p> Imperative languages typically throw exceptions to achieve that behaviour. Even <a href="https://github.com/SwensenSoftware/unquote">Unquote</a> does this. Exactly how HUnit does it I don't know; I haven't looked under the hood. </p> <p> You can do the same with <a href="https://hackage-content.haskell.org/package/QuickCheck/docs/Test-QuickCheck-Monadic.html">Test.QuickCheck.Monadic</a>: </p> <p> <pre>testProperty&nbsp;<span style="color:#a31515;">&quot;cutRod&nbsp;returns&nbsp;correct&nbsp;arrays&quot;</span>&nbsp;$&nbsp;\&nbsp;p&nbsp;-&gt;&nbsp;monadicIO&nbsp;$&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;n&nbsp;=&nbsp;<span style="color:blue;">length</span>&nbsp;p &nbsp;&nbsp;<span style="color:#2b91af;">p&#39;</span>&nbsp;<span style="color:blue;">::</span>&nbsp;<span style="color:blue;">IOArray</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;&lt;-&nbsp;run&nbsp;$&nbsp;newListArray&nbsp;(1,&nbsp;n)&nbsp;p &nbsp;&nbsp;(r,&nbsp;s)&nbsp;::&nbsp;(IOArray&nbsp;Int&nbsp;Int,&nbsp;IOArray&nbsp;Int&nbsp;Int)&nbsp;&lt;-&nbsp;run&nbsp;$&nbsp;cutRod&nbsp;p&#39;&nbsp;n &nbsp;&nbsp;actualRevenue&nbsp;&lt;-&nbsp;run&nbsp;$&nbsp;getElems&nbsp;r &nbsp;&nbsp;actualSizes&nbsp;&lt;-&nbsp;run&nbsp;$&nbsp;getElems&nbsp;s &nbsp;&nbsp;assertWith&nbsp;(<span style="color:blue;">length</span>&nbsp;actualRevenue&nbsp;==&nbsp;n&nbsp;+&nbsp;1)&nbsp;<span style="color:#a31515;">&quot;Revenue&nbsp;length&nbsp;is&nbsp;incorrect&quot;</span> &nbsp;&nbsp;assertWith&nbsp;(<span style="color:blue;">length</span>&nbsp;actualSizes&nbsp;==&nbsp;n)&nbsp;<span style="color:#a31515;">&quot;Size&nbsp;length&nbsp;is&nbsp;incorrect&quot;</span> &nbsp;&nbsp;assertWith&nbsp;(<span style="color:blue;">all</span>&nbsp;(\i&nbsp;-&gt;&nbsp;0&nbsp;&lt;=&nbsp;i&nbsp;&amp;&amp;&nbsp;i&nbsp;&lt;=&nbsp;n)&nbsp;actualSizes)&nbsp;<span style="color:#a31515;">&quot;Sizes&nbsp;are&nbsp;not&nbsp;all&nbsp;in&nbsp;[1..n]&quot;</span></pre> </p> <p> Like the previous example, you can repeatedly call <code>assertWith</code>, since this action, too, is a statement that returns no value. </p> <p> So far, so good. </p> <h3 id="7321a1e253aa47b9a005ffc313729bf2"> Composing assertions <a href="#7321a1e253aa47b9a005ffc313729bf2">#</a> </h3> <p> What if, however, you want to write tests as pure functions? </p> <p> Pure functions are composed from expressions, while statements aren't allowed (or, at least, ineffective, and subject to be optimized away by a compiler). In other words, the above strategy isn't going to work. If you want to write more than one assertion, you need to figure out how they compose. </p> <p> The naive answer might be to use <a href="https://en.wikipedia.org/wiki/Logical_conjunction">logical conjunction</a> (AKA Boolean <em>and</em>). Write one assertion as a Boolean expression, another assertion as another Boolean expression, and just compose them using the standard 'and' operator. In Haskell, that would be <code>&&</code>. </p> <p> This works to a fashion, but has a major drawback. If such a composed assertion fails, it doesn't tell you why. All you know is that the entire Boolean expression evaluated to <code>False</code>. </p> <p> This is the reason that most testing libraries come with explicit assertion APIs. In HUnit, you may wish to use the <a href="https://hackage.haskell.org/package/HUnit/docs/Test-HUnit-Base.html#v:-126--61--63-">~=?</a> operator, and in QuickCheck the <a href="https://hackage-content.haskell.org/package/QuickCheck/docs/Test-QuickCheck.html#v:-61--61--61-">===</a> operator. </p> <p> The question, however, is how they compose. Ideally, <a href="/2022/11/07/applicative-assertions">assertions should compose applicatively</a>, but I've never seen that in the wild. If not, look for a <a href="/2017/10/06/monoids">monoid</a>, or at least a <a href="/2017/11/27/semigroups">semigroup</a>. </p> <p> Let's do that for both HUnit and QuickCheck. </p> <h3 id="5e1c9efb4ff841d8a588e01920eab8d2"> Composing HUnit assertions <a href="#5e1c9efb4ff841d8a588e01920eab8d2">#</a> </h3> <p> My favourite HUnit assertion is the <code>~=?</code> operator, which has the (simplified) type <code>a &gt; a -&gt; Test</code>. In other words, an expression like <code>expectedRevenue&nbsp;~=?&nbsp;actualRevenue</code> has the type <code>Test</code>. The question, then, is: How does <code>Test</code> compose? </p> <p> Not <em>that</em> well, I'm afraid, but I find the following workable. You can compose one or more <code>Test</code> values with the <a href="https://hackage.haskell.org/package/HUnit/docs/Test-HUnit-Base.html#v:TestList">TestList</a> constructor, but if you're already using the <a href="https://hackage.haskell.org/package/HUnit/docs/Test-HUnit-Base.html#v:-126-:">~:</a> operator, as I usually do (see below), then you just need a <code>Testable</code> instance, and it turns out that a list of <code>Testable</code> values is itself a <code>Testable</code> instance. This means that you can write a pure unit test and compose <code>~=?</code> like this: </p> <p> <pre><span style="color:#a31515;">&quot;CLRS&nbsp;example&quot;</span>&nbsp;~: &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;p&nbsp;=&nbsp;[0,&nbsp;1,&nbsp;5,&nbsp;8,&nbsp;9,&nbsp;10,&nbsp;17,&nbsp;17,&nbsp;20,&nbsp;24,&nbsp;30]&nbsp;::&nbsp;[Int] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(r,&nbsp;s)&nbsp;=&nbsp;cutRod&nbsp;p&nbsp;10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;actualRevenue&nbsp;=&nbsp;Map.elems&nbsp;r &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;actualSizes&nbsp;=&nbsp;Map.elems&nbsp;s &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expectedRevenue&nbsp;=&nbsp;[0,&nbsp;1,&nbsp;5,&nbsp;8,&nbsp;10,&nbsp;13,&nbsp;17,&nbsp;18,&nbsp;22,&nbsp;25,&nbsp;30] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expectedSizes&nbsp;=&nbsp;[1,&nbsp;2,&nbsp;3,&nbsp;2,&nbsp;2,&nbsp;6,&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;10] &nbsp;&nbsp;<span style="color:blue;">in</span>&nbsp;[expectedRevenue&nbsp;~=?&nbsp;actualRevenue, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;expectedSizes&nbsp;~=?&nbsp;actualSizes]</pre> </p> <p> This is a refactoring of the above test, now as a pure function, because it tests the pure variation of <code>cutRod</code>. Notice that the two assertions are simply returned as a list. </p> <p> While this has enough syntactical elegance to satisfy me, it does have the disadvantage that it actually creates <em>two</em> test cases. One that runs with the first assertion, and one that executes with the second: </p> <p> <pre>:CLRS example: : [<span style="color: green;">OK</span>] : [<span style="color: green;">OK</span>]</pre> </p> <p> In most cases this is unlikely to be a problem, but it could be if the test performs a resource-intensive computation. Each assertion you add makes it run one more time. </p> <p> A test like the one shown here is so 'small' that this is rarely much of an issue. On the other hand, a property-based testing library might stress a System Under Test more, so fortunately, QuickCheck assertions compose better than HUnit assertions. </p> <h3 id="63d7b7bb1e7a4155afe8f318c5f91fb5"> Composing QuickCheck assertions <a href="#63d7b7bb1e7a4155afe8f318c5f91fb5">#</a> </h3> <p> The <code>===</code> operator has the (simplified) type <code>a -&gt; a -&gt; Property</code>. <a href="https://hoogle.haskell.org/">Hoogling</a> for a combinator with the type <code>Property -&gt; Property -&gt; Property</code> doesn't reveal anything useful, but fortunately it turns out that for running QuickCheck properties, all you really need is a <code>Testable</code> instance (not the same <code>Testable</code> as HUnit defines). And lo and behold! The <a href="https://hackage-content.haskell.org/package/QuickCheck/docs/Test-QuickCheck.html#v:.-38--38-.">.&amp;&amp;.</a> operator is just what we need. That, or the <a href="https://hackage-content.haskell.org/package/QuickCheck/docs/Test-QuickCheck.html#v:conjoin">conjoin</a> function, if you have more than two assertions to combine, as in this example: </p> <p> <pre>testProperty&nbsp;<span style="color:#a31515;">&quot;cutRod&nbsp;returns&nbsp;correct&nbsp;arrays&quot;</span>&nbsp;$&nbsp;\&nbsp;p&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;n&nbsp;=&nbsp;<span style="color:blue;">length</span>&nbsp;p &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;p&#39;&nbsp;=&nbsp;0&nbsp;:&nbsp;p&nbsp;&nbsp;<span style="color:green;">--&nbsp;Ensure&nbsp;the&nbsp;first&nbsp;element&nbsp;is&nbsp;0 </span> &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;(r,&nbsp;s)&nbsp;::&nbsp;(Map&nbsp;Int&nbsp;Int,&nbsp;Map&nbsp;Int&nbsp;Int)&nbsp;=&nbsp;cutRod&nbsp;p&#39;&nbsp;n &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actualRevenue&nbsp;=&nbsp;Map.elems&nbsp;r &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actualSizes&nbsp;=&nbsp;Map.elems&nbsp;s &nbsp;&nbsp;conjoin&nbsp;[ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">length</span>&nbsp;actualRevenue&nbsp;===&nbsp;n&nbsp;+&nbsp;1, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">length</span>&nbsp;actualSizes&nbsp;===&nbsp;n, &nbsp;&nbsp;&nbsp;&nbsp;counterexample&nbsp;<span style="color:#a31515;">&quot;Sizes&nbsp;are&nbsp;not&nbsp;all&nbsp;in&nbsp;[0..n]&quot;</span>&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">all</span>&nbsp;(\i&nbsp;-&gt;&nbsp;0&nbsp;&lt;=&nbsp;i&nbsp;&amp;&amp;&nbsp;i&nbsp;&lt;=&nbsp;n)&nbsp;actualSizes&nbsp;]</pre> </p> <p> The <code>.&amp;&amp;.</code> operator is actually a bit more flexible than <code>conjoin</code>, but due to operator precedence and indentation rules, trying to chain those three assertions with <code>.&amp;&amp;.</code> is less elegant than using <code>conjoin</code>. In this case. </p> <h3 id="4d2bfeaad380487196478b194c9b840c"> Conclusion <a href="#4d2bfeaad380487196478b194c9b840c">#</a> </h3> <p> In imperative languages, composing test assertions is as simple as writing one assertion after another. Since assertions are statements, and imperative languages allow you to sequence statements, this is such a trivial way to compose assertions that you've probably never given it much thought. </p> <p> Pure programs, however, are not composed from statements, but rather from expressions. A pure assertion is an expression that returns a value, so if you want to compose two or more pure assertions, you need to figure out how to compose the values that the assertions return. </p> <p> Ideally, assertions should compose as <a href="/2018/10/01/applicative-functors">applicative functors</a>, but they rarely do. Instead, you'll have to go looking for combinators that enable you to combine two or more of a test library's built-in assertions. In this article, you've seen how to compose assertions in HUnit and QuickCheck. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/09/29/composing-pure-haskell-assertions It's striking so quickly the industry forgets that lines of code isn't a measure of productivity https://blog.ploeh.dk/2025/09/22/its-striking-so-quickly-the-industry-forgets-that-lines-of-code-isnt-a-measure-of-productivity/ Mon, 22 Sep 2025 06:52:00 UTC <div id="post"> <p> <em>Code is a liability, not an asset.</em> </p> <p> It's not a new idea that the more source code you have, the greater the maintenance burden. Dijkstra already touched on this topic in his Turing Award lecture in 1972, and later wrote, </p> <blockquote> <p> "if we wish to count lines of code, we should not regard them as "lines produced" but as "lines spent"" </p> <footer><cite>On the cruelty of really teaching computing science</cite>, Edsger W. Dijkstra, 1988</footer> </blockquote> <p> He went on to note that </p> <blockquote> <p> "the current conventional wisdom is so foolish as to book that count on the wrong side of the ledger." </p> <footer><cite>On the cruelty of really teaching computing science</cite>, Edsger W. Dijkstra, 1988</footer> </blockquote> <p> The use of the word <em>ledger</em> suggests an accounting perspective that was later also adopted by Tim Ottinger, who observed that <a href="https://blog.objectmentor.com/articles/2007/04/16/code-is-a-liability">Code is a Liability</a>. </p> <p> The entire premise of my book <a href="/2021/06/14/new-book-code-that-fits-in-your-head">Code That Fits in Your Head</a> is also that the more code you have, the harder it becomes to evolve and maintain the code base. </p> <p> Even so, it seems to me that, once more, most of the software industry is equating the ability to spew out as much code as fast as possible with productivity. My guess is that some people are in for a rude awakening in a couple of years. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/09/22/its-striking-so-quickly-the-industry-forgets-that-lines-of-code-isnt-a-measure-of-productivity Greyscale-box test-driven development https://blog.ploeh.dk/2025/09/15/greyscale-box-test-driven-development/ Mon, 15 Sep 2025 18:45:00 UTC <div id="post"> <p> <em>Is TDD white-box testing or black-box testing?</em> </p> <p> Surely you're aware of the terms <a href="https://en.wikipedia.org/wiki/Black-box_testing">black-box testing</a> and <a href="https://en.wikipedia.org/wiki/White-box_testing">white-box testing</a>, but have you ever wondered where test-driven development (TDD) fits in that picture? </p> <p> The short answer is that TDD as a software development practice sits somewhere between the two. It really isn't black and white, and exactly where TDD sits on the spectrum changes with circumstances. </p> <p> <img src="/content/binary/greyscale-tdd-spectrum.png" alt="Black-box testing to the left, white-box testing to the right, with four grey boxes of varying greyscales in between, all four labeled TDD."> </p> <p> If the above diagram indicates that TDD can't occupy the space of undiluted black- or white-box testing, that's not my intent. In my experience, however, you rarely do neither when you engage with the TDD process. Rather, you find yourself somewhere in-between. </p> <p> In the following, I'll examine the two extremes in order to explain why TDD rarely leads to either, starting with black-box testing. </p> <h3 id="7b6ff977cede461f9c859e55e2aa24c9"> Compartmentalization of knowledge <a href="#7b6ff977cede461f9c859e55e2aa24c9">#</a> </h3> <p> If you follow the usual <a href="/2019/10/21/a-red-green-refactor-checklist">red-green-refactor</a> checklist, you write test code and production code in tight loops. You write some test code, some production code, more test code, then more production code, and so on. </p> <p> If you're working by yourself, at least, that makes it almost impossible to treat the System Under Test (SUT) as a black box. After all, you're also the one who writes the production code. </p> <p> You can try to 'forget' the production code you just wrote whenever you circle back to writing another test, but in practice, you can't. Even so, it may still be a useful <a href="/2020/01/13/on-doing-katas">exercise</a>. I call this technique <em>Gollum style</em> (originally introduced in the Pluralsight course <a href="/outside-in-tdd">Outside-In Test-Driven Development</a> as a variation on the <a href="/2019/10/07/devils-advocate">Devil's advocate</a> technique). The idea is to assume two roles, and to explicitly distinguish the goals of the tester from the aims of the implementer. </p> <p> Still, while this can be an illuminating exercise, I don't pretend that this is truly black-box testing. </p> <h3 id="6c9dfbef5e974355802d4548b0d6e146"> Pair programming <a href="#6c9dfbef5e974355802d4548b0d6e146">#</a> </h3> <p> If you pair-program, you have better options. You <em>could</em> have one person write a test, and another person implement the code to pass the test. I could imagine a setup where the tester can't see the production code. Although I've never seen or heard about anyone doing that, this would get close to true black-box TDD. </p> <p> To demonstrate, imagine a team doing the <a href="https://codingdojo.org/kata/FizzBuzz/">FizzBuzz kata</a> in this way. The tester writes the first test: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="font-weight:bold;color:#74531f;">One</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FizzBuzzer</span>.<span style="color:#74531f;">Convert</span>(1); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Equal</span>(<span style="color:#a31515;">&quot;1&quot;</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>); }</pre> </p> <p> Either the implementer is allowed to see the test, or the specification is communicated to him or her in some other way. In any case, the natural response to the first test is an implementation like this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Convert</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">number</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>; }</pre> </p> <p> In TDD, this is expected. This is the simplest implementation that passes all tests. We imagine that the tester already knows this, and therefore adds this test next: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Two</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FizzBuzzer</span>.<span style="color:#74531f;">Convert</span>(2); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Equal</span>(<span style="color:#a31515;">&quot;2&quot;</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>); }</pre> </p> <p> The implementer's response is this: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Convert</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">number</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">if</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">number</span>&nbsp;==&nbsp;1) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>; }</pre> </p> <p> The tester can't see the implementation, so may believe that the implementation is now 'appropriate'. Even if he or she wants to be 'more sure', a few more test cases (for, say, <em>4</em>, <em>7</em>, or <em>38</em>) could be added; it doesn't make any difference for the following argument. </p> <p> Next, incrementally, the tester may add a few test cases that cover the <code>"Fizz"</code> behaviour: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Three</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FizzBuzzer</span>.<span style="color:#74531f;">Convert</span>(3); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Equal</span>(<span style="color:#a31515;">&quot;Fizz&quot;</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>); } [<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">void</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Six</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FizzBuzzer</span>.<span style="color:#74531f;">Convert</span>(6); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Equal</span>(<span style="color:#a31515;">&quot;Fizz&quot;</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>); }</pre> </p> <p> Similar test cases cover the <code>"Buzz"</code> and <code>"FizzBuzz"</code> behaviours. For this example, I wrote eight test cases in total, but a more sceptical tester might write twelve or even sixteen before feeling confident that the test suite sufficiently describes the desired behaviour of the system. Even so, a sufficiently adversarial implementer might (given eight test cases) deliver this implementation: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:blue;">string</span>&nbsp;<span style="color:#74531f;">Convert</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">number</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">switch</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">number</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">case</span>&nbsp;&nbsp;1:&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;1&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">case</span>&nbsp;&nbsp;2:&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;2&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">case</span>&nbsp;&nbsp;5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">case</span>&nbsp;10:&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;Buzz&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">case</span>&nbsp;15: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">case</span>&nbsp;30:&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;FizzBuzz&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">default</span>:&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#a31515;">&quot;Fizz&quot;</span>; &nbsp;&nbsp;&nbsp;&nbsp;} }</pre> </p> <p> To be clear, it's not that I expect real-world programmers to be either obtuse or nefarious. In real life, on the other hand, requirements are more complicated, and may be introduced piecemeal in a fashion that may lead to buggy, overly-complicated implementations. </p> <h3 id="8b7bb29424ea4c22a851aa98037cc43a"> Under-determination <a href="#8b7bb29424ea4c22a851aa98037cc43a">#</a> </h3> <p> Remarkably, black-box testing may work better as an ex-post technique, compared to TDD. If we imagine that an implementer has made an effort to correctly implement a system according to specification, a tester may use black-box testing to poke at the SUT, using both randomly selected test cases, and by explicitly exercising the SUT at boundary cases. </p> <p> Even so, black-box testing in reality tends to run into the problem of <a href="https://en.wikipedia.org/wiki/Underdetermination">under-determination</a>, also known from philosophy of science. As I outlined in <a href="/2021/06/14/new-book-code-that-fits-in-your-head">Code That Fits in Your Head</a>, software testing has many similarities with empirical science. We use experiments (tests) to corroborate hypotheses that we have about software: Typically either that it <em>doesn't</em> pass tests, or that it does pass all tests, depending on where in the red-green-refactor cycle we are. </p> <p> Similar to science, we are faced with the basic epistemological problem that we have a finite number of tests, but usually an infinite (or at least extremely big) state space. Thus, as pointed out by the problem of under-determination, more than one 'reality' fits the available observations (i.e. test cases). The above FizzBuzz implementation is an example of this. </p> <p> As an aside, certain problems actually have <a href="https://en.wikipedia.org/wiki/Image_(mathematics)">images</a> that are sufficiently small that you <em>can</em> cover everything in total. In its most common description, the FizzBuzz kata, too, falls into this category. </p> <blockquote> <p> "Write a program that prints the numbers from <em>1 to 100</em>." </p> <footer><cite><a href="https://codingdojo.org/kata/FizzBuzz/">FizzBuzz</a></cite>, my emphasis</footer> </blockquote> <p> This means that you <em>can</em>, in fact, write 100 test cases and thereby specify the problem in its totality. What you still can't do with black-box testing, however, is impose a particular implementation. An adversarial implementer could write the <code>Convert</code> function as one big <code>switch</code> statement. Just like <a href="/2021/03/29/table-driven-tennis-scoring">I did with the Tennis kata</a>, another <a href="/2020/08/31/properties-for-all">kata with a small state space</a>. </p> <p> This, however, rarely happens in the real world. Example-driven testing is under-determined. And no, <a href="/2021/06/28/property-based-testing-is-not-the-same-as-partition-testing">property-based testing doesn't fundamentally change that conclusion</a>. It behoves you to <em>look</em> critically at the actual implementation code, and not rely exclusively on testing. </p> <h3 id="83a20a3021d94138b5cbdd8f1dd2f71a"> Working with implementation code <a href="#83a20a3021d94138b5cbdd8f1dd2f71a">#</a> </h3> <p> It's hardly a surprise that TDD isn't black-box testing. Is it white-box testing, then? Since the red-green-refactor cycle dictates a tight loop between test and production code, you always have the implementation code at hand. In that sense, the SUT is a white box. </p> <p> That said, the <a href="https://en.wikipedia.org/wiki/White-box_testing">common view on white-box testing</a> is that you work with knowledge about the internal implementation of an <em>already-written</em> system, and use that to design test cases. Typically, looking at the code should enable a tester to identify weak spots that warrant testing. </p> <p> This isn't always the case with TDD. If you follow the red-green-refactor checklist, each cycle should leave you with a SUT that passes all tests in the simplest way that could possibly work. Consider the first incarnation of <code>Convert</code>, above (the one that always returns <code>"1"</code>). It passes all tests, and from a white-box-testing perspective, it has no weak spots. You can't identify a test case that'll make it crash. </p> <p> If you consider the test suite as an executable specification, that degenerate implementation is <em>correct</em>, since it passes all tests. Of course, according to the kata description, it's wrong. Looking at the SUT code will tell you that in a heartbeat. It should prompt you to add another test case. The question is, though, whether that qualifies as white-box testing, or it's rather reminiscent of the <a href="https://blog.cleancoder.com/uncle-bob/2013/05/27/TheTransformationPriorityPremise.html">transformation priority premise</a>. Not that that's necessarily a dichotomy. </p> <h3 id="d3c56178d31c4c1fb25654a4a5e48243"> Overspecified software <a href="#d3c56178d31c4c1fb25654a4a5e48243">#</a> </h3> <p> Perhaps a more common problem with white-box testing in relation to TDD is the tendency to take a given implementation for granted. Of course, working according to the red-green-refactor cycle, there's no implementation before the test, but a common technique is to use <a href="http://xunitpatterns.com/Mock%20Object.html">Mock Objects</a> to let tests specify how the SUT should be implemented. This leads to the familiar problem of <a href="http://xunitpatterns.com/Fragile%20Test.html">Overspecified Software</a>. </p> <p> Here's an example. </p> <h3 id="a26fc9b04a5f440aac256c6f19db26a8"> Finding values in an interval <a href="#a26fc9b04a5f440aac256c6f19db26a8">#</a> </h3> <p> In the code base that accompanies <a href="/code-that-fits-in-your-head">Code That Fits in Your Head</a>, the code that handles a new restaurant reservation contains this code snippet: </p> <p> <pre><span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">reservations</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;Repository &nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ReadReservations</span>(<span style="font-weight:bold;color:#1f377f;">restaurant</span>.Id,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.At) &nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ConfigureAwait</span>(<span style="color:blue;">false</span>); <span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">now</span>&nbsp;=&nbsp;Clock.<span style="font-weight:bold;color:#74531f;">GetCurrentDateTime</span>(); <span style="font-weight:bold;color:#8f08c4;">if</span>&nbsp;(!<span style="font-weight:bold;color:#1f377f;">restaurant</span>.MaitreD.<span style="font-weight:bold;color:#74531f;">WillAccept</span>(<span style="font-weight:bold;color:#1f377f;">now</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservations</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>)) &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#74531f;">NoTables500InternalServerError</span>(); <span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;Repository.<span style="font-weight:bold;color:#74531f;">Create</span>(<span style="font-weight:bold;color:#1f377f;">restaurant</span>.Id,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>) &nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ConfigureAwait</span>(<span style="color:blue;">false</span>);</pre> </p> <p> The <code>ReadReservations</code> method is of particular interest in this context. It turns out to be a small extension method on a more general interface method: </p> <p> <pre><span style="color:blue;">internal</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&gt;&nbsp;<span style="color:#74531f;">ReadReservations</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IReservationsRepository</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">repository</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">restaurantId</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">date</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">date</span>.Date; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">max</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>.<span style="font-weight:bold;color:#74531f;">AddDays</span>(1).<span style="font-weight:bold;color:#74531f;">AddTicks</span>(-1); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">repository</span>.<span style="font-weight:bold;color:#74531f;">ReadReservations</span>(<span style="font-weight:bold;color:#1f377f;">restaurantId</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">max</span>); }</pre> </p> <p> The <code>IReservationsRepository</code> interface doesn't have a method that allows a client to search for all reservations on a given date. Rather, it defines a more general method that enables clients to search for reservations in a given interval: </p> <p> <pre><span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">ReadReservations</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">restaurantId</span>,&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>,&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">max</span>);</pre> </p> <p> As the parameter names imply, the method finds and returns all the reservations for a given restaurant between the <code>min</code> and <code>max</code> values. <a href="/2021/12/06/the-liskov-substitution-principle-as-a-profunctor">A previous article</a> already covers this method in much detail. </p> <p> I think I've stated this more than once before: Code is never perfect. Although I made a genuine attempt to write quality code for the book's examples, now that I revisit this API, I realize that there's room for improvement. The most obvious problem with that method definition is that it's not clear whether the range includes, or excludes, the boundary values. Would it improve encapsulation if the method instead took a <a href="/2024/01/22/a-range-kata-implementation-in-c">Range&lt;DateTime&gt;</a> parameter? </p> <p> At the very least, I could have named the parameters <code>inclusiveMin</code> and <code>inclusiveMax</code>. That's how the system is implemented, and you can see an artefact of that in the above extension method. It searches from midnight of <code>date</code> to the tick just before midnight on the next day. </p> <p> The SQL implementation reflects that contract, too. </p> <p> <pre><span style="color:blue;">SELECT</span>&nbsp;[PublicId]<span style="color:gray;">,</span>&nbsp;[At]<span style="color:gray;">,</span>&nbsp;[Name]<span style="color:gray;">,</span>&nbsp;[Email]<span style="color:gray;">,</span>&nbsp;[Quantity] <span style="color:blue;">FROM</span>&nbsp;[dbo]<span style="color:gray;">.</span>[Reservations] <span style="color:blue;">WHERE</span>&nbsp;[RestaurantId]&nbsp;<span style="color:gray;">=</span>&nbsp;@RestaurantId&nbsp;<span style="color:gray;">AND</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@Min&nbsp;<span style="color:gray;">&lt;=</span>&nbsp;[At]&nbsp;<span style="color:gray;">AND</span>&nbsp;[At]&nbsp;<span style="color:gray;">&lt;=</span>&nbsp;@Max</pre> </p> <p> Here, <code>@RestaurantId</code>, <code>@Min</code>, and <code>@Max</code> are query parameters. Notice that the query uses the <code>&lt;=</code> relation for both <code>@Min</code> and <code>@Max</code>, making both endpoints inclusive. </p> <h3 id="c3113935f001498681c7052959c30b2b"> Interactive white-box testing <a href="#c3113935f001498681c7052959c30b2b">#</a> </h3> <p> Since I'm aware of the problem of overspecified software, I test-drove the entire code base using <a href="/2019/02/18/from-interaction-based-to-state-based-testing">state-based testing</a>. Imagine, however, that I'd instead used a dynamic mock library. If so, a test could have looked like this: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">PostUsingMoq</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">now</span>&nbsp;=&nbsp;<span style="color:#2b91af;">DateTime</span>.Now; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Some</span>.Reservation.<span style="font-weight:bold;color:#74531f;">WithDate</span>(<span style="font-weight:bold;color:#1f377f;">now</span>.<span style="font-weight:bold;color:#74531f;">AddDays</span>(2).<span style="font-weight:bold;color:#74531f;">At</span>(20,&nbsp;15)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">repoTD</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Mock</span>&lt;<span style="color:#2b91af;">IReservationsRepository</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">repoTD</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Setup</span>(<span style="font-weight:bold;color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">r</span>.<span style="font-weight:bold;color:#74531f;">ReadReservations</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Some</span>.Restaurant.Id, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.At.Date, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.At.Date.<span style="font-weight:bold;color:#74531f;">AddDays</span>(1).<span style="font-weight:bold;color:#74531f;">AddTicks</span>(-1))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ReturnsAsync</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Collection</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationsController</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">SystemClock</span>(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">InMemoryRestaurantDatabase</span>(<span style="color:#2b91af;">Some</span>.Restaurant), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">repoTD</span>.Object); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">ar</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.<span style="font-weight:bold;color:#74531f;">Post</span>(<span style="color:#2b91af;">Some</span>.Restaurant.Id,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.<span style="font-weight:bold;color:#74531f;">ToDto</span>()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">IsAssignableFrom</span>&lt;<span style="color:#2b91af;">CreatedAtActionResult</span>&gt;(<span style="font-weight:bold;color:#1f377f;">ar</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;More&nbsp;assertions&nbsp;could&nbsp;go&nbsp;here.</span> }</pre> </p> <p> This test uses <a href="https://github.com/devlooped/moq">Moq</a>, but the example doesn't hinge on that. I rarely use dynamic mock libraries these days, but when I do, I still prefer Moq. </p> <p> Notice how the <code>Setup</code> reproduces the implementation of the <code>ReadReservations</code> extension method. The implication is that if you change the implementation code, you break the test. </p> <p> Even so, we may consider this an example of a test-driven white-box test. While, according to the red-green-refactor cycle, you're supposed to write the test before the implementation, this style of TDD only works if you, the test writer, has an exact plan for how the SUT is going to look. </p> <h3 id="7eda505b89c646c7a02b1726901b30b9"> An innocent refactoring? <a href="#7eda505b89c646c7a02b1726901b30b9">#</a> </h3> <p> Don't you find that <code><span style="font-weight:bold;color:#1f377f;">min</span>.<span style="font-weight:bold;color:#74531f;">AddDays</span>(1).<span style="font-weight:bold;color:#74531f;">AddTicks</span>(-1)</code> expression a bit odd? Wouldn't the code be cleaner if you could avoid the <code><span style="font-weight:bold;color:#74531f;">AddTicks</span>(-1)</code> part? </p> <p> Well, you can. </p> <p> A <em>tick</em> is the smallest unit of measurement of <a href="https://learn.microsoft.com/dotnet/api/system.datetime">DateTime</a> values. Since ticks are discrete, the range defined by the extension method would be equivalent to a right-open interval, where the minimum value is still included, but the maximum is not. If you made that change, the extension method would be simpler: </p> <p> <pre><span style="color:blue;">internal</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&gt;&nbsp;<span style="color:#74531f;">ReadReservations</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IReservationsRepository</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">repository</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">restaurantId</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">date</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">date</span>.Date; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">max</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>.<span style="font-weight:bold;color:#74531f;">AddDays</span>(1); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">repository</span>.<span style="font-weight:bold;color:#74531f;">ReadReservations</span>(<span style="font-weight:bold;color:#1f377f;">restaurantId</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">max</span>); }</pre> </p> <p> In order to offset that change, you also change the SQL accordingly: </p> <p> <pre><span style="color:blue;">SELECT</span>&nbsp;[PublicId]<span style="color:gray;">,</span>&nbsp;[At]<span style="color:gray;">,</span>&nbsp;[Name]<span style="color:gray;">,</span>&nbsp;[Email]<span style="color:gray;">,</span>&nbsp;[Quantity] <span style="color:blue;">FROM</span>&nbsp;[dbo]<span style="color:gray;">.</span>[Reservations] <span style="color:blue;">WHERE</span>&nbsp;[RestaurantId]&nbsp;<span style="color:gray;">=</span>&nbsp;@RestaurantId&nbsp;<span style="color:gray;">AND</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@Min&nbsp;<span style="color:gray;">&lt;=</span>&nbsp;[At]&nbsp;<span style="color:gray;">AND</span>&nbsp;[At]&nbsp;<span style="color:gray;">&lt;</span>&nbsp;@Max</pre> </p> <p> Notice that the query now compares <code>[At]</code> with <code>@Max</code> using the <code>&lt;</code> relation. </p> <p> While this is formally a breaking change of the interface, it's entirely internal to the application code base. No external systems or libraries depend on <code>IReservationsRepository</code>. Thus, this change is a true refactoring: It improves the code without changing the observable behaviour of the system. </p> <p> Even so, this change breaks the <code>PostUsingMoq</code> test. </p> <p> To make the test pass, you'll need to repeat the change you made to the SUT: </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">PostUsingMoq</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">now</span>&nbsp;=&nbsp;<span style="color:#2b91af;">DateTime</span>.Now; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Some</span>.Reservation.<span style="font-weight:bold;color:#74531f;">WithDate</span>(<span style="font-weight:bold;color:#1f377f;">now</span>.<span style="font-weight:bold;color:#74531f;">AddDays</span>(2).<span style="font-weight:bold;color:#74531f;">At</span>(20,&nbsp;15)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">repoTD</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Mock</span>&lt;<span style="color:#2b91af;">IReservationsRepository</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">repoTD</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Setup</span>(<span style="font-weight:bold;color:#1f377f;">r</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">r</span>.<span style="font-weight:bold;color:#74531f;">ReadReservations</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Some</span>.Restaurant.Id, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.At.Date, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.At.Date.<span style="font-weight:bold;color:#74531f;">AddDays</span>(1))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ReturnsAsync</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Collection</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationsController</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">SystemClock</span>(), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">InMemoryRestaurantDatabase</span>(<span style="color:#2b91af;">Some</span>.Restaurant), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">repoTD</span>.Object); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">ar</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">sut</span>.<span style="font-weight:bold;color:#74531f;">Post</span>(<span style="color:#2b91af;">Some</span>.Restaurant.Id,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.<span style="font-weight:bold;color:#74531f;">ToDto</span>()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">IsAssignableFrom</span>&lt;<span style="color:#2b91af;">CreatedAtActionResult</span>&gt;(<span style="font-weight:bold;color:#1f377f;">ar</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;More&nbsp;assertions&nbsp;could&nbsp;go&nbsp;here.</span> }</pre> </p> <p> If it's only one test, you can probably live with that, but it's the opposite of a robust test; it's a <a href="http://xunitpatterns.com/Fragile%20Test.html">Fragile Test</a>. </p> <blockquote> <p> "to refactor, the essential precondition is [...] solid tests" </p> <footer><cite><a href="/ref/refactoring">Refactoring</a>, Martin Fowler, 1999</cite></footer> </blockquote> <p> A common problem with <a href="/2019/02/25/an-example-of-interaction-based-testing-in-c">interaction-based testing</a> is that even small refactorings break many tests. We might see that as a symptom of having too much knowledge of implementation details. We might view this as related to white-box testing. </p> <p> To be clear, the tests in the code base that accompanies <a href="/code-that-fits-in-your-head">Code That Fits in Your Head</a> are all state-based, so contrary to the <code>PostUsingMoq</code> test, all 161 tests easily survive the above refactoring. </p> <h3 id="b41f2409e6de4ae9abfc95b7ec40da21"> Greyscale-box TDD <a href="#b41f2409e6de4ae9abfc95b7ec40da21">#</a> </h3> <p> It's not too hard to argue that TDD isn't black-box testing, but it's harder to argue that it's not white-box testing. Naturally, as you follow the red-green-refactor cycle, you know all about the implementation. Still, the danger of being too aware of the SUT code is being trapped in an <a href="/2024/12/09/implementation-and-usage-mindsets">implementation mindset</a>. </p> <p> While there's nothing wrong with getting the implementation right, many maintainability problems originate in insufficient <a href="/encapsulation-and-solid">encapsulation</a>. Deliberately treating the SUT as a grey box helps in discovering a SUT's contract. That's why I recommend techniques like <a href="/2019/10/07/devils-advocate">Devil's Advocate</a>. Pretending to view the SUT from the outside can shed valuable light on usability and maintainability issues. </p> <h3 id="adbf81f39d8e44f7a56fc05623967245"> Conclusion <a href="#adbf81f39d8e44f7a56fc05623967245">#</a> </h3> <p> The notions of white-box and black-box testing have been around for decades. So has TDD. Even so, it's not always clear to practitioners whether TDD is one or the other. The reason is, I believe, that TDD is neither. Good TDD practice sits somewhere between white-box testing and black-box testing. </p> <p> Exactly where on that greyscale spectrum TDD belongs depends on context. The more important encapsulation is, the closer you should move towards black-box testing. The more important correctness or algorithm performance is, the closer to white-box testing you should move. </p> <p> You can, however, move position on the spectrum even in the same code base. Perhaps you want to start close to white-box testing as you focus on getting the implementation right. Once the SUT works as intended, you may then decide to shift your focus towards encapsulation, in which case moving closer to black-box testing could prove beneficial. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/09/15/greyscale-box-test-driven-development IO is special https://blog.ploeh.dk/2025/09/08/io-is-special/ Mon, 08 Sep 2025 05:36:00 UTC <div id="post"> <p> <em>Are IO expressions really referentially transparent programs?</em> </p> <p> Sometimes, when I discuss <a href="/2018/11/19/functional-architecture-a-definition">functional architecture</a> or <a href="/2020/06/08/the-io-container">the IO container</a>, a reader will argue that <a href="https://www.haskell.org/">Haskell</a> <code>IO</code> really is 'pure', 'referentially transparent', 'functional', or has another similar property. </p> <p> The argument usually goes like this: An <code>IO</code> value is a composable <em>description</em> of an action, but not in itself an action. Since <code>IO</code> is a <code>Monad</code> instance, it composes via the usual monadic <em>bind</em> combinator <code>&gt;&gt;=</code>, or one of its derivatives. </p> <p> Another point sometimes made is that you <em>can</em> 'call' an <code>IO</code>-valued action from within a pure function, as demonstrated by this toy example: </p> <p> <pre><span style="color:#2b91af;">greet</span>&nbsp;<span style="color:blue;">::</span>&nbsp;<span style="color:blue;">TimeOfDay</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">String</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">String</span> greet&nbsp;timeOfDay&nbsp;name&nbsp;= &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;greeting&nbsp;=&nbsp;<span style="color:blue;">case</span>&nbsp;<span style="color:blue;">()</span>&nbsp;<span style="color:blue;">of</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;_&nbsp;|&nbsp;isMorning&nbsp;timeOfDay&nbsp;-&gt;&nbsp;<span style="color:#a31515;">&quot;Good&nbsp;morning&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;isAfternoon&nbsp;timeOfDay&nbsp;-&gt;&nbsp;<span style="color:#a31515;">&quot;Good&nbsp;afternoon&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;isEvening&nbsp;timeOfDay&nbsp;-&gt;&nbsp;<span style="color:#a31515;">&quot;Good&nbsp;evening&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:blue;">otherwise</span>&nbsp;-&gt;&nbsp;<span style="color:#a31515;">&quot;Hello&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sideEffect&nbsp;=&nbsp;<span style="color:blue;">putStrLn</span>&nbsp;<span style="color:#a31515;">&quot;Side&nbsp;effect!&quot;</span> &nbsp;&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="color:blue;">if</span>&nbsp;<span style="color:blue;">null</span>&nbsp;name &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;greeting&nbsp;++&nbsp;<span style="color:#a31515;">&quot;.&quot;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;greeting&nbsp;++&nbsp;<span style="color:#a31515;">&quot;,&nbsp;&quot;</span>&nbsp;++&nbsp;name&nbsp;++&nbsp;<span style="color:#a31515;">&quot;.&quot;</span></pre> </p> <p> This is effectively a Haskell port of the example given in <a href="/2020/07/06/referential-transparency-of-io">Referential transparency of IO</a>. Here, <code>sideEffect</code> is a value of the type <code>IO ()</code>, even though <code>greet</code> is a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a>. Such examples are sometimes used to argue that the expression <code>putStrLn "Side effect!"</code> is pure, because it's deterministic and has no side effects. </p> <p> Rather, <code>sideEffect</code> is a 'program' that describes an action. The program is a referentially transparent value, although actually running it is not. </p> <p> As I also explained in <a href="/2020/07/06/referential-transparency-of-io">Referential transparency of IO</a>, the above function application is legal because <code>greet</code> never uses the value 'inside' the <code>IO</code> action. In fact, the compiler may choose to optimize the <code>sideEffect</code> expression away, and I believe that <a href="https://en.wikipedia.org/wiki/Glasgow_Haskell_Compiler">GHC</a> does just that. </p> <p> I've tried to summarize the most common arguments as succinctly as I can. While I could cite actual online discussions that I've had, I don't wish to single out anyone. I don't want to make this article appear as though it's an attack on anyone in particular. Rather, my position remains that <em><code>IO</code> is special</em>, and I'll subsequently try to explain the reasoning. </p> <h3 id="a0e9e80d72eb4a979dddbce385649d3b"> Reductio ad absurdum <a href="#a0e9e80d72eb4a979dddbce385649d3b">#</a> </h3> <p> While I could begin my argument stating the general case, backed up by citing some papers, I'm afraid I'll lose most readers in the process. Therefore I'll flip the argument around and start with a counter-example. What would happen if we accept the claim that <code>IO</code> is pure or <a href="https://en.wikipedia.org/wiki/Referential_transparency">referentially transparent</a>? </p> <p> It would follow that <em>all</em> Haskell code should be considered pure. That would include <code>putStrLn "Hello, world."</code> or <a href="https://hackage.haskell.org/package/acme-missiles/docs/Acme-Missiles.html">launchMissiles</a>. That I find that conclusion absurd may just be my <a href="/2020/10/12/subjectivity">subjective</a> opinion, but it also seems to go against the original purpose of using <code>IO</code> to tackle the awkward squad. </p> <p> Furthermore, and this may be more objective, it seems to allow writing <em>everything</em> in <code>IO</code>, and still call it 'functional'. What do I mean by that? </p> <h3 id="283ca4d2dc6b4b38897fd43f2c3c51d1"> Functional imperative code <a href="#283ca4d2dc6b4b38897fd43f2c3c51d1">#</a> </h3> <p> If we accept that <code>IO</code> is pure, then we may decide to write everything in procedural style. We could, for example, <a href="/2024/12/23/implementing-rod-cutting">implement rod-cutting</a> by mirroring the imperative pseudocode used to describe the algorithm. </p> <p> <pre>{-#&nbsp;<span style="color:gray;">LANGUAGE</span>&nbsp;FlexibleContexts&nbsp;#-} <span style="color:blue;">module</span>&nbsp;RodCutting&nbsp;<span style="color:blue;">where</span> <span style="color:blue;">import</span>&nbsp;Control.Monad&nbsp;(<span style="color:#2b91af;">forM_</span>,&nbsp;<span style="color:#2b91af;">when</span>) <span style="color:blue;">import</span>&nbsp;Data.Array.IO <span style="color:blue;">import</span>&nbsp;Data.IORef&nbsp;(<span style="color:#2b91af;">newIORef</span>,&nbsp;<span style="color:#2b91af;">writeIORef</span>,&nbsp;<span style="color:#2b91af;">readIORef</span>,&nbsp;<span style="color:#2b91af;">modifyIORef</span>) <span style="color:#2b91af;">cutRod</span>&nbsp;<span style="color:blue;">::</span>&nbsp;(<span style="color:blue;">Ix</span>&nbsp;i,&nbsp;<span style="color:blue;">Num</span>&nbsp;i,&nbsp;<span style="color:blue;">Enum</span>&nbsp;i,&nbsp;<span style="color:blue;">Num</span>&nbsp;e,&nbsp;<span style="color:blue;">Bounded</span>&nbsp;e,&nbsp;<span style="color:blue;">Ord</span>&nbsp;e) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:blue;">IOArray</span>&nbsp;i&nbsp;e&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;i&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;(<span style="color:blue;">IOArray</span>&nbsp;i&nbsp;e,&nbsp;<span style="color:blue;">IOArray</span>&nbsp;i&nbsp;i) cutRod&nbsp;p&nbsp;n&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;r&nbsp;&lt;-&nbsp;newArray_&nbsp;(0,&nbsp;n) &nbsp;&nbsp;s&nbsp;&lt;-&nbsp;newArray_&nbsp;(1,&nbsp;n) &nbsp;&nbsp;writeArray&nbsp;r&nbsp;0&nbsp;0&nbsp;&nbsp;<span style="color:green;">--&nbsp;r[0]&nbsp;=&nbsp;0 </span>&nbsp;&nbsp;forM_&nbsp;[1..n]&nbsp;$&nbsp;\j&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;q&nbsp;&lt;-&nbsp;newIORef&nbsp;<span style="color:blue;">minBound</span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;q&nbsp;=&nbsp;-∞ </span>&nbsp;&nbsp;&nbsp;&nbsp;forM_&nbsp;[1..j]&nbsp;$&nbsp;\i&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qValue&nbsp;&lt;-&nbsp;readIORef&nbsp;q &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p_i&nbsp;&lt;-&nbsp;readArray&nbsp;p&nbsp;i &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r_j_i&nbsp;&lt;-&nbsp;readArray&nbsp;r&nbsp;(j&nbsp;-&nbsp;i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when&nbsp;(qValue&nbsp;&lt;&nbsp;p_i&nbsp;+&nbsp;r_j_i)&nbsp;$&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;writeIORef&nbsp;q&nbsp;(p_i&nbsp;+&nbsp;r_j_i)&nbsp;&nbsp;<span style="color:green;">--&nbsp;q&nbsp;=&nbsp;p[i]&nbsp;+&nbsp;r[j&nbsp;-&nbsp;i] </span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;writeArray&nbsp;s&nbsp;j&nbsp;i&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">--&nbsp;s[j]&nbsp;=&nbsp;i </span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;qValue&#39;&nbsp;&lt;-&nbsp;readIORef&nbsp;q &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;writeArray&nbsp;r&nbsp;j&nbsp;qValue&#39;&nbsp;&nbsp;<span style="color:green;">--&nbsp;r[j]&nbsp;=&nbsp;q </span> &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;(r,&nbsp;s)</pre> </p> <p> Ironically, the <code>cutRod</code> action remains referentially transparent, as is the original pseudocode from <a href="/ref/clrs">CLRS</a>. This is because the algorithm itself is deterministic, and has no (external) side effects. Even so, the Haskell type system can't 'see' that. This implementation is intrinsically <code>IO</code>-valued. </p> <h3 id="2b88809a7f244ed9bbabed7cfacff682"> Functional encapsulation <a href="#2b88809a7f244ed9bbabed7cfacff682">#</a> </h3> <p> You may think that this just proves the point that <code>IO</code> is pure, but it doesn't. We've always known that we can lift any pure value into <code>IO</code> using <code>return</code>: <code>return 42</code> remains referentially transparent, even if it's contained in <code>IO</code>. </p> <p> The reverse isn't always true. We can't conclude that code is referentially transparent when it's contained in <code>IO</code>. Usually, it isn't. </p> <p> Be that as it may, why do we even care? </p> <p> The problem is one of <a href="/2022/10/24/encapsulation-in-functional-programming">encapsulation</a>. When an action like <code>cutRod</code>, above, returns an <code>IO</code> value, we're facing a dearth of guarantees. As users of the action, we may have many questions, most of which aren't answered by the type: </p> <ul> <li>Does <code>cutRod</code> modify the input array <code>p</code>?</li> <li>Is <code>cutRod</code> deterministic?</li> <li>Does <code>cutRod</code> launch missiles?</li> <li>Can I memoize the return values of <code>cutRod</code>?</li> <li>Does <code>cutRod</code> somehow keep a reference to the arrays that it returns? Can I be sure that a background thread, or a subsequent API call, doesn't mutate these arrays? In other words, is there a potential <a href="https://en.wikipedia.org/wiki/Aliasing_(computing)">aliasing</a> problem?</li> </ul> <p> At best, such lack of guarantees lead to <a href="/2013/07/08/defensive-coding">defensive coding</a>, but usually it leads to bugs. </p> <p> If, on the other hand, we were to write a version of <code>cutRod</code> that does <em>not</em> involve <code>IO</code>, we'd be able to answer all the above questions. The advantage would be that the function would be safer and easier to consume. </p> <h3 id="b0946c3ce3cc44359ec4babce80335cd"> Referential transparency is not the same as purity <a href="#b0946c3ce3cc44359ec4babce80335cd">#</a> </h3> <p> This leads to a point that I failed to understand for years, <a href="/2020/02/24/discerning-and-maintaining-purity#60eb2b1f83dd4b2fbc0be684d729af96">until Tyson Williams pointed it out to me</a>. Referential transparency is not the same as purity, although the overlap is substantial. </p> <p> <img src="/content/binary/ref-trans-purity-venn.png" alt="Venn diagram of two sets: Referential transparency and purity. The intersection is considerable." width="400"> </p> <p> Of course, such a claim requires me to define the terms, but I'll try to keep it light. I'll define <em>referential transparency</em> as the property that allows replacing a function with the value it produces. Practically, it allows memoization. On the other hand, I'll define <em>purity</em> as functions that Haskell can distinguish from impure actions. In practice, this implies the absence of <code>IO</code>. </p> <p> Usually this amounts to the same thing, but as we've seen above, it's possible to write referentially transparent code that nonetheless is embedded in <code>IO</code>. There are also <a href="http://conal.net/blog/posts/notions-of-purity-in-haskell">examples of functions that look pure, although they may not be referentially transparent</a>. Fortunately these are, in my experience, more rare. </p> <p> That said, this is a digression. My agenda is to argue that <code>IO</code> is special. Yes, it's a <code>Monad</code> instance. Yes, it composes. No, it's not referentially transparent. </p> <h3 id="5392eba1c39c405d99e77de57d842120"> Semantics <a href="#5392eba1c39c405d99e77de57d842120">#</a> </h3> <p> From the point of encapsulation, I've previously argued that <a href="/2021/07/28/referential-transparency-fits-in-your-head">referential transparency is attractive because it fits in your head</a>. Code that is not referentially transparent usually doesn't. </p> <p> Why is <code>IO</code> not referentially transparent? To repeat the argument that I sometimes run into, <code>IO</code> values describe programs. Every time your Haskell code runs, the same <code>IO</code> value describes the same program. </p> <p> This strikes me as about as useful an assertion as insisting that all <a href="https://en.wikipedia.org/wiki/C_(programming_language)">C</a> code is referentially transparent. After all, a C program also describes the same program even if executed multiple times. </p> <p> But you don't have to take my word for it. In <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/marktoberdorf/mark.pdf">Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell</a> Simon Peyton Jones presents the semantics of Haskell. </p> <blockquote> <p> "Our semantics is stratified in two levels: an <em>inner denotational semantics</em> that describes the behaviour of pure terms, while an <em>outer monadic transition semantics</em> describes the behaviour of <code>IO</code> computations." </p> <footer><cite>Tackling the Awkward Squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell</cite>, Simon Peyton Jones, 2000</footer> </blockquote> <p> Over the next 20 pages, that paper goes into details on how <code>IO</code> is special. The point is that it has different semantics from the rest of Haskell. </p> <h3 id="ba343f93c94d4ffba33c78a226f0f0de"> Pure rod-cutting <a href="#ba343f93c94d4ffba33c78a226f0f0de">#</a> </h3> <p> Before I close, I realize that the above <code>cutRod</code> action may cause distress with some readers. To relieve the tension I'll leave you with a pure implementation. </p> <p> <pre>{-#&nbsp;<span style="color:gray;">LANGUAGE</span>&nbsp;TupleSections&nbsp;#-} <span style="color:blue;">module</span>&nbsp;RodCutting&nbsp;(<span style="color:#2b91af;">cutRod</span>,&nbsp;<span style="color:#2b91af;">solve</span>)&nbsp;<span style="color:blue;">where</span> <span style="color:blue;">import</span>&nbsp;Data.Foldable&nbsp;(<span style="color:#2b91af;">foldl&#39;</span>) <span style="color:blue;">import</span>&nbsp;Data.Map.Strict&nbsp;(<span style="color:#2b91af;">(!)</span>) <span style="color:blue;">import</span>&nbsp;<span style="color:blue;">qualified</span>&nbsp;Data.Map.Strict&nbsp;<span style="color:blue;">as</span>&nbsp;Map <span style="color:#2b91af;">seekBetterCut</span>&nbsp;<span style="color:blue;">::</span>&nbsp;(<span style="color:blue;">Ord</span>&nbsp;a,&nbsp;<span style="color:blue;">Num</span>&nbsp;a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;[a]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(a,&nbsp;<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;a,&nbsp;<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:#2b91af;">Int</span>)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Int</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(a,&nbsp;<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;a,&nbsp;<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:#2b91af;">Int</span>) seekBetterCut&nbsp;p&nbsp;j&nbsp;(q,&nbsp;r,&nbsp;s)&nbsp;i&nbsp;= &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;price&nbsp;=&nbsp;p&nbsp;!!&nbsp;i &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;remainingRevenue&nbsp;=&nbsp;r&nbsp;!&nbsp;(j&nbsp;-&nbsp;i) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(q&#39;,&nbsp;s&#39;)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;q&nbsp;&lt;&nbsp;price&nbsp;+&nbsp;remainingRevenue&nbsp;<span style="color:blue;">then</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(price&nbsp;+&nbsp;remainingRevenue,&nbsp;Map.insert&nbsp;j&nbsp;i&nbsp;s) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;(q,&nbsp;s) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;r&#39;&nbsp;=&nbsp;Map.insert&nbsp;j&nbsp;q&#39;&nbsp;r &nbsp;&nbsp;<span style="color:blue;">in</span>&nbsp;(q&#39;,&nbsp;r&#39;,&nbsp;s&#39;) <span style="color:#2b91af;">findBestCut</span>&nbsp;<span style="color:blue;">::</span>&nbsp;(<span style="color:blue;">Bounded</span>&nbsp;a,&nbsp;<span style="color:blue;">Ord</span>&nbsp;a,&nbsp;<span style="color:blue;">Num</span>&nbsp;a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;[a]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;a,&nbsp;<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:#2b91af;">Int</span>)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Int</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;a,&nbsp;<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:#2b91af;">Int</span>) findBestCut&nbsp;p&nbsp;(r,&nbsp;s)&nbsp;j&nbsp;= &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;q&nbsp;=&nbsp;<span style="color:blue;">minBound</span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;q&nbsp;=&nbsp;-∞ </span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(_,&nbsp;r&#39;,&nbsp;s&#39;)&nbsp;=&nbsp;foldl&#39;&nbsp;(seekBetterCut&nbsp;p&nbsp;j)&nbsp;(q,&nbsp;r,&nbsp;s)&nbsp;[1..j] &nbsp;&nbsp;<span style="color:blue;">in</span>&nbsp;(r&#39;,&nbsp;s&#39;) <span style="color:#2b91af;">cutRod</span>&nbsp;<span style="color:blue;">::</span>&nbsp;(<span style="color:blue;">Bounded</span>&nbsp;a,&nbsp;<span style="color:blue;">Ord</span>&nbsp;a,&nbsp;<span style="color:blue;">Num</span>&nbsp;a) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;[a]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;(<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;a,&nbsp;<span style="color:blue;">Map</span>.<span style="color:blue;">Map</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:#2b91af;">Int</span>) cutRod&nbsp;p&nbsp;n&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;r&nbsp;=&nbsp;Map.fromAscList&nbsp;$&nbsp;<span style="color:blue;">map</span>&nbsp;(,&nbsp;0)&nbsp;[0..n]&nbsp;&nbsp;<span style="color:green;">--&nbsp;r[0:n]&nbsp;initialized&nbsp;to&nbsp;0 </span>&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;s&nbsp;=&nbsp;Map.fromAscList&nbsp;$&nbsp;<span style="color:blue;">map</span>&nbsp;(,&nbsp;0)&nbsp;[1..n]&nbsp;&nbsp;<span style="color:green;">--&nbsp;s[1:n]&nbsp;initialized&nbsp;to&nbsp;0 </span>&nbsp;&nbsp;foldl&#39;&nbsp;(findBestCut&nbsp;p)&nbsp;(r,&nbsp;s)&nbsp;[1..n] <span style="color:#2b91af;">solve</span>&nbsp;<span style="color:blue;">::</span>&nbsp;(<span style="color:blue;">Bounded</span>&nbsp;a,&nbsp;<span style="color:blue;">Ord</span>&nbsp;a,&nbsp;<span style="color:blue;">Num</span>&nbsp;a)&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;[a]&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;[<span style="color:#2b91af;">Int</span>] solve&nbsp;p&nbsp;n&nbsp;= &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;(_,&nbsp;s)&nbsp;=&nbsp;cutRod&nbsp;p&nbsp;n &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;loop&nbsp;l&nbsp;n&#39;&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;n&#39;&nbsp;&gt;&nbsp;0&nbsp;<span style="color:blue;">then</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;cut&nbsp;=&nbsp;s&nbsp;!&nbsp;n&#39; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">in</span>&nbsp;loop&nbsp;(cut&nbsp;:&nbsp;l)&nbsp;(n&#39;&nbsp;-&nbsp;cut) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;l &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;l&#39;&nbsp;=&nbsp;loop&nbsp;<span style="color:blue;">[]</span>&nbsp;n &nbsp;&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="color:blue;">reverse</span>&nbsp;l&#39;</pre> </p> <p> This is a fairly direct translation of the imperative algorithm. It's possible that you could come up with something more elegant. At least, I think that <a href="/2025/01/06/encapsulating-rod-cutting">I did so in F#</a>. </p> <p> Regardless of the level of elegance of the implementation, this version of <code>cutRod</code> advertises its properties via its type. A client developer can now trivially answer the above questions, just by looking at the type: No, the function doesn't mutate the input list <code>p</code>. Yes, the function is deterministic. No, it doesn't launch missiles. Yes, you can memoize it. No, there's no aliasing problem. </p> <h3 id="379ee8d1db8046a1ac2133d7ff603a4a"> Conclusion <a href="#379ee8d1db8046a1ac2133d7ff603a4a">#</a> </h3> <p> From time to time, I run into the claim that Haskell <code>IO</code>, being monadic and composable, is referentially transparent, and that it's only during execution that this property is lost. </p> <p> I argue that such claims are of little practical interest. There are other parts of Haskell that <em>remain</em> referentially transparent, even during execution. Thus, <code>IO</code> is still special. </p> <p> From a practical perspective, the reason I care about referential transparency is because the more you have of it, the simpler your code is; the better it fits in your head. The kind of referential transparency that some people argue that <code>IO</code> has does not have the property of making code simpler. In reality, <code>IO</code> code has the same inherent properties as code written in C, <a href="https://www.python.org/">Python</a>, <a href="https://www.java.com">Java</a>, <a href="https://fortran-lang.org/">Fortran</a>, etc. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/09/08/io-is-special Song recommendations with C# free monads https://blog.ploeh.dk/2025/09/01/song-recommendations-with-c-free-monads/ Mon, 01 Sep 2025 05:57:00 UTC <div id="post"> <p> <em>Just because it's possible. Don't do this at work.</em> </p> <p> This is the last article in a series named <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">Alternative ways to design with functional programming</a>. In it, you've seen various suggestions on how to model a non-trivial problem with various kinds of functional-programming patterns. The previous two articles showed how to use free monads to model the problem in <a href="https://www.haskell.org/">Haskell</a> and <a href="https://fsharp.org/">F#</a>. In this article, I'll repeat the exercise in C#. It's not going to be pretty, but it's possible. </p> <p> What is the point of this exercise? Mostly to supply parity in demo code. If you're more familiar with C# than F# or Haskell, this may give you a better sense of what a free monad is, and how it works. That's all. I don't consider the following practical code, and I don't endorse it. </p> <p> The code shown here is based on the <code>free</code> branch of the <em>DotNet</em> Git repository available with this article series. </p> <h3 id="a33aa288b6e14a7db2fadabceb3ba20f"> Functor <a href="#a33aa288b6e14a7db2fadabceb3ba20f">#</a> </h3> <p> A free monad enables you to define a <a href="/2022/03/28/monads">monad</a> from any <a href="/2018/03/22/functors">functor</a>. In this context, you start with the functor that models an instruction set for a domain-specific language (DSL). The goal is to replace the <code>SongService</code> interface with this instruction set. </p> <p> As a reminder, this is the interface: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">interface</span>&nbsp;<span style="color:#2b91af;">SongService</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">User</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">GetTopListenersAsync</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songId</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">GetTopScrobblesAsync</span>(<span style="color:blue;">string</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>); }</pre> </p> <p> I'll remind the reader that the code is my attempt to reconstruct the sample code shown in <a href="https://tyrrrz.me/blog/pure-impure-segregation-principle">Pure-Impure Segregation Principle</a>. I don't know if <code>SongService</code> is a base class or an interface. Based on the lack of the <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> C# <code>I</code> prefix for interfaces, one may suppose that it was really intended to be a base class, but since I find interfaces easier to handle than base classes, here we are. </p> <p> In any case, the goal is to replace it with an instruction set, starting with a <a href="https://en.wikipedia.org/wiki/Tagged_union">sum type</a>. Since C# comes with no native support for sum types, we'll need to model it with either <a href="/2018/05/22/church-encoding">Church encoding</a> or a <a href="/2018/06/25/visitor-as-a-sum-type">Visitor</a>. I've been over the Visitor territory enough times already, so here I'll go with the Church option, since it's a tad simpler. </p> <p> I start by creating a new class called <code><span style="color:#2b91af;">SongInstruction</span>&lt;<span style="color:#2b91af;">T</span>&gt;</code> with this method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Match</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;(<span style="color:blue;">int</span>,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">User</span>&gt;,&nbsp;<span style="color:#2b91af;">T</span>&gt;),&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">getTopListeners</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;(<span style="color:blue;">string</span>,&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;,&nbsp;<span style="color:#2b91af;">T</span>&gt;),&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">getTopScrobbles</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;imp.<span style="font-weight:bold;color:#74531f;">Match</span>(<span style="font-weight:bold;color:#1f377f;">getTopListeners</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">getTopScrobbles</span>); }</pre> </p> <p> If you squint sufficiently hard, you may be able to see how the <code>getTopListeners</code> parameter corresponds to the interface's <code>GetTopListenersAsync</code> method, and likewise for the other parameter. </p> <p> I'm not going to give you a very detailed walkthrough, as I've <a href="/2018/07/24/dependency-injection-revisited">already done that earlier in a different context</a>. Likewise, I'll skip some of the implementation details. All the code is available in the Git repository. </p> <p> To be a functor, the class needs a <code>Select</code> method. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">SongInstruction</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">Select</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Match</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">t</span>&nbsp;=&gt;&nbsp;<span style="color:#2b91af;">SongInstruction</span>.<span style="color:#74531f;">GetTopListeners</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">t</span>.Item1,&nbsp;<span style="color:green;">//&nbsp;songId</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">users</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">selector</span>(<span style="font-weight:bold;color:#1f377f;">t</span>.Item2(<span style="font-weight:bold;color:#1f377f;">users</span>))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">t</span>&nbsp;=&gt;&nbsp;<span style="color:#2b91af;">SongInstruction</span>.<span style="color:#74531f;">GetTopScrobbles</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">t</span>.Item1,&nbsp;<span style="color:green;">//&nbsp;userName</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">selector</span>(<span style="font-weight:bold;color:#1f377f;">t</span>.Item2(<span style="font-weight:bold;color:#1f377f;">songs</span>)))); }</pre> </p> <p> The name <code>t</code> is, in both cases, short for <em>tuple</em>. It's possible that more recent versions of C# finally allow pattern matching of tuples in lambda expressions, but the version this code is based on doesn't. In both cases <code>Item2</code> is the 'continuation' function. </p> <h3 id="1d16ea38310845e3b2cea2a44ec98d4a"> Monad <a href="#1d16ea38310845e3b2cea2a44ec98d4a">#</a> </h3> <p> The next step is to wrap the functor in a data structure that enables you to sequence the above instructions. That has to be another sum type, this time called <code><span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">T</span>&gt;</code>, characterized by this <code>Match</code> method: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">TResult</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Match</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">SongInstruction</span>&lt;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">free</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">pure</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;imp.<span style="font-weight:bold;color:#74531f;">Match</span>(<span style="font-weight:bold;color:#1f377f;">free</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">pure</span>); }</pre> </p> <p> A <code>SelectMany</code> method is required to make this type a proper monad: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">SelectMany</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Match</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;<span style="color:#2b91af;">SongProgram</span>.<span style="color:#74531f;">Free</span>(<span style="font-weight:bold;color:#1f377f;">i</span>.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="font-weight:bold;color:#1f377f;">p</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">p</span>.<span style="font-weight:bold;color:#74531f;">SelectMany</span>(<span style="font-weight:bold;color:#1f377f;">selector</span>))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">selector</span>); }</pre> </p> <p> The code is already verbose enough as it is, so I've used <code>i</code> for <em>instruction</em> and <code>p</code> for <em>program</em>. </p> <h3 id="4c10469d3ba64daa81a9ca05824d1cae"> Lifted helpers <a href="#4c10469d3ba64daa81a9ca05824d1cae">#</a> </h3> <p> Although not strictly required, I often find it useful to add a helper method for each case of the instruction type: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">User</span>&gt;&gt;&nbsp;<span style="color:#74531f;">GetTopListeners</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songId</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#74531f;">Free</span>(<span style="color:#2b91af;">SongInstruction</span>.<span style="color:#74531f;">GetTopListeners</span>(<span style="font-weight:bold;color:#1f377f;">songId</span>,&nbsp;<span style="color:#74531f;">Pure</span>)); } <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&gt;&nbsp;<span style="color:#74531f;">GetTopScrobbles</span>(<span style="color:blue;">string</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#74531f;">Free</span>(<span style="color:#2b91af;">SongInstruction</span>.<span style="color:#74531f;">GetTopScrobbles</span>(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:#74531f;">Pure</span>)); }</pre> </p> <p> This just makes the user code look a bit cleaner. </p> <h3 id="c922ff0d22cb41e4b9fe89effe0b58f1"> Song recommendations as a DSL <a href="#c922ff0d22cb41e4b9fe89effe0b58f1">#</a> </h3> <p> Using the composition from <a href="/2025/06/16/song-recommendations-from-c-combinators">Song recommendations from C# combinators</a> as a starting point, it doesn't take that many changes to turn it into a <code>SongProgram</code>-valued function. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">IReadOnlyList</span>&lt;<span style="color:#2b91af;">Song</span>&gt;&gt;&nbsp;<span style="color:#74531f;">GetRecommendations</span>(<span style="color:blue;">string</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;1.&nbsp;Get&nbsp;user&#39;s&nbsp;own&nbsp;top&nbsp;scrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;2.&nbsp;Get&nbsp;other&nbsp;users&nbsp;who&nbsp;listened&nbsp;to&nbsp;the&nbsp;same&nbsp;songs</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;3.&nbsp;Get&nbsp;top&nbsp;scrobbles&nbsp;of&nbsp;those&nbsp;users</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;4.&nbsp;Aggregate&nbsp;the&nbsp;songs&nbsp;into&nbsp;recommendations</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>.<span style="color:#74531f;">GetTopScrobbles</span>(<span style="font-weight:bold;color:#1f377f;">userName</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">SelectMany</span>(<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;=&gt;&nbsp;<span style="color:#74531f;">UserTopScrobbles</span>(<span style="font-weight:bold;color:#1f377f;">scrobbles</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Traverse</span>(<span style="font-weight:bold;color:#1f377f;">scrobble</span>&nbsp;=&gt;&nbsp;<span style="color:#2b91af;">SongProgram</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="color:#74531f;">GetTopListeners</span>(<span style="font-weight:bold;color:#1f377f;">scrobble</span>.Song.Id) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="color:#74531f;">TopListeners</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">SelectMany</span>(<span style="font-weight:bold;color:#1f377f;">users</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">users</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Traverse</span>(<span style="font-weight:bold;color:#1f377f;">user</span>&nbsp;=&gt;&nbsp;<span style="color:#2b91af;">SongProgram</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="color:#74531f;">GetTopScrobbles</span>(<span style="font-weight:bold;color:#1f377f;">user</span>.UserName) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="color:#74531f;">TopScrobbles</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="color:#74531f;">Songs</span>))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="color:#74531f;">TakeTopRecommendations</span>)); }</pre> </p> <p> Notice how much it resembles the original <code>GetRecommendationsAsync</code> method on the <code>RecommendationsProvider</code> class. Instead of <code>songService.GetTopScrobblesAsync</code> it just has <code>SongProgram.GetTopScrobbles</code>, and instead of <code>songService.GetTopListenersAsync</code> it has <code>SongProgram.GetTopListeners</code>. </p> <p> To support this composition, however, a <a href="/2024/11/11/traversals">traversal</a> is required. </p> <h3 id="f6f58bba60324a15a6aa36fb17b55fca"> Traverse <a href="#f6f58bba60324a15a6aa36fb17b55fca">#</a> </h3> <p> The traversal needs a <code>Select</code> function on <code>SongProgram</code>, so we'll start with that. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">Select</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;(<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#74531f;">SelectMany</span>(<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;<span style="color:#2b91af;">SongProgram</span>.<span style="color:#74531f;">Pure</span>(<span style="font-weight:bold;color:#1f377f;">selector</span>(<span style="font-weight:bold;color:#1f377f;">x</span>))); }</pre> </p> <p> This is the standard implementation of a functor from a monad. </p> <p> It turns out that it's also useful to define a function to concatenate two sequence-valued programs. </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&nbsp;<span style="color:#74531f;">Concat</span>&lt;<span style="color:#2b91af;">T</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">xs</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">ys</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">xs</span>.<span style="font-weight:bold;color:#74531f;">SelectMany</span>(<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">ys</span>.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="font-weight:bold;color:#1f377f;">y</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>.<span style="font-weight:bold;color:#74531f;">Concat</span>(<span style="font-weight:bold;color:#1f377f;">y</span>))); }</pre> </p> <p> This could, perhaps, be a <code>public</code> function, but in this situation, I only need it to implement <code>Traverse</code>, so I kept it <code>private</code>. The <code>Traverse</code> function, on the other hand, is <code>public</code>. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">static</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;<span style="color:#74531f;">Traverse</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">TResult</span>&gt;( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>&nbsp;<span style="color:#2b91af;">IEnumerable</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">source</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Func</span>&lt;<span style="color:#2b91af;">T</span>,&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">selector</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">source</span>.<span style="font-weight:bold;color:#74531f;">Aggregate</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#74531f;">Pure</span>(<span style="color:#2b91af;">Enumerable</span>.<span style="color:#74531f;">Empty</span>&lt;<span style="color:#2b91af;">TResult</span>&gt;()), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(<span style="font-weight:bold;color:#1f377f;">acc</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>)&nbsp;=&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">acc</span>.<span style="font-weight:bold;color:#74531f;">Concat</span>(<span style="font-weight:bold;color:#1f377f;">selector</span>(<span style="font-weight:bold;color:#1f377f;">x</span>).<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="font-weight:bold;color:#1f377f;">xr</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>[]&nbsp;{<span style="font-weight:bold;color:#1f377f;">xr</span>}.<span style="font-weight:bold;color:#74531f;">AsEnumerable</span>()))); }</pre> </p> <p> Given a sequence of values, <code>Traverse</code> applies <code>selector</code> to each, and collects all resulting programs into a single sequence-valued program. You see it in use in the above <code>GetRecommendations</code> composition. </p> <h3 id="b440d896708d4e1787389d7cc0f473c1"> Interpreter <a href="#b440d896708d4e1787389d7cc0f473c1">#</a> </h3> <p> That last missing piece is an interpreter that can evaluate a program. Since I already have a class called <code>FakeSongService</code>, adding an <code>Interpret</code> method was the easiest implementation strategy. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">T</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Interpret</span>&lt;<span style="color:#2b91af;">T</span>&gt;(<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">T</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">program</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">program</span>.<span style="font-weight:bold;color:#74531f;">Match</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">i</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">i</span>.<span style="font-weight:bold;color:#74531f;">Match</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">t</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">Interpret</span>(<span style="font-weight:bold;color:#1f377f;">t</span>.Item2(<span style="font-weight:bold;color:#74531f;">GetTopListernes</span>(<span style="font-weight:bold;color:#1f377f;">t</span>.Item1))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">t</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">Interpret</span>(<span style="font-weight:bold;color:#1f377f;">t</span>.Item2(<span style="font-weight:bold;color:#74531f;">GetTopScrobbles</span>(<span style="font-weight:bold;color:#1f377f;">t</span>.Item1)))), &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>); }</pre> </p> <p> Here, <code>GetTopListernes</code> and <code>GetTopScrobbles</code> are two <code>private</code> helper functions: </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">User</span>&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">GetTopListernes</span>(<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songId</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">listeners</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;kvp&nbsp;<span style="color:blue;">in</span>&nbsp;users &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">where</span>&nbsp;kvp.Value.<span style="font-weight:bold;color:#74531f;">ContainsKey</span>(<span style="font-weight:bold;color:#1f377f;">songId</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">User</span>(kvp.Key,&nbsp;kvp.Value.Values.<span style="font-weight:bold;color:#74531f;">Sum</span>()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">listeners</span>.<span style="font-weight:bold;color:#74531f;">ToList</span>(); } <span style="color:blue;">private</span>&nbsp;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">GetTopScrobbles</span>(<span style="color:blue;">string</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;=&nbsp;users &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">GetOrAdd</span>(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ConcurrentDictionary</span>&lt;<span style="color:blue;">int</span>,&nbsp;<span style="color:blue;">int</span>&gt;()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="font-weight:bold;color:#1f377f;">kvp</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">Scrobble</span>(songs[<span style="font-weight:bold;color:#1f377f;">kvp</span>.Key],&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>.Value)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>.<span style="font-weight:bold;color:#74531f;">ToList</span>(); }</pre> </p> <p> The implementation closely mirrors the original <a href="http://xunitpatterns.com/Fake%20Object.html">Fake</a> interface implementation, where <code>users</code> and <code>songs</code> are class fields on <code>FakeSongService</code>. This class was first shown in <a href="/2025/04/10/characterising-song-recommendations">Characterising song recommendations</a>. </p> <p> It's now possible to rewrite all the tests. </p> <h3 id="0ad149fe02794524a18af4a4f6eefe07"> Refactoring the tests <a href="#0ad149fe02794524a18af4a4f6eefe07">#</a> </h3> <p> Since the original <code>GetRecommendationsAsync</code> method was task-based, all tests had to run in <a href="https://learn.microsoft.com/dotnet/fsharp/language-reference/task-expressions">task workflows</a>. This is no longer necessary, as this simplified <a href="https://fscheck.github.io/FsCheck/">FsCheck</a> property demonstrates: </p> <p> <pre>[&lt;<span style="color:#2b91af;">Property</span>&gt;] <span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">``One&nbsp;user,&nbsp;some&nbsp;songs``</span>&nbsp;()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">gen</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">user</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Gen</span>.userName &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Gen</span>.<span style="color:#74531f;">arrayOf</span>&nbsp;<span style="color:#2b91af;">Gen</span>.song &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbleCounts</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Gen</span>.<span style="color:#74531f;">choose</span>&nbsp;(1,&nbsp;100)&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Gen</span>.<span style="color:#74531f;">arrayOfLength</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>.Length &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">user</span>,&nbsp;<span style="color:#2b91af;">Array</span>.<span style="color:#74531f;">zip</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbleCounts</span>)&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Arb</span>.<span style="color:#74531f;">fromGen</span>&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Prop</span>.<span style="color:#74531f;">forAll</span>&nbsp;&lt;|&nbsp;<span style="color:blue;">fun</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">user</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>)&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FakeSongService</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Array</span>.<span style="color:#74531f;">iter</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">s</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">c</span>)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">user</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">c</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RecommendationsProvider</span>.<span style="font-weight:bold;color:#74531f;">GetRecommendations</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">user</span>&nbsp;|&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Interpret</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="font-weight:bold;color:#74531f;">Empty</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span></pre> </p> <p> Originally, this test had to be defined in terms of the <code>task</code> computation expression, but now it's a pure function. In <a href="/2013/06/24/a-heuristic-for-formatting-code-according-to-the-aaa-pattern">the act phase</a> the test calls <code>RecommendationsProvider.GetRecommendations user</code> and pipes the returned program to <code>srvc.Interpret</code>. The result, <code>actual</code>, is a plain <code>IReadOnlyCollection&lt;Song&gt;</code> value. </p> <p> Similarly, I was able to migrate all the example-based tests over, too. </p> <p> <pre>[&lt;<span style="color:#2b91af;">Fact</span>&gt;] <span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">``One&nbsp;verified&nbsp;recommendation``</span>&nbsp;()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FakeSongService</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="color:#a31515;">&quot;cat&quot;</span>,&nbsp;<span style="color:#2b91af;">Song</span>&nbsp;(1,&nbsp;<span style="color:blue;">false</span>,&nbsp;6uy),&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;10) &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="color:#a31515;">&quot;ana&quot;</span>,&nbsp;<span style="color:#2b91af;">Song</span>&nbsp;(1,&nbsp;<span style="color:blue;">false</span>,&nbsp;5uy),&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;10) &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="color:#a31515;">&quot;ana&quot;</span>,&nbsp;<span style="color:#2b91af;">Song</span>&nbsp;(2,&nbsp;&nbsp;<span style="color:blue;">true</span>,&nbsp;5uy),&nbsp;9_9990) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">RecommendationsProvider</span>.<span style="font-weight:bold;color:#74531f;">GetRecommendations</span>&nbsp;<span style="color:#a31515;">&quot;cat&quot;</span>&nbsp;|&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Interpret</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="font-weight:bold;color:#74531f;">Equal</span><span style="font-weight:bold;color:#74531f;">&lt;</span><span style="font-weight:bold;color:#74531f;">Song</span><span style="font-weight:bold;color:#74531f;">&gt;</span>&nbsp;([&nbsp;<span style="color:#2b91af;">Song</span>&nbsp;(2,&nbsp;<span style="color:blue;">true</span>,&nbsp;5uy)&nbsp;],&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>)</pre> </p> <p> Once all tests were migrated over to the new <code>GetRecommendations</code> function, I deleted the old <code>RecommendationsProvider</code> class as well as the <code>SongService</code> interface, since none of them were required any longer. </p> <h3 id="25ccf7c8525f44b29e2d43eeeb99e713"> Conclusion <a href="#25ccf7c8525f44b29e2d43eeeb99e713">#</a> </h3> <p> The lack of proper syntactic sugar, similar to <code>do</code> notation in Haskell, or <a href="https://learn.microsoft.com/dotnet/fsharp/language-reference/computation-expressions">computation expressions</a> in F#, means that free monads aren't a useful design option in C#. Still, perhaps the last three articles help a reader or two understanding what a free monad is. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/09/01/song-recommendations-with-c-free-monads Song recommendations with F# free monads https://blog.ploeh.dk/2025/08/25/song-recommendations-with-f-free-monads/ Mon, 25 Aug 2025 06:38:00 UTC <div id="post"> <p> <em>With an extensive computation expression.</em> </p> <p> This article is part of a series called <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">Alternative ways to design with functional programming</a>. As the title suggests, it examines alternative <a href="/2018/11/19/functional-architecture-a-definition">functional-programming architectures</a>. It does so by looking at the same overall example problem: Calculating song recommendations from a large data set of 'scrobbles'; records of playback data for many users. In the previous article, you saw <a href="/2025/08/18/song-recommendations-with-haskell-free-monads">how to implement the desired functionality using a free monad in Haskell</a>. In this article, you'll see how to use a free monad in <a href="https://fsharp.org/">F#</a>. </p> <p> If you are following along in the accompanying Git repository, the code shown here is from the <em>fsharp-free</em> branch. The starting point is <em>fsharp-port</em>. </p> <h3 id="88f2fcfe4cc344afb56e666a4fccdde7"> Functor <a href="#88f2fcfe4cc344afb56e666a4fccdde7">#</a> </h3> <p> A free monad enables you to define a <a href="/2022/03/28/monads">monad</a> from any <a href="/2018/03/22/functors">functor</a>. In this context, you start with the functor that models an instruction set for a domain-specific language (DSL). The goal is to replace the <code>SongService</code> interface with this instruction set. </p> <p> As a reminder, this is the interface: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">SongService</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">abstract</span>&nbsp;<span style="font-weight:bold;color:#74531f;">GetTopListenersAsync</span>&nbsp;:&nbsp;songId&nbsp;:&nbsp;<span style="color:#2b91af;">int</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">User</span>&gt;&gt; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">abstract</span>&nbsp;<span style="font-weight:bold;color:#74531f;">GetTopScrobblesAsync</span>&nbsp;:&nbsp;userName&nbsp;:&nbsp;<span style="color:#2b91af;">string</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&gt;</pre> </p> <p> I'm following the <a href="/2017/08/07/f-free-monad-recipe">F# free monad recipe</a>, which, I'm happy to report, turned out to be easy to do. </p> <p> First, the <a href="https://en.wikipedia.org/wiki/Tagged_union">sum type</a>: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">SongInstruction</span>&lt;<span style="color:#2b91af;">&#39;a</span>&gt;&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">GetTopListeners</span>&nbsp;<span style="color:blue;">of</span>&nbsp;songId&nbsp;:&nbsp;<span style="color:#2b91af;">int</span>&nbsp;*&nbsp;(<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">User</span>&gt;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">&#39;a</span>) &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">GetTopScrobbles</span>&nbsp;<span style="color:blue;">of</span>&nbsp;userName&nbsp;:&nbsp;<span style="color:#2b91af;">string</span>&nbsp;*&nbsp;(<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">&#39;a</span>)</pre> </p> <p> If you check with the F# free monad recipe and compare the <code>SongService</code> interface methods with the <code>SongInstruction</code> cases, you should be able to spot the similarity, and how to get from interface to discriminated union. </p> <p> As shown in the <a href="/2025/08/18/song-recommendations-with-haskell-free-monads">previous article</a>, in <a href="https://www.haskell.org/">Haskell</a> you can declaratively state that a type should be a <code>Functor</code> instance. In F# you have to implement it yourself. </p> <p> <pre><span style="color:blue;">module</span>&nbsp;<span style="color:#2b91af;">SongInstruction</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">map</span>&nbsp;<span style="color:#74531f;">f</span>&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">GetTopListeners</span>&nbsp;(&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">songId</span>,&nbsp;<span style="color:#74531f;">next</span>)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">GetTopListeners</span>&nbsp;(&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">songId</span>,&nbsp;<span style="color:#74531f;">next</span>&nbsp;&gt;&gt;&nbsp;<span style="color:#74531f;">f</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">GetTopScrobbles</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:#74531f;">next</span>)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">GetTopScrobbles</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:#74531f;">next</span>&nbsp;&gt;&gt;&nbsp;<span style="color:#74531f;">f</span>)</pre> </p> <p> Here I've put it in its own little module, in order to make it clear which kind of data the <code>map</code> function handles. </p> <h3 id="253e3a8880c348e3ba2ad9fabeda579b"> Monad <a href="#253e3a8880c348e3ba2ad9fabeda579b">#</a> </h3> <p> The next step is to wrap the functor in a data structure that enables you to sequence the above instructions. </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">&#39;a</span>&gt;&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Free</span>&nbsp;<span style="color:blue;">of</span>&nbsp;<span style="color:#2b91af;">SongInstruction</span>&lt;<span style="color:#2b91af;">SongProgram</span>&lt;<span style="color:#2b91af;">&#39;a</span>&gt;&gt; &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Pure</span>&nbsp;<span style="color:blue;">of</span>&nbsp;<span style="color:#2b91af;">&#39;a</span></pre> </p> <p> A <code>bind</code> function is required to make this type a proper monad: </p> <p> <pre><span style="color:blue;">module</span>&nbsp;<span style="color:#2b91af;">SongProgram</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;<span style="color:#74531f;">bind</span>&nbsp;<span style="color:#74531f;">f</span>&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Free</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">inst</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">inst</span>&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">SongInstruction</span>.<span style="color:#74531f;">map</span>&nbsp;(<span style="color:#74531f;">bind</span>&nbsp;<span style="color:#74531f;">f</span>)&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Free</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Pure</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">inst</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">f</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">inst</span></pre> </p> <p> Again, I'm slavishly following the F# free monad recipe; please refer to it for more details. </p> <h3 id="4a3cd3bd35984a30a5596b69951b9131"> Computation expression <a href="#4a3cd3bd35984a30a5596b69951b9131">#</a> </h3> <p> Technically, that's all it takes to make it possible to write programs in the little DSL. Doing it exclusively with the above <code>bind</code> function would, however, but quite cumbersome, so you'll also appreciate some syntactic sugar in the form of a <a href="https://learn.microsoft.com/dotnet/fsharp/language-reference/computation-expressions">computation expression</a>. </p> <p> As you will see shortly, I needed to (temporarily) support some imperative language constructs, so I had to make it more involved than usually required. </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">SongProgramBuilder</span>&nbsp;()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">Bind</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">x</span>,&nbsp;<span style="color:#74531f;">f</span>)&nbsp;=&nbsp;<span style="color:#2b91af;">SongProgram</span>.<span style="color:#74531f;">bind</span>&nbsp;<span style="color:#74531f;">f</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">Return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Pure</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">ReturnFrom</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">Zero</span>&nbsp;()&nbsp;=&nbsp;<span style="color:#2b91af;">Pure</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">Delay</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">f</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">f</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">Run</span>&nbsp;<span style="color:#74531f;">f</span>&nbsp;=&nbsp;<span style="color:#74531f;">f</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">While</span>&nbsp;(<span style="color:#74531f;">guard</span>,&nbsp;<span style="color:#74531f;">body</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;<span style="color:#74531f;">not</span>&nbsp;(<span style="color:#74531f;">guard</span>&nbsp;()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">then</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">Zero</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">Bind</span>&nbsp;(<span style="color:#74531f;">body</span>&nbsp;(),&nbsp;<span style="color:blue;">fun</span>&nbsp;()&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">While</span>&nbsp;(<span style="color:#74531f;">guard</span>,&nbsp;<span style="color:#74531f;">body</span>)) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">TryWith</span>&nbsp;(<span style="color:#74531f;">body</span>,&nbsp;<span style="color:#74531f;">handler</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">try</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">ReturnFrom</span>&nbsp;(<span style="color:#74531f;">body</span>&nbsp;()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">with</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">e</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">handler</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">e</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">TryFinally</span>&nbsp;(<span style="color:#74531f;">body</span>,&nbsp;<span style="color:#74531f;">compensation</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">try</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">ReturnFrom</span>&nbsp;(<span style="color:#74531f;">body</span>&nbsp;()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">finally</span>&nbsp;<span style="color:#74531f;">compensation</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">Using</span>&nbsp;(<span style="color:#1f377f;">disposable</span>&nbsp;:&nbsp;#System.<span style="color:#2b91af;">IDisposable</span>,&nbsp;<span style="color:#74531f;">body</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">body&#39;</span>&nbsp;=&nbsp;<span style="color:blue;">fun</span>&nbsp;()&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">body</span>&nbsp;<span style="color:#1f377f;">disposable</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">TryFinally</span>&nbsp;(<span style="color:#74531f;">body&#39;</span>,&nbsp;<span style="color:blue;">fun</span>&nbsp;()&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;<span style="color:#1f377f;">disposable</span>&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:blue;">null</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#1f377f;">disp</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#1f377f;">disp</span>.<span style="font-weight:bold;color:#74531f;">Dispose</span>&nbsp;()) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">For</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">sequence</span>&nbsp;:&nbsp;<span style="color:#2b91af;">seq</span>&lt;_&gt;,&nbsp;<span style="color:#74531f;">body</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">Using</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">sequence</span>.<span style="font-weight:bold;color:#74531f;">GetEnumerator</span>&nbsp;(),&nbsp;<span style="color:blue;">fun</span>&nbsp;<span style="color:#1f377f;">enum</span>&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">While</span>&nbsp;(<span style="color:#1f377f;">enum</span>.<span style="font-weight:bold;color:#74531f;">MoveNext</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">this</span>.<span style="font-weight:bold;color:#74531f;">Delay</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;()&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">body</span>&nbsp;<span style="color:#1f377f;">enum</span>.Current))) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">Combine</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">x</span>,&nbsp;<span style="color:#74531f;">y</span>)&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">SongProgram</span>.<span style="color:#74531f;">bind</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;()&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">y</span>&nbsp;())</pre> </p> <p> I had to do quite a bit of yak shaving before I got the <code>For</code> method right. Not surprisingly, Scott Wlaschin's <a href="https://fsharpforfunandprofit.com/posts/computation-expressions-intro/">series on computation expressions</a> proved invaluable. </p> <p> As you always do with computation expressions, you leave a builder object somewhere the rest of your code can see it: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;songProgram&nbsp;=&nbsp;<span style="color:#2b91af;">SongProgramBuilder</span>&nbsp;()</pre> </p> <p> You'll soon see an example of using a <code>songProgram</code> computation expression. </p> <h3 id="edfef1f9fe8440aa9fe09256e588c226"> Lifted helpers <a href="#edfef1f9fe8440aa9fe09256e588c226">#</a> </h3> <p> Although not strictly required, I often find it useful to add a helper function for each case of the instruction type: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">getTopListeners</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songId</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Free</span>&nbsp;(<span style="color:#2b91af;">GetTopListeners</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">songId</span>,&nbsp;<span style="color:#2b91af;">Pure</span>)) <span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">getTopScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Free</span>&nbsp;(<span style="color:#2b91af;">GetTopScrobbles</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:#2b91af;">Pure</span>))</pre> </p> <p> This just makes the user code look a bit cleaner. </p> <h3 id="3866c8b8d87c47e58dfa87e762c79ce5"> Imperative-looking program <a href="#3866c8b8d87c47e58dfa87e762c79ce5">#</a> </h3> <p> With all that machinery in place, you can now write a <a href="https://en.wikipedia.org/wiki/Referential_transparency">referentially transparent</a> function that implements the same algorithm as the original class method. </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">getRecommendations</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;=&nbsp;<span style="color:blue;">songProgram</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;1.&nbsp;Get&nbsp;user&#39;s&nbsp;own&nbsp;top&nbsp;scrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;2.&nbsp;Get&nbsp;other&nbsp;users&nbsp;who&nbsp;listened&nbsp;to&nbsp;the&nbsp;same&nbsp;songs</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;3.&nbsp;Get&nbsp;top&nbsp;scrobbles&nbsp;of&nbsp;those&nbsp;users</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;4.&nbsp;Aggregate&nbsp;the&nbsp;songs&nbsp;into&nbsp;recommendations</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;=&nbsp;<span style="color:#74531f;">getTopScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobblesSnapshot</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">sortByDescending</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.ScrobbleCount) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">truncate</span>&nbsp;100 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">toList</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendationCandidates</span>&nbsp;=&nbsp;<span style="color:#2b91af;">ResizeArray</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">for</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobble</span>&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobblesSnapshot</span>&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListeners</span>&nbsp;=&nbsp;<span style="color:#74531f;">getTopListeners</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobble</span>.Song.Id &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListenersSnapshot</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListeners</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">filter</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>.TotalScrobbleCount&nbsp;&gt;=&nbsp;10_000) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">sortByDescending</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>.TotalScrobbleCount) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">truncate</span>&nbsp;20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">toList</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">for</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListener</span>&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListenersSnapshot</span>&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Impure</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherScrobbles</span>&nbsp;=&nbsp;<span style="color:#74531f;">getTopScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListener</span>.UserName &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Pure</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherScrobblesSnapshot</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">otherScrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">filter</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.Song.IsVerifiedArtist) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">sortByDescending</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.Song.Rating) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">truncate</span>&nbsp;10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">toList</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">otherScrobblesSnapshot</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">List</span>.<span style="color:#74531f;">map</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.Song) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendationCandidates</span>.<span style="font-weight:bold;color:#74531f;">AddRange</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendations</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendationCandidates</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">sortByDescending</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.Rating) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">truncate</span>&nbsp;200 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">toList</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;:&gt;&nbsp;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;_&gt; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendations</span>&nbsp;}</pre> </p> <p> Notice how much it resembles the original <code>GetRecommendationsAsync</code> method on the <code>RecommendationsProvider</code> class. Instead of <code>songService.GetTopScrobblesAsync</code> it just has <code>getTopScrobbles</code>, and instead of <code>songService.GetTopListenersAsync</code> it has <code>getTopListeners</code>. The whole computation is wrapped in <code>songProgram</code>, and the return type is <code>SongProgram&lt;IReadOnlyCollection&lt;Song&gt;&gt;</code>. </p> <p> Perhaps you're wondering how the local state mutation (of <code>recommendationCandidates</code>) squares with my claim that this function is referentially transparent, but consider what referential transparency means. It means that you could replace a particular function call (say, <code>getRecommendations "cat"</code>) with the value it returns. And you can. That the function used local mutation to arrive at that return value is of no concern to the caller. </p> <p> Even so, later in this article, we'll refactor the code to something that looks more like a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a>. For now, however, we'll first see how to evaluate programs like the one returned by <code>getRecommendations</code>. </p> <h3 id="fc95832d78e74e94b6318f9cba9e3ee9"> Interpreter <a href="#fc95832d78e74e94b6318f9cba9e3ee9">#</a> </h3> <p> Again, I follow the F# free monad recipe. Since I already have a class called <code>FakeSongService</code>, adding an <code>Interpret</code> method was the easiest implementation strategy. A private recursive function takes care of the implementation: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;<span style="color:#74531f;">interpret</span>&nbsp;=&nbsp;<span style="color:blue;">function</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Pure</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Free</span>&nbsp;(<span style="color:#2b91af;">GetTopListeners</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">songId</span>,&nbsp;<span style="color:#74531f;">next</span>))&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">users</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">filter</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>.Value.<span style="font-weight:bold;color:#74531f;">ContainsKey</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songId</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">map</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">user</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>.Key&nbsp;(<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">sum</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>.Value.Values)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">toList</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">next</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">interpret</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Free</span>&nbsp;(<span style="color:#2b91af;">GetTopScrobbles</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:#74531f;">next</span>))&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">users</span>.<span style="font-weight:bold;color:#74531f;">GetOrAdd</span>(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:#2b91af;">ConcurrentDictionary</span>&lt;_,&nbsp;_&gt;&nbsp;()) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">map</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">scrobble</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>[<span style="font-weight:bold;color:#1f377f;">kvp</span>.Key]&nbsp;<span style="font-weight:bold;color:#1f377f;">kvp</span>.Value) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">toList</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">next</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">interpret</span></pre> </p> <p> The implementation closely mirrors the original <a href="http://xunitpatterns.com/Fake%20Object.html">Fake</a> interface implementation, where <code>users</code> and <code>songs</code> are class fields on <code>FakeSongService</code>. This class was first shown in <a href="/2025/04/10/characterising-song-recommendations">Characterising song recommendations</a>. </p> <p> Since I added the <code>interpret</code> function in the class, we need a method that enables client code to call it: </p> <p> <pre><span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">Interpret</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">program</span>&nbsp;=&nbsp;<span style="color:#74531f;">interpret</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">program</span></pre> </p> <p> It's now possible to rewrite all the tests. </p> <h3 id="622ba7086970434d812c0fde623eab14"> Refactoring the tests <a href="#622ba7086970434d812c0fde623eab14">#</a> </h3> <p> Since the original <code>GetRecommendationsAsync</code> method was task-based, all tests had to run in <a href="https://learn.microsoft.com/dotnet/fsharp/language-reference/task-expressions">task workflows</a>. This is no longer necessary, as this simplified <a href="https://fscheck.github.io/FsCheck/">FsCheck</a> property demonstrates: </p> <p> <pre>[&lt;<span style="color:#2b91af;">Property</span>&gt;] <span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">``One&nbsp;user,&nbsp;some&nbsp;songs``</span>&nbsp;()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">gen</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">user</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Gen</span>.userName &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Gen</span>.<span style="color:#74531f;">arrayOf</span>&nbsp;<span style="color:#2b91af;">Gen</span>.song &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbleCounts</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Gen</span>.<span style="color:#74531f;">choose</span>&nbsp;(1,&nbsp;100)&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Gen</span>.<span style="color:#74531f;">arrayOfLength</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>.Length &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">user</span>,&nbsp;<span style="color:#2b91af;">Array</span>.<span style="color:#74531f;">zip</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbleCounts</span>)&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Arb</span>.<span style="color:#74531f;">fromGen</span>&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Prop</span>.<span style="color:#74531f;">forAll</span>&nbsp;&lt;|&nbsp;<span style="color:blue;">fun</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">user</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>)&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FakeSongService</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Array</span>.<span style="color:#74531f;">iter</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">s</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">c</span>)&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">user</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">c</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#74531f;">getRecommendations</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">user</span>&nbsp;|&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Interpret</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="font-weight:bold;color:#74531f;">Empty</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span></pre> </p> <p> Originally, this test had to be defined in terms of the <code>task</code> computation expression, but now it's a pure function. In <a href="/2013/06/24/a-heuristic-for-formatting-code-according-to-the-aaa-pattern">the act phase</a> the test calls <code>getRecommendations user</code> and pipes the returned program to <code>srvc.Interpret</code>. The result, <code>actual</code>, is a plain <code>IReadOnlyCollection&lt;Song&gt;</code> value. </p> <p> Similarly, I was able to migrate all the example-based tests over, too. </p> <p> <pre>[&lt;<span style="color:#2b91af;">Fact</span>&gt;] <span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">``One&nbsp;verified&nbsp;recommendation``</span>&nbsp;()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>&nbsp;=&nbsp;<span style="color:#2b91af;">FakeSongService</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="color:#a31515;">&quot;cat&quot;</span>,&nbsp;<span style="color:#74531f;">song</span>&nbsp;1&nbsp;<span style="color:blue;">false</span>&nbsp;6uy,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;10) &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="color:#a31515;">&quot;ana&quot;</span>,&nbsp;<span style="color:#74531f;">song</span>&nbsp;1&nbsp;<span style="color:blue;">false</span>&nbsp;5uy,&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;10) &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Scrobble</span>&nbsp;(<span style="color:#a31515;">&quot;ana&quot;</span>,&nbsp;<span style="color:#74531f;">song</span>&nbsp;2&nbsp;&nbsp;<span style="color:blue;">true</span>&nbsp;5uy,&nbsp;9_9990) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="color:#74531f;">getRecommendations</span>&nbsp;<span style="color:#a31515;">&quot;cat&quot;</span>&nbsp;|&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">srvc</span>.<span style="font-weight:bold;color:#74531f;">Interpret</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="font-weight:bold;color:#74531f;">Equal</span><span style="font-weight:bold;color:#74531f;">&lt;</span><span style="font-weight:bold;color:#74531f;">Song</span><span style="font-weight:bold;color:#74531f;">&gt;</span>&nbsp;([&nbsp;<span style="color:#74531f;">song</span>&nbsp;2&nbsp;<span style="color:blue;">true</span>&nbsp;5uy&nbsp;],&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>)</pre> </p> <p> Once all tests were migrated over to the new <code>getRecommendations</code> function, I deleted the old <code>RecommendationsProvider</code> class as well as the <code>SongService</code> interface, since none of them were required any longer. Notice how I managed to move in smaller steps than in the <a href="/2025/08/18/song-recommendations-with-haskell-free-monads">previous article</a>. As described in <a href="/2021/06/14/new-book-code-that-fits-in-your-head">Code That Fits in Your Head</a>, I used the <a href="https://martinfowler.com/bliki/StranglerFigApplication.html">Strangler pattern</a> to move incrementally. I should also have done that with the Haskell code base, but fortunately I didn't run into trouble. </p> <p> With all the tests migrated to pure functions, it's time to go back to <code>getRecommendations</code> to give it some refactoring love. </p> <h3 id="a34d556e4dd646d2a17cb5f54d2a011f"> Traverse <a href="#a34d556e4dd646d2a17cb5f54d2a011f">#</a> </h3> <p> The local mutation in the above incarnation of <code>getRecommendations</code> is located within a doubly-nested loop. You typically need a <a href="/2024/11/11/traversals">traversal</a> if you want to refactor such loops to expressions. </p> <p> The traversal needs a <code>map</code> function, so we'll start with that. </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">map</span>&nbsp;<span style="color:#74531f;">f</span>&nbsp;=&nbsp;<span style="color:#74531f;">bind</span>&nbsp;(<span style="color:#74531f;">f</span>&nbsp;&gt;&gt;&nbsp;<span style="color:#2b91af;">Pure</span>)</pre> </p> <p> This function is included in the <code>SongProgram</code> module shown above. That's the reason it can call <code>bind</code> without a prefix. The same is true for the <code>traverse</code> function. </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">traverse</span>&nbsp;<span style="color:#74531f;">f</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">xs</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">concat</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">xs</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">ys</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">xs</span>&nbsp;|&gt;&nbsp;<span style="color:#74531f;">bind</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">ys</span>&nbsp;|&gt;&nbsp;<span style="color:#74531f;">map</span>&nbsp;(<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">append</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>)) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">fold</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">acc</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">concat</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">acc</span>&nbsp;(<span style="color:#74531f;">f</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">x</span>&nbsp;|&gt;&nbsp;<span style="color:#74531f;">map</span>&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">singleton</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(<span style="color:#2b91af;">Pure</span>&nbsp;(<span style="color:#2b91af;">Seq</span>.empty)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">xs</span></pre> </p> <p> The local <code>concat</code> function concatenates two <code>SongProgram</code> values that contain sequences to a single <code>SongProgram</code> value containing the concatenated sequence. The traversal uses this helper function to <code>fold</code> over the <code>xs</code>. </p> <h3 id="615a74cc93364179a78a4e55679d6577"> Refactored program <a href="#615a74cc93364179a78a4e55679d6577">#</a> </h3> <p> You can now go through all the usual motions of replacing the nested loops and the local mutation with traversal, extracting helper functions and so on. If you're interested in the <a href="https://stackoverflow.blog/2022/12/19/use-git-tactically/">small steps</a> I took, you may consult the Git repository. Here, I only present the <code>getRecommendations</code> function in the state I decided to leave it. </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:#74531f;">getRecommendations</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;=&nbsp;<span style="color:blue;">songProgram</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;1.&nbsp;Get&nbsp;user&#39;s&nbsp;own&nbsp;top&nbsp;scrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;2.&nbsp;Get&nbsp;other&nbsp;users&nbsp;who&nbsp;listened&nbsp;to&nbsp;the&nbsp;same&nbsp;songs</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;3.&nbsp;Get&nbsp;top&nbsp;scrobbles&nbsp;of&nbsp;those&nbsp;users</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;4.&nbsp;Aggregate&nbsp;the&nbsp;songs&nbsp;into&nbsp;recommendations</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;=&nbsp;<span style="color:#74531f;">getTopScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherlListeners</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#74531f;">getUsersOwnTopScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">SongProgram</span>.<span style="color:#74531f;">traverse</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">getTopListeners</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.Song.Id) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherScrobbles</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">otherlListeners</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">collect</span>&nbsp;<span style="color:#74531f;">getOtherUsersWhoListenedToTheSameSongs</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">SongProgram</span>.<span style="color:#74531f;">traverse</span>&nbsp;(<span style="color:blue;">fun</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#74531f;">getTopScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>.UserName) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">otherScrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">collect</span>&nbsp;<span style="color:#74531f;">getTopScrobblesOfUsers</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">aggregateTheSongsIntoRecommendations</span>&nbsp;}</pre> </p> <p> Notice the two applications of <code>traverse</code>, which replace the twice-nested loop. </p> <p> The type of <code>getRecommendations</code> is unchanged, and all tests still pass. </p> <h3 id="32d20c7df6384010902d6cb53526e9d6"> Conclusion <a href="#32d20c7df6384010902d6cb53526e9d6">#</a> </h3> <p> As expected, it required more boilerplate code to refactor the <code>GetRecommendationsAsync</code> method to a design based on a free monad, than the corresponding refactoring did in Haskell. Even so, following the F# free monad recipe made it was smooth sailing. I did, however, hit a snag, mostly of my own manufacture, when implementing support for <code>for</code> loops in the computation expression builder, but that problem turned out to be unrelated to the free monad. </p> <p> Again, you may wonder what the point is. First, I'll refer you to the decision flowchart in the <a href="/2017/08/07/f-free-monad-recipe">F# free monad recipe</a>, as well as remind you that these articles are all intended to be descriptive rather than prescriptive. They only present what is possible. It's up to you to decide which option to choose. </p> <p> Second, a <code>SongProgram&lt;'a&gt;</code> may look similar to an interface, but consider how much more restricted it is. A <a href="/2017/01/30/partial-application-is-dependency-injection">method that uses dependency injection is inherently impure</a>; in such a method, everything may happen, including every kind of bug. </p> <p> The F# type system does not check whether or not unconstrained side effects or non-determinism takes place, but still, a type like <code>SongProgram&lt;'a&gt;</code> strongly suggests that only <code>SongProgram</code>-related actions take place. </p> <p> I think that free monads still have a place in F#, although mostly as a niche use case. In C#, on the other hand, free monads aren't useful because the language lacks features to make this kind of programming workable. Still, for demonstration purposes only, it <em>can</em> be done. </p> <p> <strong>Next:</strong> <a href="/2025/09/01/song-recommendations-with-c-free-monads">Song recommendations with C# free monads</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/08/25/song-recommendations-with-f-free-monads Song recommendations with Haskell free monads https://blog.ploeh.dk/2025/08/18/song-recommendations-with-haskell-free-monads/ Mon, 18 Aug 2025 05:44:00 UTC <div id="post"> <p> <em>A surprisingly easy refactoring.</em> </p> <p> This article is part of a larger series titled <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">Alternative ways to design with functional programming</a>. In short, it uses <a href="https://www.haskell.org/">Haskell</a>, <a href="https://fsharp.org/">F#</a>, and C# to present various internal architectures to deal with an example problem. Please refer to the table of contents included with the <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">first article</a> to get a sense of what has already been covered. </p> <p> In this article, you'll see <a href="/2025/08/11/song-recommendations-with-free-monads">how a free monad may be used to address the problem</a> that when data size is sufficiently large, you may need to load it piecemeal, based on the results of previous steps in an algorithm. In short, the problem being addressed is to calculate a list of song recommendations based on so-called 'scrobble' data from a multitude of other users' music playback history. </p> <p> If you want to follow along with the Git repository, the code presented here is from the Haskell repository's <em>free</em> branch. </p> <h3 id="efc53e7ce8b747ddb18acd0958527b06"> Starting point <a href="#efc53e7ce8b747ddb18acd0958527b06">#</a> </h3> <p> Instead of starting from scratch from the code base presented in <a href="/2025/04/21/porting-song-recommendations-to-haskell">Porting song recommendations to Haskell</a>, I'll start at what was an interim refactoring step in <a href="/2025/06/30/song-recommendations-from-haskell-combinators">Song recommendations from Haskell combinators</a>: </p> <p> <pre><span style="color:#2b91af;">getRecommendations</span>&nbsp;<span style="color:blue;">::</span>&nbsp;<span style="color:blue;">SongService</span>&nbsp;a&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">String</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;[<span style="color:blue;">Song</span>] getRecommendations&nbsp;srvc&nbsp;un&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:green;">--&nbsp;1.&nbsp;Get&nbsp;user&#39;s&nbsp;own&nbsp;top&nbsp;scrobbles </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;2.&nbsp;Get&nbsp;other&nbsp;users&nbsp;who&nbsp;listened&nbsp;to&nbsp;the&nbsp;same&nbsp;songs </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;3.&nbsp;Get&nbsp;top&nbsp;scrobbles&nbsp;of&nbsp;those&nbsp;users </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;4.&nbsp;Aggregate&nbsp;the&nbsp;songs&nbsp;into&nbsp;recommendations </span> &nbsp;&nbsp;<span style="color:green;">--&nbsp;Impure </span>&nbsp;&nbsp;scrobbles&nbsp;&lt;-&nbsp;getTopScrobbles&nbsp;srvc&nbsp;un &nbsp;&nbsp;<span style="color:green;">--&nbsp;Pure </span>&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;scrobblesSnapshot&nbsp;=&nbsp;<span style="color:blue;">take</span>&nbsp;100&nbsp;$&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;scrobbleCount)&nbsp;scrobbles &nbsp;&nbsp;<span style="color:green;">--&nbsp;Impure </span>&nbsp;&nbsp;recommendations&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;join&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;traverse&nbsp;(\scrobble&nbsp;-&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;join&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;traverse&nbsp;(\otherListener&nbsp;-&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;scrobbledSong&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">take</span>&nbsp;10&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;songRating&nbsp;.&nbsp;scrobbledSong)&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">filter</span>&nbsp;(songHasVerifiedArtist&nbsp;.&nbsp;scrobbledSong)&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;getTopScrobbles&nbsp;srvc&nbsp;(userName&nbsp;otherListener))&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">take</span>&nbsp;20&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;userScrobbleCount)&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">filter</span>&nbsp;((10_000&nbsp;&lt;=)&nbsp;.&nbsp;userScrobbleCount)&nbsp;=&lt;&lt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;getTopListeners&nbsp;srvc&nbsp;(songId&nbsp;$&nbsp;scrobbledSong&nbsp;scrobble)) &nbsp;&nbsp;&nbsp;&nbsp;scrobblesSnapshot &nbsp;&nbsp;<span style="color:green;">--&nbsp;Pure </span>&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;<span style="color:blue;">take</span>&nbsp;200&nbsp;$&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;songRating)&nbsp;recommendations</pre> </p> <p> The reason I wanted to start here is that with the <code>IORef</code> out of the way, the only <code>IO</code>-bound code remaining involves the <code>SongService</code> methods. </p> <p> The plan is to replace the <code>SongService</code> type class with a free monad. Once that's done, there's no more <code>IO</code> left; it will have been replaced by the free monad. That's why it's easiest to first get rid of everything else involving <code>IO</code>. If I didn't, the refactoring wouldn't be as easy. As Kent Beck wrote, </p> <blockquote> <p> "for each desired change, make the change easy (warning: this may be hard), then make the easy change" </p> <footer><cite><a href="https://x.com/kentbeck/status/250733358307500032">Tweet</a>, Kent Beck, 2012</cite></footer> </blockquote> <p> Starting from the above incarnation of the code makes the change easy. </p> <h3 id="1d5af97b6c2542698aa20cb449cc771e"> Functor <a href="#1d5af97b6c2542698aa20cb449cc771e">#</a> </h3> <p> As a reminder, this type class is the one I'm getting rid of: </p> <p> <pre><span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">SongService</span>&nbsp;a&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;<span style="color:#2b91af;">getTopListeners</span>&nbsp;<span style="color:blue;">::</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">Int</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;[<span style="color:blue;">User</span>] &nbsp;&nbsp;<span style="color:#2b91af;">getTopScrobbles</span>&nbsp;<span style="color:blue;">::</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">String</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#2b91af;">IO</span>&nbsp;[<span style="color:blue;">Scrobble</span>]</pre> </p> <p> Converting such an 'interface' to a <a href="https://en.wikipedia.org/wiki/Tagged_union">sum type</a> of instructions is such a well-defined process that I think it could be automated (<a href="https://xkcd.com/1205/">if it were worth the effort</a>). You take each method of the type class and make it a case in the sum type. </p> <p> <pre><span style="color:blue;">data</span>&nbsp;SongInstruction&nbsp;a&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;GetTopListeners&nbsp;Int&nbsp;([User]&nbsp;-&gt;&nbsp;a) &nbsp;&nbsp;|&nbsp;GetTopScrobbles&nbsp;String&nbsp;([Scrobble]&nbsp;-&gt;&nbsp;a) &nbsp;&nbsp;<span style="color:blue;">deriving</span>&nbsp;(<span style="color:#2b91af;">Functor</span>)</pre> </p> <p> I usually think of such a type as representing possible instructions in a little domain-specific language (DSL). In this case, the DSL allows only two instructions: <code>GetTopListeners</code> and <code>GetTopScrobbles</code>. </p> <p> If you've never seen a free monad before, you may be wondering: <em>What's the <code>a</code>?</em> It's what we may call the <em>carrier type</em>. If you haven't worked with, say, <a href="https://bartoszmilewski.com/2017/02/28/f-algebras/">F-Algebras</a>, this takes some time getting used to, but the carrier type represents a 'potential'. As presented here, it may be anything, but when you want to evaluate or 'run' the program, the <code>a</code> turns out to be the return type of the evaluation. </p> <p> Since <code>SongInstruction</code> is a <code>Functor</code>, it's possible to map <code>a</code> to <code>b</code>, or one concrete type to another, so that the <code>a</code> type parameter can take on more than one concrete type during a small 'program' written in the DSL. </p> <p> In any case, at this point, <code>SongInstruction a</code> is only a <code>Functor</code>, and not yet a <code>Monad</code>. </p> <h3 id="44bb4cf9252b4eeb8ae0fe302a4cbd42"> Free monad <a href="#44bb4cf9252b4eeb8ae0fe302a4cbd42">#</a> </h3> <p> You may, if you want to, introduce a type alias that makes <code>SongInstruction a</code> (or, rather, its <code>Free</code> wrapper) a <code>Monad</code>. </p> <p> <pre><span style="color:blue;">type</span>&nbsp;SongProgram&nbsp;=&nbsp;Free&nbsp;SongInstruction</pre> </p> <p> The <code>Free</code> wrapper comes from <a href="https://hackage.haskell.org/package/free/docs/Control-Monad-Free.html">Control.Monad.Free</a>. </p> <p> In the rest of the code listings in this article, I make no use of this type alias, so I only present it here because it's the type <a href="https://en.wikipedia.org/wiki/Glasgow_Haskell_Compiler">the compiler</a> will infer when running the test. In other words, while never explicitly stated, this is going to be the de-facto free monad in this article. </p> <h3 id="368a9eb18f5846d49896baacf66fbb25"> From action to function <a href="#368a9eb18f5846d49896baacf66fbb25">#</a> </h3> <p> Changing the <code>getRecommendations</code> action to a function that returns (effectively) <code>Free (SongInstruction [Song])</code> turned out to be easier than I had expected. </p> <p> Since I've <a href="/2024/11/04/pendulum-swing-no-haskell-type-annotation-by-default">decided to omit type declarations whenever possible</a>, refactoring is easier because the type inferencing system can allow changes to function and action types to ripple through to the ultimate callers. (To be clear, however, I here show some of the code with type annotations. I've only added those in the process of writing this article, as an aid to you, the reader. You will not find those type annotations in the Git repository.) </p> <p> First, I added a few helper methods to create 'program instructions': </p> <p> <pre>getTopListeners&nbsp;sid&nbsp;=&nbsp;liftF&nbsp;$&nbsp;GetTopListeners&nbsp;sid&nbsp;<span style="color:blue;">id</span> getTopScrobbles&nbsp;un&nbsp;=&nbsp;liftF&nbsp;$&nbsp;GetTopScrobbles&nbsp;un&nbsp;<span style="color:blue;">id</span></pre> </p> <p> The <code>liftF</code> function wraps a <code>Functor</code> (here, <code>SongInstruction</code>) in a free monad. This makes it easer to write programs in that DSL. </p> <p> The only changes now required to <code>getRecommendations</code> is to remove <code>srvc</code> in four places: </p> <p> <pre><span style="color:#2b91af;">getRecommendations</span>&nbsp;<span style="color:blue;">::</span>&nbsp;<span style="color:blue;">MonadFree</span>&nbsp;<span style="color:blue;">SongInstruction</span>&nbsp;m&nbsp;<span style="color:blue;">=&gt;</span>&nbsp;<span style="color:#2b91af;">String</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;m&nbsp;[<span style="color:blue;">Song</span>] getRecommendations&nbsp;un&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:green;">--&nbsp;1.&nbsp;Get&nbsp;user&#39;s&nbsp;own&nbsp;top&nbsp;scrobbles </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;2.&nbsp;Get&nbsp;other&nbsp;users&nbsp;who&nbsp;listened&nbsp;to&nbsp;the&nbsp;same&nbsp;songs </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;3.&nbsp;Get&nbsp;top&nbsp;scrobbles&nbsp;of&nbsp;those&nbsp;users </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;4.&nbsp;Aggregate&nbsp;the&nbsp;songs&nbsp;into&nbsp;recommendations </span> &nbsp;&nbsp;<span style="color:green;">--&nbsp;Impure </span>&nbsp;&nbsp;scrobbles&nbsp;&lt;-&nbsp;getTopScrobbles&nbsp;un &nbsp;&nbsp;<span style="color:green;">--&nbsp;Pure </span>&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;scrobblesSnapshot&nbsp;=&nbsp;<span style="color:blue;">take</span>&nbsp;100&nbsp;$&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;scrobbleCount)&nbsp;scrobbles &nbsp;&nbsp;<span style="color:green;">--&nbsp;Impure </span>&nbsp;&nbsp;recommendations&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;join&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;traverse&nbsp;(\scrobble&nbsp;-&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;join&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;traverse&nbsp;(\otherListener&nbsp;-&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;scrobbledSong&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">take</span>&nbsp;10&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;songRating&nbsp;.&nbsp;scrobbledSong)&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">filter</span>&nbsp;(songHasVerifiedArtist&nbsp;.&nbsp;scrobbledSong)&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;getTopScrobbles&nbsp;(userName&nbsp;otherListener))&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">take</span>&nbsp;20&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;userScrobbleCount)&nbsp;. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">filter</span>&nbsp;((10_000&nbsp;&lt;=)&nbsp;.&nbsp;userScrobbleCount)&nbsp;=&lt;&lt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;getTopListeners&nbsp;(songId&nbsp;$&nbsp;scrobbledSong&nbsp;scrobble)) &nbsp;&nbsp;&nbsp;&nbsp;scrobblesSnapshot &nbsp;&nbsp;<span style="color:green;">--&nbsp;Pure </span>&nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;<span style="color:blue;">take</span>&nbsp;200&nbsp;$&nbsp;sortOn&nbsp;(Down&nbsp;.&nbsp;songRating)&nbsp;recommendations</pre> </p> <p> It's almost the same code as before. The only difference is that <code>srvc</code> is not longer a parameter to either <code>getRecommendations</code>, <code>getTopListeners</code>, or <code>getTopScrobbles</code>. </p> <p> Again, I'll point out that I've only added the type annotation for the benefit of you, the reader. We see now, however, that the return type is <code>m [Song]</code>, where <code>m</code> is any <code>MonadFree SongInstruction</code>. </p> <h3 id="9ebdd39dee9a4b3f949de971fb2b3801"> Interpreter <a href="#9ebdd39dee9a4b3f949de971fb2b3801">#</a> </h3> <p> As described in <a href="/2025/04/21/porting-song-recommendations-to-haskell">Porting song recommendations to Haskell</a> I use a <code>FakeSongService</code> as a <a href="https://martinfowler.com/bliki/TestDouble.html">Test Double</a>. <code>SongService</code> is now gone, but I can repurpose the instance implementation as an interpreter of <code>SongInstruction</code> programs. </p> <p> <pre><span style="color:#2b91af;">interpret</span>&nbsp;<span style="color:blue;">::</span>&nbsp;<span style="color:blue;">FakeSongService</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">Free</span>&nbsp;<span style="color:blue;">SongInstruction</span>&nbsp;a&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;a interpret&nbsp;(FakeSongService&nbsp;ss&nbsp;us)&nbsp;=&nbsp;iter&nbsp;eval &nbsp;&nbsp;<span style="color:blue;">where</span> &nbsp;&nbsp;&nbsp;&nbsp;eval&nbsp;(GetTopListeners&nbsp;sid&nbsp;next)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">uncurry</span>&nbsp;User&nbsp;&lt;$&gt; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map.toList&nbsp;(<span style="color:blue;">sum</span>&nbsp;&lt;$&gt;&nbsp;Map.<span style="color:blue;">filter</span>&nbsp;(Map.member&nbsp;sid)&nbsp;us) &nbsp;&nbsp;&nbsp;&nbsp;eval&nbsp;(GetTopScrobbles&nbsp;un&nbsp;next)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">fmap</span>&nbsp;(\(sid,&nbsp;c)&nbsp;-&gt;&nbsp;Scrobble&nbsp;(ss&nbsp;!&nbsp;sid)&nbsp;c)&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map.toList&nbsp;$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Map.findWithDefault&nbsp;Map.empty&nbsp;un&nbsp;us</pre> </p> <p> Compare that code to the previous <code>SongService</code> instance shown in <a href="/2025/04/21/porting-song-recommendations-to-haskell">Porting song recommendations to Haskell</a>. The functions are nearly identical, only <code>return</code> is replaced by <code>next</code>, and a few other, minute changes. </p> <h3 id="f46a84de631943c0a1d3f59d9fcfc5e8"> Test changes <a href="#f46a84de631943c0a1d3f59d9fcfc5e8">#</a> </h3> <p> The hardest part of this refactoring was to adjust the tests. As I've described in <a href="/2021/06/14/new-book-code-that-fits-in-your-head">Code That Fits in Your Head</a>, I don't like when I have to change the System Under Test and the test code in the same commit, but in this case I lacked the skill to do it more incrementally. </p> <p> The issue is that since <code>SongService</code> methods were <code>IO</code>-bound, the tests ran in <code>IO</code>. Particularly for the <a href="https://hackage.haskell.org/package/QuickCheck">QuickCheck</a> properties, I had to remove the <code>ioProperty</code> and <code>monadicIO</code> combinators. This also meant adjusting some of the assertions. The <code>"One user, some songs"</code> test now looks like this: </p> <p> <pre>testProperty&nbsp;<span style="color:#a31515;">&quot;One&nbsp;user,&nbsp;some&nbsp;songs&quot;</span>&nbsp;$&nbsp;\ &nbsp;&nbsp;(ValidUserName&nbsp;user) &nbsp;&nbsp;(<span style="color:blue;">fmap</span>&nbsp;getSong&nbsp;-&gt;&nbsp;songs) &nbsp;&nbsp;-&gt;&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;scrobbleCounts&nbsp;&lt;-&nbsp;vectorOf&nbsp;(<span style="color:blue;">length</span>&nbsp;songs)&nbsp;$&nbsp;choose&nbsp;(1,&nbsp;100) &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;scrobbles&nbsp;=&nbsp;<span style="color:blue;">zip</span>&nbsp;songs&nbsp;scrobbleCounts &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;srvc&nbsp;=&nbsp;<span style="color:blue;">foldr</span>&nbsp;(<span style="color:blue;">uncurry</span>&nbsp;(scrobble&nbsp;user))&nbsp;emptyService&nbsp;scrobbles &nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;actual&nbsp;=&nbsp;interpret&nbsp;srvc&nbsp;$&nbsp;getRecommendations&nbsp;user &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;counterexample&nbsp;<span style="color:#a31515;">&quot;Should&nbsp;be&nbsp;empty&quot;</span>&nbsp;(<span style="color:blue;">null</span>&nbsp;actual)</pre> </p> <p> Notice the interpreter in action, to the left of the application of <code>getRecommendations</code>. Since <code>interpret</code> reduces any <code>Free SongInstruction a</code> to <code>a</code>, it evaluates <code>Free SongInstruction [Song]</code> to <code>[Song]</code>; that's the type of <code>actual</code>. </p> <p> The change represents a net benefit in my view. All tests are now pure, instead of running in <code>IO</code>. This makes them simpler. </p> <h3 id="8e30c90a008d4a0088ab79a4a6d15532"> Final refactoring <a href="#8e30c90a008d4a0088ab79a4a6d15532">#</a> </h3> <p> The above version of the code was only a good starting point for making the changeover to a free monad. Extracting the usual helper functions, you can arrive at this variation of the <code>getRecommendations</code> function: </p> <p> <pre>getRecommendations&nbsp;un&nbsp;=&nbsp;<span style="color:blue;">do</span> &nbsp;&nbsp;<span style="color:green;">--&nbsp;1.&nbsp;Get&nbsp;user&#39;s&nbsp;own&nbsp;top&nbsp;scrobbles </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;2.&nbsp;Get&nbsp;other&nbsp;users&nbsp;who&nbsp;listened&nbsp;to&nbsp;the&nbsp;same&nbsp;songs </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;3.&nbsp;Get&nbsp;top&nbsp;scrobbles&nbsp;of&nbsp;those&nbsp;users </span>&nbsp;&nbsp;<span style="color:green;">--&nbsp;4.&nbsp;Aggregate&nbsp;the&nbsp;songs&nbsp;into&nbsp;recommendations </span> &nbsp;&nbsp;userTops&nbsp;&lt;-&nbsp;getTopScrobbles&nbsp;un&nbsp;&lt;&amp;&gt;&nbsp;getUsersOwnTopScrobbles &nbsp;&nbsp;otherListeners&nbsp;&lt;-&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;traverse&nbsp;(getTopListeners&nbsp;.&nbsp;(songId&nbsp;.&nbsp;scrobbledSong))&nbsp;userTops&nbsp;&lt;&amp;&gt; &nbsp;&nbsp;&nbsp;&nbsp;getOtherUsersWhoListenedToTheSameSongs&nbsp;.&nbsp;join &nbsp;&nbsp;songs&nbsp;&lt;- &nbsp;&nbsp;&nbsp;&nbsp;traverse&nbsp;(getTopScrobbles&nbsp;.&nbsp;userName)&nbsp;otherListeners&nbsp;&lt;&amp;&gt; &nbsp;&nbsp;&nbsp;&nbsp;getTopScrobblesOfOtherUsers&nbsp;.&nbsp;join &nbsp;&nbsp;<span style="color:blue;">return</span>&nbsp;$&nbsp;aggregateTheSongsIntoRecommendations&nbsp;songs</pre> </p> <p> Again, it looks a lot like one of the variations shown in <a href="/2025/04/21/porting-song-recommendations-to-haskell">Porting song recommendations to Haskell</a>, just without the <code>srvc</code> parameter. </p> <h3 id="e7f18ceb9a9d45a19bfea1f248ee872e"> Conclusion <a href="#e7f18ceb9a9d45a19bfea1f248ee872e">#</a> </h3> <p> Refactoring from a type class, which in other languages could be an interface, is so easy that you may rightfully ask what the point is. To me, the most important benefit is that you restrict your options. As I discussed in a podcast episode some years ago, <a href="https://www.dotnetrocks.com/details/1542">constraints liberate</a>. Here, we move from allowing <em>anything</em> (<code>IO</code>) to only allowing a limited set of instructions. </p> <p> You could argue that a 'real' interpreter (rather than a test-specific interpreter) might run in <code>IO</code>, such as the <a href="/2017/06/28/pure-times-in-haskell">interpreter shown here</a>. Still, I would argue that most interpreters are smaller, and more stable, than the programs you may write with free monads. Thus, the amount of code you have to review that's allowed to do anything is smaller than it otherwise would have been. </p> <p> In any case, refactoring to a free monad wasn't too difficult in Haskell. How easy is it in F#? </p> <p> <strong>Next:</strong> <a href="/2025/08/25/song-recommendations-with-f-free-monads">Song recommendations with F# free monads</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/08/18/song-recommendations-with-haskell-free-monads Song recommendations with free monads https://blog.ploeh.dk/2025/08/11/song-recommendations-with-free-monads/ Mon, 11 Aug 2025 06:04:00 UTC <div id="post"> <p> <em>A Golden Hammer.</em> </p> <p> This article is part of a larger article series about <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">alternative ways to design with functional programming</a>, particularly when faced with massive data loads. In previous articles in the series, you've seen various alternatives that may or may not enable you to solve the example problem using functional programming. Each of the previous alternatives, <a href="/2025/04/28/song-recommendations-as-an-impureim-sandwich">applying the Recawr Sandwich pattern</a>, <a href="/2025/06/09/song-recommendations-from-combinators">employing functional combinators</a>, or <a href="/2025/07/14/song-recommendations-with-pipes-and-filters">using pipes and filters</a>, came with some trade-offs. Either there were limits to the practicality of the architecture, or it wasn't really functional after all. </p> <p> In this, and the following three articles, we finally reach for a universal solution: Free monads. </p> <p> By <em>universal</em> I mean: It's always possible to do this (if your language supports it). It doesn't follow that it's always a good idea. </p> <p> So there are trade-offs here, too. </p> <p> As is usually the case, although sometimes I forget to write it, this and the following articles are <em>descriptive</em>, not prescriptive. In no way do I insist that things must be done this way. I only present examples as options. </p> <h3 id="137ca70378114954a7905e93ba8c21a8"> The last resort <a href="#137ca70378114954a7905e93ba8c21a8">#</a> </h3> <p> If using a free monad is a universal possibility, then why is that not the default option? Why have I waited this long in the article series before covering it? </p> <p> For more than a single reason. </p> <p> It's an 'advanced' technique, and I predict that to many programmers, it looks like black magic. If you're working with a team unready for free monads, foisting it upon them are unlikely to lead to anything good. </p> <p> The following story may illustrate the problem. It's not about free monads, but rather about Dependency Injection (DI) Containers. A specific one, actually. I was consulting with a team, working as a temporary lead developer for about half a year. I made a number of technical decisions, some of them good and others not so much. Among the latter was the decision to use the <a href="https://www.castleproject.org/projects/windsor/">Castle Windsor</a> DI Container. </p> <p> Not that Castle Windsor was a bad library. After having done the research and written <a href="/ref/diidn">a book</a>, I considered it the best DI Container available. </p> <p> The problem, rather, was that the rest of the team considered it 'automagical'. Not that they weren't sophisticated programmers, but they had no interest learning the Castle Windsor API. They didn't consider it part of their core work, and they didn't think it provided enough benefit compared to the maintenance burden it imposed. </p> <p> They humoured me as long as I stayed on, but also explicitly told me that they'd rip it out as soon as I was gone. In the meantime, I became the Castle Windsor bottleneck. Everything related to that piece of technology had to go through me, since I was the only person who understood how it worked. </p> <p> A few years later, I returned to that team and that code base on a new project, and they'd kept their word. They'd removed Castle Windsor in favour of <a href="/2014/06/10/pure-di">Pure DI</a>, bless them. </p> <p> This experience was crucial in making me realize that, despite their intellectual attraction, DI Containers are rarely the correct choice. </p> <p> Free monads look to me as though they belong to the same category. While I don't have a similar story to tell, I'm wary of recommending them unless other options are played out. I'll refer you to the decision flowchart in the article <a href="/2017/08/07/f-free-monad-recipe">F# free monad recipe</a>. </p> <h3 id="3c98545a69c042f19a304ac36db1392f"> Language support <a href="#3c98545a69c042f19a304ac36db1392f">#</a> </h3> <p> Another concern about free monads is whether your language of choice supports them. They fit perfectly in <a href="https://www.haskell.org/">Haskell</a>, which is also the reason I start this sub-series of articles with a Haskell example. </p> <ul> <li><a href="/2025/08/18/song-recommendations-with-haskell-free-monads">Song recommendations with Haskell free monads</a></li> <li><a href="/2025/08/25/song-recommendations-with-f-free-monads">Song recommendations with F# free monads</a></li> <li><a href="/2025/09/01/song-recommendations-with-c-free-monads">Song recommendations with C# free monads</a></li> </ul> <p> In F# you'll have to do some more legwork, but once you've added the required infrastructure, the 'user code' based on free monads is perfectly fine. </p> <p> C#, on the other hand, doesn't have all the language features that will make free monads a good experience. I wouldn't suggest using a free monad in C#. I include the article with the C# free monad for demonstration purposes only. </p> <p> These articles will not introduce free monads to novice readers. For a gentler introduction, see the article series <a href="/2017/07/10/pure-interactions">Pure interactions</a>. </p> <h3 id="2d17efd5d83346ddb73c33d991da8096"> Conclusion <a href="#2d17efd5d83346ddb73c33d991da8096">#</a> </h3> <p> When all else fails, and you just <em>must</em> write <a href="https://en.wikipedia.org/wiki/Pure_function">pure functions</a>, reach for free monads. They are not for everyone, or every language, but they do offer a functional solution to problems with large data sets or rich interaction with users or the environment. </p> <p> <strong>Next:</strong> <a href="/2025/08/18/song-recommendations-with-haskell-free-monads">Song recommendations with Haskell free monads</a>. </p> </div><hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/08/11/song-recommendations-with-free-monads Testing races with a synchronizing Decorator https://blog.ploeh.dk/2025/08/04/testing-races-with-a-synchronizing-decorator/ Mon, 04 Aug 2025 07:24:00 UTC <div id="post"> <p> <em>Synchronized database reads for testing purposes.</em> </p> <p> In a previous article, you saw how to use a <a href="/2025/06/02/testing-races-with-a-slow-decorator">slow Decorator to test for race conditions.</a> Towards the end, I discussed how that solution is only near-deterministic. In this article, I discuss a technique which is, I think, properly deterministic, but unfortunately less elegant. </p> <p> In short, it works by letting a <a href="https://en.wikipedia.org/wiki/Decorator_pattern">Decorator</a> synchronize reads. </p> <h3 id="867f586443864351a77bbeb8d2e00859"> The problem <a href="#867f586443864351a77bbeb8d2e00859">#</a> </h3> <p> In the previous article, I used words to describe the problem, but really, I should be showing, not telling. Here's a variation on the previous test that exemplifies the problem. </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">NoOverbookingRace</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">date</span>&nbsp;=&nbsp;<span style="color:#2b91af;">DateTime</span>.Now.Date.<span style="font-weight:bold;color:#74531f;">AddDays</span>(1).<span style="font-weight:bold;color:#74531f;">AddHours</span>(18.5); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">using</span>&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">service</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RestaurantService</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">using</span>&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">slowService</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;repo&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">service</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">SlowReservationsRepository</span>(<span style="color:#2b91af;">TimeSpan</span>.<span style="color:#74531f;">FromMilliseconds</span>(100),&nbsp;repo); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">task1</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">slowService</span>.<span style="font-weight:bold;color:#74531f;">PostReservation</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationDtoBuilder</span>() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithDate</span>(<span style="font-weight:bold;color:#1f377f;">date</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithQuantity</span>(10) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Build</span>()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="color:#2b91af;">Task</span>.<span style="color:#74531f;">Delay</span>(<span style="color:#2b91af;">TimeSpan</span>.<span style="color:#74531f;">FromSeconds</span>(1)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">task2</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">slowService</span>.<span style="font-weight:bold;color:#74531f;">PostReservation</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationDtoBuilder</span>() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithDate</span>(<span style="font-weight:bold;color:#1f377f;">date</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithQuantity</span>(10) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Build</span>()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="color:#2b91af;">Task</span>.<span style="color:#74531f;">WhenAll</span>(<span style="font-weight:bold;color:#1f377f;">task1</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">task2</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Single</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>.StatusCode&nbsp;==&nbsp;<span style="color:#2b91af;">HttpStatusCode</span>.InternalServerError); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">ok</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Single</span>(<span style="font-weight:bold;color:#1f377f;">actual</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>.IsSuccessStatusCode); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Check&nbsp;that&nbsp;the&nbsp;reservation&nbsp;was&nbsp;actually&nbsp;created:</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">resp</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">service</span>.<span style="font-weight:bold;color:#74531f;">GetReservation</span>(<span style="font-weight:bold;color:#1f377f;">ok</span>.Headers.Location); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">resp</span>.<span style="font-weight:bold;color:#74531f;">EnsureSuccessStatusCode</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">resp</span>.<span style="font-weight:bold;color:#74531f;">ParseJsonContent</span>&lt;<span style="color:#2b91af;">ReservationDto</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Equal</span>(10,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.Quantity); }</pre> </p> <p> Apart from a single new line of code, this is is identical to the test shown in the previous article. The added line is the <code>Task.Delay</code> between <code>task1</code> and <code>task2</code>. </p> <p> What's the point of adding this delay there? Only to <em>demonstrate</em> a problem. That's one of the situations I described in the previous article: Even though the test starts both tasks without awaiting them, they aren't guaranteed to run in parallel. Both start as soon as they're created, so <code>task2</code> is going to be ever so slightly behind <code>task1</code>. What happens if there's a delay between the creation of these two tasks? </p> <p> Here I've explicitly introduced such a delay for demonstration purposes, but such a delay could happen on a real system for a number of reasons, including garbage collection, thread starvation, the OS running a higher-priority task, etc. </p> <p> Why might that pause matter? </p> <p> Because it may produce <a href="https://en.wikipedia.org/wiki/False_positives_and_false_negatives">false negatives</a>. Imagine a situation where there's <em>no</em> transaction control; where there's no <a href="https://learn.microsoft.com/dotnet/api/system.transactions.transactionscope">TransactionScope</a> around the database interactions. If the pause is long enough, the tasks effectively run in sequence (instead of in parallel), in which case the system correctly rejects the second attempt. </p> <p> This is even when using the <code>SlowReservationsRepository</code> Decorator. </p> <p> How long does the pause need to be before this happens? </p> <p> As described in the previous article, with a configured delay of 100 ms for the <code>SlowReservationsRepository</code>, creating a new reservation is delayed by 300 ms. This bears out. Experimenting on my own machine, if I change that explicit, artificial delay to 300 ms, and remove the transaction control, the test sometimes fails, and sometimes passes. With the above one-second delay, the test always passes, even when transaction control is missing. </p> <p> You could decide that a 300 ms pause at just the worst possible time is so unlikely that you're willing to simply accept those odds. I would probably be, too. Still, <a href="/2018/11/12/what-to-test-and-not-to-test">what to test, and what not to test</a> is a function of context. You may find yourself in a context where that's not good enough. What other options are there? </p> <h3 id="702b62450cb24cdc95f384b15d80a07c"> Synchronizing Decorator <a href="#702b62450cb24cdc95f384b15d80a07c">#</a> </h3> <p> What you <em>really</em> need to reproduce the race condition is to synchronize the database reads. If you could make sure that the Repository only returns data when enough reads have been performed, you can deterministically reproduce the problem. </p> <p> Again, start with a Decorator. This time, build into it a way to synchronize reads. </p> <p> <pre><span style="color:blue;">internal</span>&nbsp;<span style="color:blue;">sealed</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">SynchronizedReaderRepository</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IReservationsRepository</span> { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">CountdownEvent</span>&nbsp;countdownEvent&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">CountdownEvent</span>(2); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">SynchronizedReaderRepository</span>(<span style="color:#2b91af;">IReservationsRepository</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">inner</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Inner&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">inner</span>; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">IReservationsRepository</span>&nbsp;Inner&nbsp;{&nbsp;<span style="color:blue;">get</span>;&nbsp;}</pre> </p> <p> Here I've used a <a href="https://learn.microsoft.com/dotnet/api/system.threading.countdownevent">CountdownEvent</a> object to ensure that reads only progress when the countdown reaches zero. It's possible that more appropriate threading APIs exist, but this serves well as a proof of concept. </p> <p> The method you need to synchronize is <code>ReadReservations</code>, so you can leave all the other methods to delegate to <code>Inner</code>. Only <code>ReadReservations</code> is special. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Reservation</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">ReadReservations</span>( &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">int</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">restaurantId</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>, &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">DateTime</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">max</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">result</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;Inner&nbsp;.<span style="font-weight:bold;color:#74531f;">ReadReservations</span>(<span style="font-weight:bold;color:#1f377f;">restaurantId</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">min</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">max</span>); &nbsp;&nbsp;&nbsp;&nbsp;countdownEvent.<span style="font-weight:bold;color:#74531f;">Signal</span>(); &nbsp;&nbsp;&nbsp;&nbsp;countdownEvent.<span style="font-weight:bold;color:#74531f;">Wait</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">result</span>; }</pre> </p> <p> This implementation also starts by delegating to <code>Inner</code>, but before it returns the <code>result</code>, it signals the <code>countdownEvent</code> and blocks the thread by waiting on the <code>countdownEvent</code>. Only when both threads have signalled it does the counter reach zero, and the methods may proceed. </p> <p> If we assume that, while the test is running, no other calls to <code>ReadReservations</code> is made, this guarantees that both threads receive the same answer. This will make both competing threads come to the answer that they can accept the reservation. If no transaction control is in place, the system will overbook the requested time slot. </p> <h3 id="008987e40f7e4d5baeda6b245d086a43"> Testing with the synchronizing Repository <a href="#008987e40f7e4d5baeda6b245d086a43">#</a> </h3> <p> The test that uses <code>SynchronizedReaderRepository</code> is almost identical to the previous test. </p> <p> <pre>[<span style="color:#2b91af;">Fact</span>] <span style="color:blue;">public</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">NoOverbookingRace</span>() { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">date</span>&nbsp;=&nbsp;<span style="color:#2b91af;">DateTime</span>.Now.Date.<span style="font-weight:bold;color:#74531f;">AddDays</span>(1).<span style="font-weight:bold;color:#74531f;">AddHours</span>(18.5); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">using</span>&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">service</span>&nbsp;=&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">RestaurantService</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">using</span>&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">syncedService</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">service</span>.<span style="font-weight:bold;color:#74531f;">Select</span>(<span style="font-weight:bold;color:#1f377f;">repo</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">SynchronizedReaderRepository</span>(<span style="font-weight:bold;color:#1f377f;">repo</span>)); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">task1</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">syncedService</span>.<span style="font-weight:bold;color:#74531f;">PostReservation</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationDtoBuilder</span>() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithDate</span>(<span style="font-weight:bold;color:#1f377f;">date</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithQuantity</span>(10) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Build</span>()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">task2</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">syncedService</span>.<span style="font-weight:bold;color:#74531f;">PostReservation</span>(<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">ReservationDtoBuilder</span>() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithDate</span>(<span style="font-weight:bold;color:#1f377f;">date</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">WithQuantity</span>(10) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Build</span>()); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="color:#2b91af;">Task</span>.<span style="color:#74531f;">WhenAll</span>(<span style="font-weight:bold;color:#1f377f;">task1</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">task2</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Single</span>( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">actual</span>, &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>.StatusCode&nbsp;==&nbsp;<span style="color:#2b91af;">HttpStatusCode</span>.InternalServerError); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">ok</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Single</span>(<span style="font-weight:bold;color:#1f377f;">actual</span>,&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">msg</span>.IsSuccessStatusCode); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Check&nbsp;that&nbsp;the&nbsp;reservation&nbsp;was&nbsp;actually&nbsp;created:</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">resp</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">service</span>.<span style="font-weight:bold;color:#74531f;">GetReservation</span>(<span style="font-weight:bold;color:#1f377f;">ok</span>.Headers.Location); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">resp</span>.<span style="font-weight:bold;color:#74531f;">EnsureSuccessStatusCode</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">resp</span>.<span style="font-weight:bold;color:#74531f;">ParseJsonContent</span>&lt;<span style="color:#2b91af;">ReservationDto</span>&gt;(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Assert</span>.<span style="color:#74531f;">Equal</span>(10,&nbsp;<span style="font-weight:bold;color:#1f377f;">reservation</span>.Quantity); }</pre> </p> <p> Contrary to using the slow Repository, this test doesn't allow false negatives. If transaction control is missing from the System Under Test (SUT), this test fails. And it passes when transaction control is in place. </p> <h3 id="c261a239b7a44a819eed3d4526adefed"> Disadvantages <a href="#c261a239b7a44a819eed3d4526adefed">#</a> </h3> <p> That sounds great, so why not just do this, instead of using a delaying Decorator? Because, as usual, there are trade-offs involved. This kind of solution comes with some disadvantages that are worth taking into account. </p> <p> In short, this could make the test more <a href="http://xunitpatterns.com/Fragile%20Test.html">fragile</a>. As shown above, <code>SynchronizedReaderRepository</code> makes a specific assumption. It assumes that it needs to synchronize exactly two parallel readers. One problem with this is that this may be coupled to exactly one test. If you had other tests, you'd need to write a new Decorator, or generalize this one in some way. </p> <p> Another problem is that this makes the test sensitive to changes in the SUT. What if a code change introduces a new call to <code>ReadReservations</code>? If so, the <code>countdownEvent</code> may unblock the threads too soon. One such change may be that the SUT decides to also query for surrounding times slots. You might be able to make <code>SynchronizedReaderRepository</code> robust against such changes by keeping a dictionary of synchronization objects (such as the above <code>CountdownEvent</code>) per argument set, but that clearly complicates the implementation. </p> <p> And even so, it doesn't protect against identical 'double reads', even though these may be less likely to happen. </p> <p> This Decorator is also vulnerable to caching. If you have a read-through cache that wraps around <code>SynchronizedReaderRepository</code>, only the first query may get to it, which would then cause it to block forever. Perhaps, again, you could fix this with the <a href="https://learn.microsoft.com/dotnet/api/system.threading.countdownevent.wait">Wait</a> overload that takes a timeout value. </p> <p> That said, if you cache reads, the pessimistic locking that <a href="https://learn.microsoft.com/dotnet/api/system.transactions.transactionscope">TransactionScope</a> uses isn't going to work. You could, perhaps, address that concern with optimistic concurrency, but that comes with its own problems. </p> <h3 id="d7dcb5c138e1451499f5c2c2162fb416"> Conclusion <a href="#d7dcb5c138e1451499f5c2c2162fb416">#</a> </h3> <p> You can address race conditions in various ways, but synchronization has been around for a long time. Not only can you use synchronization primitives and APIs to make your code thread-safe, you can also use them to deterministically reproduce race conditions, or to test that such a bug is no longer present in the system. </p> <p> I don't want to claim that this is universally possible, but if you run into such problems, it's at least worth considering if you could take advantage of synchronization to reproduce a problem. </p> <p> Of course, the implication is that you understand what the problem is. This is often the hardest part of dealing with race conditions, and the ideas described in this article don't help with that. </p> </div> <div id="comments"> <hr> <h2 id="comments-header"> Comments </h2> <div class="comment" id="c4c5e0bd500b4d5c8408c60ff11fff96"> <div class="comment-author">Anthony Lloyd <a href="#c4c5e0bd500b4d5c8408c60ff11fff96">#</a></div> <div class="comment-content"> <p> A more general solution would be to use the parallel random testing described in the talk by John Hughes <a href="https://github.com/AnthonyLloyd/CsCheck?tab=readme-ov-file#Parallel-testing">here</a>. </p> </div> <div class="comment-date">2025-08-19 22:22 UTC</div> </div> <div class="comment" id="58d2a2a64ad94b25960cfc1cd8e64201"> <div class="comment-author"><a href="/">Mark Seemann</a> <a href="#58d2a2a64ad94b25960cfc1cd8e64201">#</a></div> <div class="comment-content"> <p> Thank you for writing. I tried watching the talk, but I don't get how to translate that idea to this example. Additionally, I currently don't have the bandwidth to read a 12-page paper. Would it be possible to sketch out how the concept translates to testing a race condition like the one shown here? </p> </div> <div class="comment-date">2025-09-07 18:20 UTC</div> </div> <div class="comment" id="500b4d5c84d94b25960cfc1cd8e64201"> <div class="comment-author">Anthony Lloyd <a href="#500b4d5c84d94b25960cfc1cd8e64201">#</a></div> <div class="comment-content"> <p> You can think of it as a normal property-based test (in fact CsCheck builds on the existing random testing functions) with a generated initial state set of operations plus a small set of operations to be run in parallel (some PostReservation calls). The property to test is that this parallel run is linearizable which means we can find at least one sequential order of the parallel operations that gives the same result (reservation.Quantity) as the parallel run. This does require some housekeeping to get all the possible permutations correct as you know some ran on the same thread in a certain order which reduces the number to test. We get all the goodies of shrinking here (CsCheck has an advantage as shrinking is random) which is why John was able to help solve very hard concurrency issues for companies. </p> <pre><code style="background-color: #eee;border: 1px solid #999;display:block;padding:5px;"> public class ReservationTests(Xunit.Abstractions.ITestOutputHelper output) { [Fact] public void ReservationSystem_Parallel_Test() { Check.SampleParallel( // initial state Gen.Const(() => new ReservationSystem()), // parallel operations Gen.Int[1, 10].Operation<ReservationSystem>((rs, q) => rs.PostReservation(new ReservationDtoBuilder().WithQuantity(q))), // equality check parallel vs sequential equal: (rs1, rs2) => rs1.AllBookings().Equals(rs2.AllBookings()), // string representation of the bookings state for when the test fails print: rs => rs.AllBookings().ToTableString(), // display output in test results writeLine: output.WriteLine ); } } </code></pre> </div> <div class="comment-date">2025-09-10 7:26 UTC</div> </div> </div> <hr> This blog is totally free, but if you like it, please consider <a href="https://blog.ploeh.dk/support">supporting it</a>. Mark Seemann https://blog.ploeh.dk/2025/08/04/testing-races-with-a-synchronizing-decorator