ploeh blog https://blog.ploeh.dk danish software design en-us Mark Seemann Mon, 15 Sep 2025 18:46:06 UTC Mon, 15 Sep 2025 18:46:06 UTC 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 Song recommendations with F# agents https://blog.ploeh.dk/2025/07/28/song-recommendations-with-f-agents/ Mon, 28 Jul 2025 08:09:00 UTC <div id="post"> <p> <em>MailboxProcessors as small Recawr Sandwiches.</em> </p> <p> This article is part of a series named <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">Alternative ways to design with functional programming</a>. As the title implies, over a multitude of articles, I present various alternatives for applying functional programming to a particular problem. When I present the <a href="/2020/03/02/impureim-sandwich">Impureim Sandwich</a> design pattern, the most common reaction is: <em>What if you need to make additional, impure reads in the middle of an algorithm?</em> </p> <p> This article series looks at alternatives when this (in my experience rare) requirement seems inescapable. A <a href="/2025/07/14/song-recommendations-with-pipes-and-filters">previous article</a> outlined a general alternative: Use some kind of pipes-and-filters architecture to turn an undisciplined <a href="https://martinfowler.com/eaaCatalog/transactionScript.html">Transaction Script</a> into a composition of 'filters', where each filter is a self-contained <a href="/2025/01/13/recawr-sandwich">Recawr Sandwich</a>. </p> <p> Depending on the specific technology choices you make, you may encounter various terminology related to this kind of architecture. Filters may also be called <em>actors</em>, <em>message handlers</em>, or, as is the case in this article, <em>agents</em>. For a consistent pattern language, see <a href="/ref/eip">Enterprise Integration Patterns</a>. </p> <p> The code shown here is taken from the <em>fsharp-agents</em> branch of the example code Git repository. </p> <h3 id="5950d36c50c5467ba893b1b80c2b5034"> Async instead of Task <a href="#5950d36c50c5467ba893b1b80c2b5034">#</a> </h3> <p> The <a href="https://fsharp.org/">F#</a> base library comes with a class called <a href="https://fsharp.github.io/fsharp-core-docs/reference/fsharp-control-fsharpmailboxprocessor-1.html">MailboxProcessor</a>, often called an <em>agent</em>. It's an in-memory message handler that can run in the background of other tasks, pulling messages off an internal queue one at a time. </p> <p> It's been around for such a long time that its API is based on <a href="https://fsharp.github.io/fsharp-core-docs/reference/fsharp-control-fsharpasync-1.html">Async&lt;T&gt;</a>, which precedes the now-ubiquitous <a href="https://learn.microsoft.com/dotnet/api/system.threading.tasks.task-1">Task&lt;TResult&gt;</a>. While conversions exist, I thought it'd make the example code simpler if I first redefined the <code>SongService</code> interface to return <code>Async</code>-based results. </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;">Async</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;">Async</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&gt;</pre> </p> <p> Keep in mind that, despite lack of the <a href="/2015/08/03/idiomatic-or-idiosyncratic">idiomatic</a> <code>I</code> prefix, this is an interface, not an abstract class. (It would have had to have the <code>[&lt;AbstractClass&gt;]</code> attribute to be an abstract class.) </p> <p> This is minor change that only affected a few lines of code where I had to change from <a href="https://learn.microsoft.com/dotnet/fsharp/language-reference/task-expressions">task expressions</a> to <a href="https://learn.microsoft.com/dotnet/fsharp/language-reference/async-expressions">async expressions</a>. </p> <h3 id="49e02be04bbc453db9c6a2c1df8a142e"> Gather own scrobbles <a href="#49e02be04bbc453db9c6a2c1df8a142e">#</a> </h3> <p> As was also the case in the <a href="/2025/07/21/song-recommendations-with-c-reactive-extensions">previous article</a>, we may as well start at the beginning of the algorithm. Given a user name, we'd like to find that user's top scrobbles. Once we've found them, we'd like to post them to an agent. Since F# agents are message-based, we must define an appropriate message type. </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:#2b91af;">ScrobbleMessage</span>&nbsp;=&nbsp;<span style="color:#2b91af;">Scrobble</span>&nbsp;<span style="color:blue;">of</span>&nbsp;<span style="color:#2b91af;">Scrobble</span>&nbsp;|&nbsp;<span style="color:#2b91af;">EndOfStream</span></pre> </p> <p> If you recall the <a href="/2025/07/21/song-recommendations-with-c-reactive-extensions">previous article</a>, with <a href="https://github.com/dotnet/reactive">Reactive Extensions for .NET</a>, you can use the <a href="https://learn.microsoft.com/dotnet/api/system.iobserver-1.oncompleted">OnCompleted</a> method to signal the end of a stream. Such a method isn't available for an F# agent, because an agent is a consumer of messages, rather than a stream of values. For that reason, a <code>ScrobbleMessage</code> may either be a <code>Scrobble</code> or an <code>EndOfStream</code>. </p> <p> With the message definition in place, you can define the first step of the algorithm like this: </p> <p> <pre><span style="color:green;">//&nbsp;string&nbsp;-&gt;&nbsp;SongService&nbsp;-&gt;&nbsp;MailboxProcessor&lt;ScrobbleMessage&gt;&nbsp;-&gt;&nbsp;Async&lt;unit&gt;</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:#74531f;">gatherOwnScrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;:&nbsp;<span style="color:#2b91af;">SongService</span>)&nbsp;(<span style="color:#1f377f;">channel</span>&nbsp;:&nbsp;<span style="color:#2b91af;">MailboxProcessor</span>&lt;_&gt;)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">async</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Impure</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>.<span style="font-weight:bold;color:#74531f;">GetTopScrobblesAsync</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Pure</span> &nbsp;&nbsp;&nbsp;&nbsp;&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;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</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;">sortByDescending</span>&nbsp;_.ScrobbleCount &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;100 &nbsp;&nbsp;&nbsp;&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:#2b91af;">Scrobble</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Impure</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">iter</span>&nbsp;<span style="color:#1f377f;">channel</span>.<span style="font-weight:bold;color:#74531f;">Post</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobblesSnapshot</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">channel</span>.<span style="font-weight:bold;color:#74531f;">Post</span>&nbsp;<span style="color:#2b91af;">EndOfStream</span>&nbsp;}</pre> </p> <p> The <code>gatherOwnScrobbles</code> action isn't itself an agent. Rather, it takes one as input, to which it posts messages. Notice that the operation returns an <code>Async&lt;unit&gt;</code> value. In other words, it doesn't really return anything, but rather posts messages to the injected <code>channel</code>. </p> <p> Like in the <a href="/2025/07/21/song-recommendations-with-c-reactive-extensions">previous article</a>, once all scrobbles are posted, <code>gatherOwnScrobbles</code> indicates the end of the stream by posting a final <code>EndOfStream</code> message. This still works in this implementation, since F# agents (as far as I've been able ascertain) handle messages in order. If you're using a distributed messaging framework based on a message bus, and possibly handlers running on multiple machines, you can't always assume this to be the case. As I wrote in <a href="/2025/07/14/song-recommendations-with-pipes-and-filters">Song recommendations with pipes and filters</a>, you'll need to extrapolate from both this and the previous article in such cases. This is where a pattern language as presented in <a href="/ref/eip">Enterprise Integration Patterns</a> may come in handy. Perhaps you need a <a href="https://www.enterpriseintegrationpatterns.com/patterns/messaging/MessageSequence.html">Message Sequence</a> in this case. </p> <p> Be that as it may, the <code>gatherOwnScrobbles</code> action is a small <a href="/2025/01/13/recawr-sandwich">Recawr Sandwich</a> with clearly delineated steps. </p> <p> The natural next step is to implement a MailboxProcessor that can receive those scrobble messages. </p> <h3 id="4ec7b8d1fd6a4158ac86dc83621e8082"> Gather other listeners <a href="#4ec7b8d1fd6a4158ac86dc83621e8082">#</a> </h3> <p> To handle the messages posted by <code>gatherOwnScrobbles</code> we'll create an agent. This one, however, isn't going to complete the algorithm. Rather, it's going to publish even more messages that yet another agent may deal with. For that, we need another message type: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:#2b91af;">UserMessage</span>&nbsp;=&nbsp;<span style="color:#2b91af;">User</span>&nbsp;<span style="color:blue;">of</span>&nbsp;<span style="color:#2b91af;">User</span>&nbsp;|&nbsp;<span style="color:#2b91af;">EndOfStream</span></pre> </p> <p> We see what starts to look like a pattern: A 'payload' case, and a case to indicate that no more message will be coming. </p> <p> The following action creates an agent that handles scrobble messages and publishes user messages: </p> <p> <pre><span style="color:green;">//&nbsp;SongService&nbsp;-&gt;&nbsp;MailboxProcessor&lt;UserMessage&gt;&nbsp;-&gt;&nbsp;MailboxProcessor&lt;ScrobbleMessage&gt;</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:#74531f;">gatherOtherListeners</span> &nbsp;&nbsp;&nbsp;&nbsp;(<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;:&nbsp;<span style="color:#2b91af;">SongService</span>)&nbsp;(<span style="color:#1f377f;">channel</span>&nbsp;:&nbsp;<span style="color:#2b91af;">MailboxProcessor</span>&lt;_&gt;)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">MailboxProcessor</span>.<span style="font-weight:bold;color:#74531f;">Start</span>&nbsp;&lt;|&nbsp;<span style="color:blue;">fun</span>&nbsp;<span style="color:#1f377f;">inbox</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="color:blue;">rec</span>&nbsp;<span style="color:#74531f;">loop</span>&nbsp;()&nbsp;=&nbsp;<span style="color:blue;">async</span>&nbsp;{ &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;">message</span>&nbsp;=&nbsp;<span style="color:#1f377f;">inbox</span>.<span style="font-weight:bold;color:#74531f;">Receive</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Scrobble</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobble</span>&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&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;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let!</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListeners</span>&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:#1f377f;">songService</span>.<span style="font-weight:bold;color:#74531f;">GetTopListenersAsync</span>&nbsp;<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="color:green;">//&nbsp;Pure</span> &nbsp;&nbsp;&nbsp;&nbsp;&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;">otherListenersSnapshot</span>&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:#1f377f;">otherListeners</span> &nbsp;&nbsp;&nbsp;&nbsp;&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;">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;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">sortByDescending</span>&nbsp;_.TotalScrobbleCount &nbsp;&nbsp;&nbsp;&nbsp;&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;20 &nbsp;&nbsp;&nbsp;&nbsp;&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;">map</span>&nbsp;<span style="color:#2b91af;">User</span> &nbsp;&nbsp;&nbsp;&nbsp;&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;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">Seq</span>.<span style="color:#74531f;">iter</span>&nbsp;<span style="color:#1f377f;">channel</span>.<span style="font-weight:bold;color:#74531f;">Post</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListenersSnapshot</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">loop</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">ScrobbleMessage</span>.<span style="color:#2b91af;">EndOfStream</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:#1f377f;">channel</span>.<span style="font-weight:bold;color:#74531f;">Post</span>&nbsp;<span style="color:#2b91af;">EndOfStream</span>&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#74531f;">loop</span>&nbsp;()</pre> </p> <p> If you can look past some of the infrastructure required to initialize and implement the agent (<code>MailboxProcessor</code>), the main message handler is, once again, a small Recawr Sandwich. The other case in the <code>match</code> expression maps one <code>EndOfStream</code> case to another <code>EndOfStream</code> case. Notice that this case does <em>not</em> recursively call <code>loop</code>. This means that once the agent receives an <code>EndOfStream</code> message, it stops all further message processing. </p> <p> You may have noticed that the <code>loop</code> starts with an 'unmarked' impure step to receive a message. Once a message arrives, it matches on the message. You may argue that there seems to be more than one impure step in the sandwich, but as I've previously outlined, <a href="/2023/10/09/whats-a-sandwich">sometimes a sandwich has more that three layers</a>. </p> <p> I could have compressed the code that receives and dispatches the message to a single line of code: </p> <p> <pre><span style="color:blue;">match!</span>&nbsp;<span style="color:#1f377f;">input</span>.<span style="font-weight:bold;color:#74531f;">Receive</span>&nbsp;()&nbsp;<span style="color:blue;">with</span></pre> </p> <p> I felt, however, that for readers who aren't familiar with F# agents, it would help to instead make things more explicit by having a named <code>message</code> value in the code. It's an example of using an explicit variable for readability purposes. </p> <p> A third agent, created by <code>gatherOtherScrobbles</code>, handles the messages published by <code>gatherOtherListeners</code> by publishing even more song messages. We'll get back to that message type in a moment, but the agent looks similar to the one shown above. You may consult the Git repository if you're curious about the details. </p> <h3 id="a2b09f2657e2497f955927fa13adc438"> Collecting the recommendations <a href="#a2b09f2657e2497f955927fa13adc438">#</a> </h3> <p> The final agent is a bit different, because it needs to do two things: </p> <ul> <li>Handle song messages</li> <li>Return the recommendations once they're ready</li> </ul> <p> Because of that extra responsibility, the message type isn't a two-way discriminated union. Instead, it has a third case that we haven't yet seen. </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:#2b91af;">SongMessage</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Song</span>&nbsp;<span style="color:blue;">of</span>&nbsp;<span style="color:#2b91af;">Song</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">EndOfStream</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Fetch</span>&nbsp;<span style="color:blue;">of</span>&nbsp;<span style="color:#2b91af;">AsyncReplyChannel</span>&lt;<span style="color:#2b91af;">Option</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Song</span>&gt;&gt;&gt;</pre> </p> <p> The <code>Song</code> and <code>EndOfStream</code> cases are similar to what we've already seen. These are the two messages that the <code>gatherOtherScrobbles</code> agent publishes. </p> <p> What does the third case, <code>Fetch</code>, do? It looks odd, with its <code>AsyncReplyChannel</code> payload. In a moment, you'll see how it's used, but essentially, this is how F# agents support the <a href="https://www.enterpriseintegrationpatterns.com/patterns/messaging/RequestReply.html">Request-Reply</a> pattern. Let's see it all in action: </p> <p> <pre><span style="color:green;">//&nbsp;unit&nbsp;-&gt;&nbsp;MailboxProcessor&lt;SongMessage&gt;</span> <span style="color:blue;">let</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:#74531f;">collectRecommendations</span>&nbsp;()&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#2b91af;">MailboxProcessor</span>.<span style="font-weight:bold;color:#74531f;">Start</span>&nbsp;&lt;|&nbsp;<span style="color:blue;">fun</span>&nbsp;<span style="color:#1f377f;">input</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="color:blue;">rec</span>&nbsp;<span style="color:#74531f;">loop</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendations</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">isDone</span>&nbsp;=&nbsp;<span style="color:blue;">async</span>&nbsp;{ &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;">message</span>&nbsp;=&nbsp;<span style="color:#1f377f;">input</span>.<span style="font-weight:bold;color:#74531f;">Receive</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">message</span>&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Song</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">song</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">loop</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">song</span>&nbsp;<span style="color:#2b91af;">::</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendations</span>)&nbsp;<span style="color:blue;">false</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">SongMessage</span>.<span style="color:#2b91af;">EndOfStream</span>&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&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;">recommendations</span>&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:#1f377f;">recommendations</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">List</span>.<span style="color:#74531f;">sortByDescending</span>&nbsp;_.Rating &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#2b91af;">List</span>.<span style="color:#74531f;">truncate</span>&nbsp;200 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">loop</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendations</span>&nbsp;<span style="color:blue;">true</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Fetch</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">replyChannel</span>&nbsp;<span style="color:blue;">-&gt;</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">if</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">isDone</span>&nbsp;<span style="color:blue;">then</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:#1f377f;">replyChannel</span>.<span style="font-weight:bold;color:#74531f;">Reply</span>&nbsp;(<span style="color:#2b91af;">Some</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendations</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">else</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:#1f377f;">replyChannel</span>.<span style="font-weight:bold;color:#74531f;">Reply</span>&nbsp;<span style="color:#2b91af;">None</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">loop</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">recommendations</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">isDone</span>&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#74531f;">loop</span>&nbsp;[]&nbsp;<span style="color:blue;">false</span></pre> </p> <p> The purpose of this agent is to collect all the songs that the previous agent recommended. Once it receives an <code>EndOfStream</code> message, it sorts the songs and keeps only the top 200. </p> <p> Note that the recursive <code>loop</code> action takes two parameters, <code>recommendations</code> and <code>isDone</code>. The loops starts with an empty song list and the flag set to <code>false</code>. When a new <code>Song</code> arrives, the loop prepends the song onto the song list and recurses. Notice that in that case, the flag remains <code>false</code>. </p> <p> Only when an <code>EndOfStream</code> message arrives does the agent calculate the final recommendations. Afterwards, it recursively calls <code>loop</code> with the flag raised (set to <code>true</code>). Notice, however, that the agent doesn't stop handling messages, like the other agents do when encountering an <code>EndOfStream</code> message. </p> <p> At any time during execution, a <code>Fetch</code> message may arrive. This is a request to return the recommendations, if they're ready. In that case, the <code>recommendations</code> are wrapped in a <code>Some</code> case and returned. If the recommendations are not yet ready, <code>None</code> is returned instead. </p> <p> This enables the overall, blocking method to poll for the recommendations until they are ready. You'll see how this works in a moment. </p> <h3 id="729573092e814326a356423e87078f5e"> Polling for results <a href="#729573092e814326a356423e87078f5e">#</a> </h3> <p> The <code>MailboxProcessor</code> class defines a <code>PostAndAsyncReply</code> method that does, indeed, fit the <code>Fetch</code> case of the above <code>SongMessage</code> type. This enables us to implement a polling mechanism like this: </p> <p> <pre><span style="color:blue;">let</span>&nbsp;<span style="color:blue;">rec</span>&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:#74531f;">poll</span>&nbsp;(<span style="color:#1f377f;">agent</span>&nbsp;:&nbsp;<span style="color:#2b91af;">MailboxProcessor</span>&lt;_&gt;)&nbsp;=&nbsp;<span style="color:blue;">task</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">match!</span>&nbsp;<span style="color:#1f377f;">agent</span>.<span style="font-weight:bold;color:#74531f;">PostAndAsyncReply</span>&nbsp;<span style="color:#2b91af;">Fetch</span>&nbsp;<span style="color:blue;">with</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">Some</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">result</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">result</span> &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;<span style="color:#2b91af;">None</span>&nbsp;<span style="color:blue;">-&gt;</span>&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">poll</span>&nbsp;<span style="color:#1f377f;">agent</span>&nbsp;}</pre> </p> <p> This recursive action uses <code>PostAndAsyncReply</code> to keep polling its agent until it receives a useful reply. Since this code is mostly meant for illustration purposes, I've allowed myself a few shortcuts. </p> <p> First, this effectively implements a busy loop. Whenever it receives a <code>None</code> reply, it immediately recurses to try again. A more reasonable implementation may put a small delay there, but I think that finding the optimal delay time may be a matter of experimentation. After all, if you're concerned with performance, <a href="https://ericlippert.com/2012/12/17/performance-rant/">race your horses</a>. Given that this is demo code, I don't have any real horses to race, so I'm not going to try. From observation, however, it doesn't seem as though the tests, at least, run any slower despite the tight loop. </p> <p> Secondly, the <code>poll</code> loop keeps going until it receives a useful response. What if that never happens? A more robust implementation should implement some kind of timeout or ceiling that enables it to give up if it's been running for too long. </p> <p> Apart from all that, how does the <code>poll</code> action even type-check? On a <code><span style="color:#2b91af;">MailboxProcessor</span>&lt;<span style="color:#2b91af;">'Msg</span>&gt;</code> object, the <code>PostAndAsyncReply</code> method has this type: </p> <p> <pre>(<span style="color:#2b91af;">AsyncReplyChannel</span>&lt;<span style="color:#2b91af;">'Reply</span>&gt; -&gt; <span style="color:#2b91af;">'Msg</span>) <span style="color:blue;">-&gt;</span> <span style="color:#2b91af;">Async</span>&lt;<span style="color:#2b91af;">'Reply</span>&gt;</pre> </p> <p> ignoring an optional timeout parameter. </p> <p> The above <code>Fetch</code> case constructor fits the type of <code>PostAndAsyncReply</code>, since it has the type </p> <p> <pre><span style="color:#2b91af;">AsyncReplyChannel</span>&lt;<span style="color:#2b91af;">Option</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Song</span>&gt;&gt;&gt; <span style="color:blue;">-&gt;</span> <span style="color:#2b91af;">SongMessage</span></pre> </p> <p> This means that we can infer <code>'Reply</code> to be <code><span style="color:#2b91af;">Option</span>&lt;<span style="color:#2b91af;">IReadOnlyCollection</span>&lt;<span style="color:#2b91af;">Song</span>&gt;&gt;</code>. It also means that <code>'Msg</code> must be <code>SongMessage</code>, and again we can infer that the <code>agent</code> parameter has the type <code><span style="color:#2b91af;">MailboxProcessor</span>&lt;<span style="color:#2b91af;">SongMessage</span>&gt;</code>. </p> <h3 id="d92982c8ced649ceaf2b8c42c6092f4b"> Composition <a href="#d92982c8ced649ceaf2b8c42c6092f4b">#</a> </h3> <p> With all components ready, we can now compose them as a blocking method. Notice that, in the following, the <code>GetRecommendationsAsync</code> method hasn't changed type or observable behaviour. The change from <code>Task</code> to <code>Async</code> (described above) required some trivial changes to <code>FakeSongService</code>, but apart from that, I had to change no test code to make this refactoring. </p> <p> As a first attempt, we may compose the agents using the idiomatic left-to-right pipeline operator, like this: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">RecommendationsProvider</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;:&nbsp;<span style="color:#2b91af;">SongService</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">GetRecommendationsAsync</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;=&nbsp;<span style="color:#74531f;">collectRecommendations</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">task</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do!</span>&nbsp;<span style="color:#1f377f;">collect</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">gatherOtherScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">gatherOtherListeners</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;|&gt;&nbsp;<span style="color:#74531f;">gatherOwnScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">poll</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;}</pre> </p> <p> First, the <code>task</code> expression starts all the agents, and then proceeds to <code>poll</code> the <code>collect</code> agent until it arrives at a result. </p> <p> This passes all tests, but has at least two problems. One problem is that the composition seems backwards. It looks as though the process starts with <code>collect</code>, then proceeds to <code>gatherOtherScrobbles</code>, and so on. In reality, it's the other way around. You should really understand the composition as being defined 'bottom-up', or right-to-left, if we put it on a single line. We'll return to the other problem in a moment, but let's first see if we can do something about this one. </p> <p> My first attempt to fix this problem was to try to use the reverse pipeline operator <code>&lt;|</code>, but due to precedence rules, it didn't work without parentheses. And if we need parentheses anyway, there's no reason to use the reverse pipeline operator. </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">RecommendationsProvider</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;:&nbsp;<span style="color:#2b91af;">SongService</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">GetRecommendationsAsync</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;=&nbsp;<span style="color:#74531f;">collectRecommendations</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">task</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do!</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#74531f;">gatherOwnScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#74531f;">gatherOtherListeners</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#74531f;">gatherOtherScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;( &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#1f377f;">collect</span>))) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">poll</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;}</pre> </p> <p> This composition uses a slightly unorthodox code formatting style. Since <code>collect</code> is really nested inside of <code>gatherOtherScrobbles</code>, it should really have been indented to the right of it. Likewise, <code>gatherOtherScrobbles</code> is nested inside of <code>gatherOtherListeners</code>, and so on. A more idiomatic formatting of the code might be something like this: </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">RecommendationsProvider</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;:&nbsp;<span style="color:#2b91af;">SongService</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">GetRecommendationsAsync</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">let</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;=&nbsp;<span style="color:#74531f;">collectRecommendations</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">task</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do!</span>&nbsp;<span style="color:#74531f;">gatherOwnScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&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;">gatherOtherListeners</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</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;&nbsp;<span style="color:#74531f;">gatherOtherScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;<span style="color:#1f377f;">collect</span>)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">poll</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;}</pre> </p> <p> This, however, blurs the semantics of the composition in favour of the mechanics of it. I don't consider it an improvement. </p> <p> All of this, however, turns out to be moot because of the other problem. The <code>MailboxProcessor</code> class implements <a href="https://learn.microsoft.com/dotnet/api/system.idisposable">IDisposable</a>, and to be good citizens, we ought to dispose of the objects once we're done with them. This is possible, but we're now back to the backwards order of composition. </p> <p> <pre><span style="color:blue;">type</span>&nbsp;<span style="color:#2b91af;">RecommendationsProvider</span>&nbsp;(<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;:&nbsp;<span style="color:#2b91af;">SongService</span>)&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">member</span>&nbsp;_.<span style="font-weight:bold;color:#74531f;">GetRecommendationsAsync</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;=&nbsp;<span style="color:blue;">task</span>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">use</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;=&nbsp;<span style="color:#74531f;">collectRecommendations</span>&nbsp;() &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">use</span>&nbsp;<span style="color:#1f377f;">otherScrobbles</span>&nbsp;=&nbsp;<span style="color:#74531f;">gatherOtherScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;<span style="color:#1f377f;">collect</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">use</span>&nbsp;<span style="color:#1f377f;">otherListeners</span>&nbsp;=&nbsp;<span style="color:#74531f;">gatherOtherListeners</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;<span style="color:#1f377f;">otherScrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">do!</span>&nbsp;<span style="color:#74531f;">gatherOwnScrobbles</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>&nbsp;<span style="color:#1f377f;">otherListeners</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">return!</span>&nbsp;<span style="color:#74531f;">poll</span>&nbsp;<span style="color:#1f377f;">collect</span>&nbsp;}</pre> </p> <p> This may not be an entirely unsolvable problem, but this is where I'm no longer interested in pursuing this line of inquiry much further. Instead of those 'factory actions' that create and return agents, you could refactor each agent into a separate object that, when disposed of, also disposes of any inner agents it may contain. If so, you could again compose these objects as shown above, and only dispose of the outer object. </p> <h3 id="78e407aecd044d68bd16a8ae207ffa4c"> Evaluation <a href="#78e407aecd044d68bd16a8ae207ffa4c">#</a> </h3> <p> These various attempts to make the agents compose nicely, in a way that also works as self-documenting code, reveals that F# agents aren't as composable as <a href="https://reactivex.io/">ReactiveX</a>. To be fair, the <code>MailboxProcessor</code> class also predates Reactive Extensions, so we shouldn't blame it for not being as good as a more recent technology. </p> <p> One major problem is that agents don't compose naturally, <a href="/2025/03/03/reactive-monad">like IObservable&lt;T&gt; does</a>. I briefly considered whether it'd be possible to make <code><span style="color:#2b91af;">MailboxProcessor</span>&lt;'Msg&gt;</code> a <a href="/2022/03/28/monads">monad</a>, but armed with the knowledge of variance imparted by <a href="https://thinkingwithtypes.com/">Thinking with Types</a>, I quickly realized that the type is invariant. This is easily seen because one method, <code>Post</code>, is contravariant in <code>'Msg</code>, whereas most other methods are covariant. I'm using deliberately vague language, since there's no reason to calculate the kind of variance for all methods when you've already found two incompatible members. </p> <p> Another fly in the ointment is that the <code>collectRecommendations</code> action looks messy. As presented, it's not a pretty Impureim Sandwich. Most of the 'middle' message handling could be extracted to a pure function, were it not for the <code>Fetch</code> case. Calling <code>replyChannel.Reply</code> has a side effect, and while I know of refactorings that move side effects around, I'd need access to the <code>replyChannel</code> in order to impart that effect from somewhere else. This would still be possible if I returned an action to be invoked, but I don't see much point in that. In general, that request-reply API doesn't strike me as particularly functional. </p> <p> Based on all that griping, you may be wondering whether this kind of architecture is worth the trouble. Keep in mind, though, that some of the issues I just outlined is the result of the particular <code>MailboxProcessor</code> API. It's not a given that if you use some other message-based framework, you'll run into the same issues. </p> <p> You may also find the notion of posting messages to a chain of agents, only to poll one of them for the result, as carrying coals to Newcastle. Keep in mind, however, that the code presented here refactors a blocking method call that <a href="https://x.com/Tyrrrz/status/1493369905869213700">apparently takes about ten minutes to run to completion</a>. It's possible that I read too much into the situation, but I'm guessing that the 'real' code base that was the inspiration for the example code, doesn't actually block for ten minutes in order to return a result. Rather, I still speculate, it's probably a background batch job that produces persisted views; e.g. as JSON files. If so, you'd really just want to trigger a new batch job and let it run to completion in the background. In such a scenario, I'd find an asynchronous, message-based architecture suitable for the job. In that case, you'd need no polling loop. Rather, you serve a persisted view whenever anyone asks for it, and once in a while, that persisted view has been updated by the background process. </p> <h3 id="7c4b1d25b43c4fea9a969eefe7e04fcc"> Conclusion <a href="#7c4b1d25b43c4fea9a969eefe7e04fcc">#</a> </h3> <p> Compared to the <a href="/2025/07/21/song-recommendations-with-c-reactive-extensions">previous article</a>, which used Reactive Extensions to compose self-contained Recawr Sandwiches, using F# agents is a move towards a more standard kind of message-based architecture. Hopefully, it does a good enough job of illustrating how you can refactor an impure action into a composition of individual sandwiches, even if some of the details here are particular to F# agents. </p> <p> It's not necessarily always the best solution to the underlying problem being addressed in this article series, but it seems appropriate if the problem of large data sets is combined with long running time. If you can convert the overall problem to a fire-and-forget architecture, a message-based system may be suitable. </p> <p> If, on the other hand, you need to maintain the blocking nature of the operation, you may need to reach for the big, universal <a href="https://en.wikipedia.org/wiki/Law_of_the_instrument">hammer</a>. </p> <p> <strong>Next:</strong> <a href="/2025/08/11/song-recommendations-with-free-monads">Song recommendations with 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/07/28/song-recommendations-with-f-agents Song recommendations with C# Reactive Extensions https://blog.ploeh.dk/2025/07/21/song-recommendations-with-c-reactive-extensions/ Mon, 21 Jul 2025 13:54:00 UTC <div id="post"> <p> <em>Observables as small Recawr Sandwiches.</em> </p> <p> This article is part of a series titled <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">Alternative ways to design with functional programming</a>. In the <a href="/2025/07/14/song-recommendations-with-pipes-and-filters">previous article in the series</a>, you read some general reflections on a pipes-and-filters architecture. This article gives an example in C#. </p> <p> The code shown here is from the <em>rx</em> branch of the example code Git repository. As the name implies, it uses <a href="https://reactivex.io/">ReactiveX</a>, also known as <a href="https://github.com/dotnet/reactive">Reactive Extensions for .NET</a>. </p> <p> To be honest, when refactoring an algorithm that's originally based on sequences of data, there's nothing particularly <em>reactive</em> going on here. You may, therefore, argue that it's a poor fit for this kind of architecture. Be that as it may, keep in mind that the example code <a href="https://x.com/Tyrrrz/status/1493369905869213700">in reality runs for about ten minutes</a>, so moving towards an architecture that supports progress reporting or cancellation may not be entirely inappropriate. </p> <p> The advantage of using Reactive Extensions for this particular example is that, compared to full message-bus-based frameworks, it offers a lightweight <a href="/2024/05/13/gratification">developer experience</a>, which enables us to focus on the essentials of the architecture. </p> <h3 id="e6e596b582524953aeab05c97f898d83"> Handle own scrobbles <a href="#e6e596b582524953aeab05c97f898d83">#</a> </h3> <p> We'll start with the part of the process that finds the user's own top scrobbles. Please consult with <a href="https://tyrrrz.me/">Oleksii Holub</a>'s <a href="https://tyrrrz.me/blog/pure-impure-segregation-principle#interleaved-impurities">original article</a>, or my article on <a href="/2025/04/10/characterising-song-recommendations">characterizing the implementation</a>, if you need a refresher. </p> <p> When using Reactive Extensions, should we model this part as <a href="https://learn.microsoft.com/dotnet/api/system.iobservable-1">IObservable&lt;T&gt;</a> or <a href="https://learn.microsoft.com/dotnet/api/system.iobserver-1">IObserver&lt;T&gt;</a>? </p> <p> Once you recall that <code>IObservable&lt;T&gt;</code>, <a href="/2025/03/03/reactive-monad">being a monad</a>, is eminently composable, the choice is clear. The <code>IObserver&lt;T&gt;</code> interface, on the other hand, gives rise to a <a href="/2021/09/02/contravariant-functors">contravariant functor</a>, but since that abstraction has weaker language support, we should go with the <a href="/2022/03/28/monads">monad</a>. </p> <p> We can start by declaring the type and its initializer: </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:blue;">sealed</span>&nbsp;<span style="color:blue;">class</span>&nbsp;<span style="color:#2b91af;">HandleOwnScrobblesObservable</span>&nbsp;:&nbsp;<span style="color:#2b91af;">IObservable</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt; { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:blue;">string</span>&nbsp;userName; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">private</span>&nbsp;<span style="color:blue;">readonly</span>&nbsp;<span style="color:#2b91af;">SongService</span>&nbsp;_songService; &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">HandleOwnScrobblesObservable</span>(<span style="color:blue;">string</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;<span style="color:#2b91af;">SongService</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">this</span>.userName&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">userName</span>; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;_songService&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">songService</span>; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Implementation&nbsp;goes&nbsp;here...</span></pre> </p> <p> Given a <code>userName</code> we want to produce a (finite) stream of scrobbles, so we declare that the class implements <code><span style="color:#2b91af;">IObservable</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;</code>. An instance of this class is also going to need the <code>songService</code>, so that its implementation can query the out-of-process system that holds the data. </p> <p> What's that, you say? Why does <code>_songService</code> have a leading underscore, while the <code>userName</code> field does not? Because Oleksii Golub used that naming convention for that service, but <a href="/2021/05/17/against-consistency">I don't feel obliged to stay consistent</a> with that. </p> <p> Given that we already have working code, the implementation is relatively straightforward. </p> <p> <pre><span style="color:blue;">public</span>&nbsp;<span style="color:#2b91af;">IDisposable</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Subscribe</span>(<span style="color:#2b91af;">IObserver</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">observer</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="color:#2b91af;">Observable</span>.<span style="color:#74531f;">Create</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;(<span style="font-weight:bold;color:#74531f;">Produce</span>).<span style="font-weight:bold;color:#74531f;">Subscribe</span>(<span style="font-weight:bold;color:#1f377f;">observer</span>); } <span style="color:blue;">private</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Produce</span>(<span style="color:#2b91af;">IObserver</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Impure</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;_songService.<span style="font-weight:bold;color:#74531f;">GetTopScrobblesAsync</span>(userName); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Pure</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobblesSnapshot</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobbles</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">OrderByDescending</span>(<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.ScrobbleCount) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Take</span>(100); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Impure</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">foreach</span>&nbsp;(<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobble</span>&nbsp;<span style="font-weight:bold;color:#8f08c4;">in</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">scrobblesSnapshot</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>.<span style="font-weight:bold;color:#74531f;">OnNext</span>(<span style="font-weight:bold;color:#1f377f;">scrobble</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>.<span style="font-weight:bold;color:#74531f;">OnCompleted</span>(); }</pre> </p> <p> If you are unused to Reactive Extensions, the hardest part may be figuring out how to implement <code>Subscribe</code> without getting bogged down with having to write too much of the implementation. Rx is, after all, a reusable library, so it should come with some building blocks for that, and it does. </p> <p> It seems that the simplest way to implement <code>Subscribe</code> is to delegate to <code>Observable.Create</code>, which takes an expression as input. You can write the implementation inline as a lambda expression, but here I've used a <code>private</code> helper method to slightly decouple the implementation from the library requirements. </p> <p> The first impure step is the same as we've already seen in the 'reference implementation', and the pure step should be familiar too. In the final impure step, the <code>Produce</code> method publishes the scrobbles to any subscribers that may be listening. </p> <p> This is the step where you'll need to extrapolate if you want to implement this kind of architecture on another framework than Reactive Extensions. If you're using a distributed message-based framework, you may have a message bus on which you publish messages, instead of <code>obs</code>. So <code>obs.OnNext</code> may, instead, be <code>bus.Publish</code>, or something to that effect. You may also need to package each scrobble in an explicit message object, and add correlation identifier and such. </p> <p> In many message-based frameworks (<a href="https://particular.net/nservicebus">NServiceBus</a>, for example), you're expected to implement some kind of message handler where messages arrive at a <code>Handle</code> method, typically on a stateless, long-lived object. This enables you to set up robust, distributed systems, but also comes with some overhead that requires you to coordinate or correlate messages. </p> <p> In this code example, <code>userName</code> is just a class field, and once the object is done producing messages, it signals so with <code>obs.OnCompleted()</code>, after which the stream has ended. </p> <p> The Rx implementation is simpler than some message-based systems I just outlined. That's the reason I chose it for this article. It doesn't mean that it's better, because that simplicity comes at the expense of missing capabilities. This system has no persistence, and I while I'm no expert in this field, I don't think it easily expands to a distributed system. And again, to perhaps belabour the obvious, I'm not insisting that any of those capabilities are always needed. I'm only trying to outline some of the trade-offs you should be aware of. </p> <h3 id="67a381ed508a482cb6359fb3eb9a2a88"> Handle other listeners <a href="#67a381ed508a482cb6359fb3eb9a2a88">#</a> </h3> <p> <code>HandleOwnScrobblesObservable</code> objects publish <code>Scrobble</code> objects. What does the next 'filter' look like? It's another observable stream, implemented by a class called <code>HandleOtherListenersObservable</code>. It implements <code><span style="color:#2b91af;">IObservable</span>&lt;<span style="color:#2b91af;">User</span>&gt;</code>, and its class declaration, constructor, and <code>Subscribe</code> implementation look a lot like what's already on display above. The main difference is the <code>Produce</code> method. </p> <p> <pre><span style="color:blue;">private</span>&nbsp;<span style="color:blue;">async</span>&nbsp;<span style="color:#2b91af;">Task</span>&nbsp;<span style="font-weight:bold;color:#74531f;">Produce</span>(<span style="color:#2b91af;">IObserver</span>&lt;<span style="color:#2b91af;">User</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>) { &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Impure</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListeners</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;_songService &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">GetTopListenersAsync</span>(scrobble.Song.Id); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Pure</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListenersSnapshot</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListeners</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Where</span>(<span style="font-weight:bold;color:#1f377f;">u</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>.TotalScrobbleCount&nbsp;&gt;=&nbsp;10_000) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">OrderByDescending</span>(<span style="font-weight:bold;color:#1f377f;">u</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">u</span>.TotalScrobbleCount) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Take</span>(20); &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:green;">//&nbsp;Impure</span> &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">foreach</span>&nbsp;(<span style="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListener</span>&nbsp;<span style="font-weight:bold;color:#8f08c4;">in</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">otherListenersSnapshot</span>) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>.<span style="font-weight:bold;color:#74531f;">OnNext</span>(<span style="font-weight:bold;color:#1f377f;">otherListener</span>); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>.<span style="font-weight:bold;color:#74531f;">OnCompleted</span>(); }</pre> </p> <p> Compared to the reference architecture, this implementation is hardly surprising. The most important point to make is that, as was the goal all along, this is another small <a href="/2025/01/13/recawr-sandwich">Recawr Sandwich</a>. </p> <p> A third observable, <code>HandleOtherScrobblesObservable</code>, handles the third step of the algorithm, and looks much like <code>HandleOtherListenersObservable</code>. You can see it in the Git repository. </p> <h3 id="267208bf1d944a2890cba3efcf3edd97"> Composition <a href="#267208bf1d944a2890cba3efcf3edd97">#</a> </h3> <p> The three observable streams constitute most of the building blocks required to implement the song recommendations algorithm. Notice the 'fan-out' nature of the observables. The first step starts with a single <code>userName</code> and produces up to 100 scrobbles. To handle <em>each</em> scrobble, a new instance of <code>HandleOtherListenersObservable</code> is required, and each of those produces up to twenty <code>User</code> notifications, and so on. </p> <p> In the abstract, we may view the <code>HandleOwnScrobblesObservable</code> constructor as a function from <code>string</code> to <code><span style="color:#2b91af;">IObservable</span>&lt;<span style="color:#2b91af;">Scrobble</span>&gt;</code>. Likewise, we may view the <code>HandleOtherListenersObservable</code> constructor as a function that takes a single <code>Scrobble</code> as input, and gives an <code><span style="color:#2b91af;">IObservable</span>&lt;<span style="color:#2b91af;">User</span>&gt;</code> as return value. And finally, <code>HandleOtherScrobblesObservable</code> takes a single <code>User</code> as input to return <code><span style="color:#2b91af;">IObservable</span>&lt;<span style="color:#2b91af;">Song</span>&gt;</code> as output. </p> <p> Quick, what does that look like, and how do you compose them? </p> <p> Indeed, those are <a href="/2022/04/04/kleisli-composition">Kleisli arrows</a>, but in practice, we use <a href="/2022/03/28/monads">monadic bind</a> to compose them. In C# this usually means <code>SelectMany</code>. </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;">IReadOnlyList</span>&lt;<span style="color:#2b91af;">Song</span>&gt;&gt;&nbsp;<span style="font-weight:bold;color:#74531f;">GetRecommendationsAsync</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="color:blue;">var</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HandleOwnScrobblesObservable</span>(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;_songService) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">SelectMany</span>(<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HandleOtherListenersObservable</span>(<span style="font-weight:bold;color:#1f377f;">s</span>,&nbsp;_songService)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">SelectMany</span>(<span style="font-weight:bold;color:#1f377f;">u</span>&nbsp;=&gt;&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HandleOtherScrobblesObservable</span>(<span style="font-weight:bold;color:#1f377f;">u</span>,&nbsp;_songService)) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ToList</span>(); &nbsp;&nbsp;&nbsp;&nbsp;<span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">OrderByDescending</span>(<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.Rating) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Take</span>(200) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ToArray</span>(); }</pre> </p> <p> The fourth step of the algorithm, you may notice, isn't implemented as an observable, but rather as a standard LINQ pipeline. This is because sorting is required, and if there's a way to sort an observable, I'm not aware of it. After all, given that observable objects may represent infinite data streams, I readily accept that there's no <code>OrderByDescending</code> method on <code>IObservable&lt;T&gt;</code>. (But then, the <a href="https://www.nuget.org/packages/System.Reactive/">System.Reactive</a> library defines <code>Min</code> and <code>Max</code> operations, and exactly how those work when faced with infinite streams, I haven't investigated.) </p> <p> While I could have created a helper function for that small <code>OrderByDescending</code>/<code>Take</code>/<code>ToArray</code> pipeline, I consider it under the <a href="https://wiki.haskell.org/Fairbairn_threshold">Fairbairn threshold</a>. </p> <h3 id="d8778bbf0f6a4e14b0d24181849ff943"> Query syntax <a href="#d8778bbf0f6a4e14b0d24181849ff943">#</a> </h3> <p> You can also compose the algorithm using query syntax, which I personally find prettier. </p> <p> <pre><span style="color:#2b91af;">IObservable</span>&lt;<span style="color:#2b91af;">Song</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>&nbsp;= &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;scr&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HandleOwnScrobblesObservable</span>(<span style="font-weight:bold;color:#1f377f;">userName</span>,&nbsp;_songService) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;usr&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HandleOtherListenersObservable</span>(scr,&nbsp;_songService) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">from</span>&nbsp;sng&nbsp;<span style="color:blue;">in</span>&nbsp;<span style="color:blue;">new</span>&nbsp;<span style="color:#2b91af;">HandleOtherScrobblesObservable</span>(usr,&nbsp;_songService) &nbsp;&nbsp;&nbsp;&nbsp;<span style="color:blue;">select</span>&nbsp;sng; <span style="color:#2b91af;">IList</span>&lt;<span style="color:#2b91af;">Song</span>&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span>&nbsp;=&nbsp;<span style="font-weight:bold;color:#8f08c4;">await</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">obs</span>.<span style="font-weight:bold;color:#74531f;">ToList</span>(); <span style="font-weight:bold;color:#8f08c4;">return</span>&nbsp;<span style="font-weight:bold;color:#1f377f;">songs</span> &nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">OrderByDescending</span>(<span style="font-weight:bold;color:#1f377f;">s</span>&nbsp;=&gt;&nbsp;<span style="font-weight:bold;color:#1f377f;">s</span>.Rating) &nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">Take</span>(200) &nbsp;&nbsp;&nbsp;&nbsp;.<span style="font-weight:bold;color:#74531f;">ToArray</span>();</pre> </p> <p> In this code snippet I've used explicit variable type declarations (instead of using the <code>var</code> keyword) for the sole purpose of making it easier to see which types are involved. </p> <h3 id="5b5ac82d3d67486bac8118e59f6b9d1b"> Conclusion <a href="#5b5ac82d3d67486bac8118e59f6b9d1b">#</a> </h3> <p> This article shows an implementation example of refactoring the song recommendations problem to a pipes-and-filters architecture. It uses Reactive Extensions for .NET, since this showcases the (de)composition in the simplest possible way. Hopefully, you can extrapolate from this to a more elaborate, distributed asynchronous message-based system, if you need something like that. </p> <p> The next example makes a small move in that direction. </p> <p> <strong>Next:</strong> <a href="/2025/07/28/song-recommendations-with-f-agents">Song recommendations with F# agents</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/07/21/song-recommendations-with-c-reactive-extensions Song recommendations with pipes and filters https://blog.ploeh.dk/2025/07/14/song-recommendations-with-pipes-and-filters/ Mon, 14 Jul 2025 14:52:00 UTC <div id="post"> <p> <em>Composing small Recawr Sandwiches.</em> </p> <p> This article is part of a larger series that outlines various <a href="/2025/04/07/alternative-ways-to-design-with-functional-programming">alternative ways to design with functional programming</a>. That (first) article contains a table of contents, as well as outlines the overall programme and the running example. In short, the example is a song recommendation engine that works on large data sets. </p> <p> Previous articles in this series have explored <a href="/2025/04/28/song-recommendations-as-an-impureim-sandwich">refactoring to a pure function</a> and <a href="/2025/06/09/song-recommendations-from-combinators">composing impure actions with combinators</a>. In the next few articles, we'll look at how to use message-based architectures to decouple the algorithm into smaller <a href="/2025/01/13/recawr-sandwich">Recawr Sandwiches</a>. As an overall concept, we may term such an architecture <em>pipes and filters</em>. The book <a href="/ref/eip">Enterprise Integration Patterns</a> is a great resource for this kind of (de)composition. Don't be mislead by the title: In essence, it's neither about enterprise programming nor integration. </p> <h3 id="0ce73de5ddf24106adc6a3890fc3fc9b"> Workflows of small sandwiches <a href="#0ce73de5ddf24106adc6a3890fc3fc9b">#</a> </h3> <p> As speculated in <a href="/2025/04/28/song-recommendations-as-an-impureim-sandwich">Song recommendations as an Impureim Sandwich</a>, the data sets involved when finding song recommendations for a user may be so large that an <a href="/2020/03/02/impureim-sandwich">Impureim Sandwich</a> is impractical. </p> <p> On the other hand, a message-based system essentially consists of many small message handlers that each may be implemented as Impureim Sandwiches. I've already briefly discussed this kind of decomposition in <a href="/2017/07/10/pure-interactions">Pure interactions</a>, where each message handler or 'actor' is a small process equivalent to a web request handler (Controller) or similar. </p> <p> When it comes to the song recommendation problem, we may consider a small pipes-and-filters architecture that uses small 'filters' to start even more work, handled by other filters, and so on. </p> <p> <img src="/content/binary/song-recommendations-pipes-and-filters.png" alt="Three boxes with arrows between them indicating messages going from left to right."> </p> <p> Depending on the exact implementation details, you may call this <em>pipes and filters</em>, <em>reactive functional programming</em>, the <em>actor model</em>, <em>map/reduce</em>, or something else. What I consider crucial in this context is that each 'filter' is a small Recawr Sandwich. It queries the out-of-process music data service, applies a <a href="https://en.wikipedia.org/wiki/Pure_function">pure function</a> to that data, and finally sends more messages over some impure channel. In the following articles, you'll see code examples. </p> <ul> <li><a href="/2025/07/21/song-recommendations-with-c-reactive-extensions">Song recommendations with C# Reactive Extensions</a></li> <li><a href="/2025/07/28/song-recommendations-with-f-agents">Song recommendations with F# agents</a></li> </ul> <p> As I'm writing this, I don't plan to supply a <a href="https://www.haskell.org/">Haskell</a> example. The main reason is that I've no experience with writing asynchronous message-based systems with Haskell, and while a quick web search indicates that there are plenty of libraries for <a href="https://wiki.haskell.org/Functional_Reactive_Programming">reactive functional programming</a>, on the other hand, I can't find much when it comes to message-bus-based asynchronous messaging. </p> <p> Perhaps it'd be more idiomatic to supply an <a href="https://www.erlang.org/">Erlang</a> example, but it's been too many years since I tried teaching myself Erlang, and I never became proficient with it. </p> <h3 id="02e1dda85220460db2d3f568c7c98942"> Modelling <a href="#02e1dda85220460db2d3f568c7c98942">#</a> </h3> <p> It turns out that when you decompose the song recommendation problem into smaller 'filters', each of which is a Recawr Sandwich, you arrive at a decomposition that looks suspiciously close to what we saw in <a href="/2025/06/09/song-recommendations-from-combinators">Song recommendations from combinators</a>. And as <a href="https://tyrrrz.me/blog/pure-impure-segregation-principle">Oleksii Holub wrote</a>, </p> <blockquote> <p> "However, instead of having one cohesive element to reason about, we ended up with multiple fragments, each having no meaning or value of their own. While unit testing of individual parts may have become easier, the benefit is very questionable, as it provides no confidence in the correctness of the algorithm as a whole." </p> </blockquote> <p> This remains true here. Why even bother, then? </p> <p> The purpose of this article series is to present alternatives, just like <a href="https://fsharpforfunandprofit.com/">Scott Wlaschin</a>'s excellent article <a href="https://fsharpforfunandprofit.com/posts/13-ways-of-looking-at-a-turtle/">Thirteen ways of looking at a turtle</a>. It may be that a given design alternative isn't the absolute best fit for the song recommendation problem, but it may, on the other hand, be a good fit for some other problem that you run into. If so, you should be able to extrapolate from the articles in this series. </p> <h3 id="577f32d80d674ac48c254e231f647d26"> Conclusion <a href="#577f32d80d674ac48c254e231f647d26">#</a> </h3> <p> Given that <a href="https://x.com/Tyrrrz/status/1493369905869213700">we know that the real code that the song recommendation example is based off runs for about ten minutes</a>, some kind of asynchronous process that may support progress indication or cancellation may be worth considering. This easily leads us in the direction of some kind of pipes-and-filters architecture. </p> <p> You can implement such an architecture with in-memory message streams, as the next article does, or you can go with a full-fledged messaging system based on persistent message buses and distributed, restartable message handlers. The details vary, but it's essentially the same kind of architecture. </p> <p> <strong>Next:</strong> <a href="/2025/07/21/song-recommendations-with-c-reactive-extensions">Song recommendations with C# Reactive Extensions</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/07/14/song-recommendations-with-pipes-and-filters