Song recommendations from combinators
Interleaving impure actions with pure functions. Not really functional programming.
This article is part of a larger article series about
alternative ways to design with functional programming, particularly when faced with massive data loads. In the previous few articles, you saw
functional architecture at its apparent limit. With sufficiently large data sizes, the
Impureim Sandwich pattern starts to buckle. That's really not an indictment of that pattern; only an observation that no design pattern applies universally.
In this and the next few articles, we'll instead look at a more pragmatic option. In this article I'll discuss the general idea, and follow up in other articles with examples in three different languages.
In this overall article series, I'm using https://tyrrrz.me/
as an outset for the code example. Previous articles in this article series have already covered the basics, but the gist of it is a song recommendation service that uses past play information ('scrobbles') to suggest new songs to a user.
Separating pure functions from impure composition
#
In the original article, Oleksii Holub suggests a way to separate https://en.wikipedia.org/wiki/Pure_function
from impure actions: We may extract as much pure code from the overall algorithm as possible, but we're still left with pure functions and impure actions mixed together.
Here's my reproduction of that suggestion, with trivial modifications:
// Pure
public static IReadOnlyList
HandleOwnScrobbles(IReadOnlyCollection scrobbles) =>
scrobbles
.OrderByDescending(s => s.ScrobbleCount)
.Take(100)
.Select(s => s.Song.Id)
.ToArray();
// Pure
public static IReadOnlyList HandleOtherListeners(IReadOnlyCollection users) =>
users
.Where(u => u.TotalScrobbleCount >= 10_000)
.OrderByDescending(u => u.TotalScrobbleCount)
.Take(20)
.Select(u => u.UserName)
.ToArray();
// Pure
public static IReadOnlyList HandleOtherScrobbles(IReadOnlyCollection scrobbles) =>
scrobbles
.Where(s => s.Song.IsVerifiedArtist)
.OrderByDescending(s => s.Song.Rating)
.Take(10)
.Select(s => s.Song)
.ToArray();
// Pure
public static IReadOnlyList FinalizeRecommendations(IReadOnlyList songs) =>
songs
.OrderByDescending(s => s.Rating)
.Take(200)
.ToArray();
public async Task> GetRecommendationsAsync(string userName)
{
// Impure
var scrobbles = await _songService.GetTopScrobblesAsync(userName);
// Pure
var songIds = HandleOwnScrobbles(scrobbles);
var recommendationCandidates = new List();
foreach (var songId in songIds)
{
// Impure
var otherListeners = await _songService
.GetTopListenersAsync(songId);
// Pure
var otherUserNames = HandleOtherListeners(otherListeners);
foreach (var otherUserName in otherUserNames)
{
// Impure
var otherScrobbles = await _songService
.GetTopScrobblesAsync(otherUserName);
// Pure
var songsToRecommend = HandleOtherScrobbles(otherScrobbles);
recommendationCandidates.AddRange(songsToRecommend);
}
}
// Pure
return FinalizeRecommendations(recommendationCandidates);
}
As Oleksii Holub writes,
"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."
I agree with that assessment, but still find it warranted to pursue the idea a little further. After all, my goal with this overall article series isn't to be prescriptive, but rather descriptive. By presenting and comparing alternatives, we become aware of more options. This, hopefully, helps us choose the 'right tool for the job'.
Triple-decker sandwich? #
If we look closer at this alternative, however, we find that we only need to deal with three impure actions. We might, then, postulate that this is an expanded sandwich - a triple-decker sandwich, if you will.
To be clear, I don't find this a reasonable argument. Even if you accept expanding the sandwich metaphor to add a pure validation step, the number of layers, and the structure of the sandwich would still be known at compile time. You may start at the impure boundary, then phase into pure validation, return to another impure step to gather data, call your 'main' pure function, and finally write the result to some kind of output. To borrow a figure from the What's a sandwich? article:
On the other hand, this isn't what the above code suggestion does. The problem with the song recommendation algorithm is that the impure actions cascade. While we start with a single impure out-of-process query, we then use the result of that to loop over, and perform n more queries. This, in fact, happens again, nested in the outer loop, so in terms of network calls, we're looking at an O(n2) algorithm.
We can actually be more precise than that, because the 'outer' queries actually limit their result sets. The first query only considers the top 100 results, so we know that GetTopListenersAsync is going to be called at most 100 times. The result of this call is again limited to the top 20, so that the inner calls to GetTopScrobblesAsync run at most 20 * 100 = 2,000 times. In all, the upper limit is 1 + 100 + 2,000 = 2,101 network calls. (Okay, so really, this is just an O(1) algorithm, although 1 ~ 2,101.)
Not that that isn't going to take a bit of time.
All that said, it's not execution time that concerns me in this context. Assume that the algorithm is already as optimal as possible, and that those 2,101 network calls are necessary. What rather concerns me here is how to organize the code in a way that's as maintainable as possible. As usual, when that's the main concern, I'll remind the reader to consider the example problem as a stand-in for a more complicated problem. Even Oleksii Holub's original code example is only some fifty-odd lines of code, which in itself hardly warrants all the hand-wringing we're currently subjecting it to.
Rather, what I'd like to address is the dynamic back-and-forth between pure function and impure action. Each of these thousands of out-of-process calls are non-deterministic. If you're tasked with maintaining or editing this algorithm, your brain will be taxed by all that unpredictable behaviour. Many subtle bugs lurk there.
The more we can pull the code towards pure functions the better, because referential transparency fits in your head.
So, to be explicit, I don't consider this kind of composition as an expanded Impureim Sandwich.
Standard combinators #
Is it possible to somehow improve, even just a little, on the above suggestion? Can we somehow make it look a little 'more functional'?
We could use some standard combinators, like monadic bind, traversals, and so on.
To be honest, for the specific song-recommendations example, the benefit is marginal at best, but doing it would still demonstrate a particular technique. We'd be able to get rid of the local mutation of recommendationCandidates, but that's about it.
Even so, refactoring to self-contained expressions makes other refactoring easier. As a counter-example, imagine that you'd like to extract the inner foreach loop in the above code example to a helper method.
private async Task CollectOtherUserTopScrobbles(
List recommendationCandidates,
IReadOnlyList otherUserNames)
{
foreach (var otherUserName in otherUserNames)
{
// Impure
var otherScrobbles = await _songService
.GetTopScrobblesAsync(otherUserName);
// Pure
var songsToRecommend = HandleOtherScrobbles(otherScrobbles);
recommendationCandidates.AddRange(songsToRecommend);
}
}
The call site would then look like this:
// Pure
var otherUserNames = HandleOtherListeners(otherListeners);
// Impure
await CollectOtherUserTopScrobbles(recommendationCandidates, otherUserNames);
In this specific example, such a refactoring isn't too difficult, but it's more complicated than it could be. Because of state mutation, we have to pass the object to be modified, in this case recommendationCandidates, along as a method argument. Here, there's only one, but if you have code where you change the state of two objects, you'd have to pass two extra parameters, and so on.
You've most likely worked in a real code base where you have tried to extract a helper method, only to discover that it's so incredibly tangled with the objects that it modifies that you need a long parameter list. What should have been a simplification is in danger of making everything worse.
On the other hand, self-contained expressions, even if, as in this case, they're non-deterministic, don't mutate state. In general, this tends to make it easier to extract subexpressions as helper methods, if only because they are less coupled to the rest of the code. They may required inputs as parameters, but at least you don't have to pass around objects to be modified.
Thus, the reason I find it worthwhile to include articles about this kind of refactoring is that, since it demonstrates how to refactor to a more expression-based style, you may be able to extrapolate to your own context. And who knows, you may encounter a context where more substantial improvements can be made by moving in this direction.
As usual in this article series, you'll see how to apply this technique in three different languages.
Song recommendations from C# combinators
Song recommendations from F# combinators
Song recommendations from Haskell combinators
All that said, it's important to underscore that I don't consider this proper functional architecture. Even the Haskell example is too non-deterministic to my tastes.
Conclusion #
Perhaps the most pragmatic approach to a problem like the song-recommendations example is to allow the impure actions and pure functions to interleave. I don't mean to insist that functional programming is the only way to make code maintainable. You can organize code according to other principles, and some of them may also leave you with a code base that can serve its mission well, now and in the future.
Another factor to take into account is the skill level of the team tasked with maintaining a code base. What are they comfortable with?
Not that I think you should settle for status quo. Progress can only be made if you push the envelop a little, but you can also come up with a code base so alien to your colleagues that they can't work with it at all.
I could easily imagine a team where the solution in the next three articles is the only style they'd be able to maintain.
Next: Song recommendations from C# combinators.
This blog is totally free, but if you like it, please consider https://blog.ploeh.dk/support
.
https://blog.ploeh.dk/2025/06/09/song-recommendations-from-combinators/
@ ploeh blog (RSS Feed)
2025-06-09 14:02:00Song recommendations from combinators Interleaving impure actions with pure functions. Not really functional programming. This article is part of a larger article series about alternative ways to design with functional programming, particularly when faced with massive data loads. In the previous few articles, you saw functional architecture at its apparent limit. With sufficiently large data sizes, the Impureim Sandwich pattern starts to buckle. That's really not an indictment of that pattern; only an observation that no design pattern applies universally. In this and the next few articles, we'll instead look at a more pragmatic option. In this article I'll discuss the general idea, and follow up in other articles with examples in three different languages. In this overall article series, I'm using https://tyrrrz.me/ as an outset for the code example. Previous articles in this article series have already covered the basics, but the gist of it is a song recommendation service that uses past play information ('scrobbles') to suggest new songs to a user. Separating pure functions from impure composition # In the original article, Oleksii Holub suggests a way to separate https://en.wikipedia.org/wiki/Pure_function from impure actions: We may extract as much pure code from the overall algorithm as possible, but we're still left with pure functions and impure actions mixed together. Here's my reproduction of that suggestion, with trivial modifications: // Pure public static IReadOnlyList