Song recommendations with C# free monads by Mark Seemann
Just because it's possible. Don't do this at work.
This is the last article in a series named Alternative ways to design with functional programming. 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 Haskell and F#. In this article, I'll repeat the exercise in C#. It's not going to be pretty, but it's possible.
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.
The code shown here is based on the free branch of the DotNet Git repository available with this article series.
Functor #
A free monad enables you to define a monad from any functor. 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 SongService interface with this instruction set.
As a reminder, this is the interface:
public interface SongService { Task<IReadOnlyCollection<User>> GetTopListenersAsync(int songId); Task<IReadOnlyCollection<Scrobble>> GetTopScrobblesAsync(string userName); }
I'll remind the reader that the code is my attempt to reconstruct the sample code shown in Pure-Impure Segregation Principle. I don't know if SongService is a base class or an interface. Based on the lack of the idiomatic C# I 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.
In any case, the goal is to replace it with an instruction set, starting with a sum type. Since C# comes with no native support for sum types, we'll need to model it with either Church encoding or a Visitor. 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.
I start by creating a new class called SongInstruction<T> with this method:
public TResult Match<TResult>( Func<(int, Func<IReadOnlyCollection<User>, T>), TResult> getTopListeners, Func<(string, Func<IReadOnlyCollection<Scrobble>, T>), TResult> getTopScrobbles) { return imp.Match(getTopListeners, getTopScrobbles); }
If you squint sufficiently hard, you may be able to see how the getTopListeners parameter corresponds to the interface's GetTopListenersAsync method, and likewise for the other parameter.
I'm not going to give you a very detailed walkthrough, as I've already done that earlier in a different context. Likewise, I'll skip some of the implementation details. All the code is available in the Git repository.
To be a functor, the class needs a Select method.
public SongInstruction<TResult> Select<TResult>(Func<T, TResult> selector) { return Match( t => SongInstruction.GetTopListeners( t.Item1, // songId users => selector(t.Item2(users))), t => SongInstruction.GetTopScrobbles( t.Item1, // userName songs => selector(t.Item2(songs)))); }
The name t is, in both cases, short for tuple. 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 Item2 is the 'continuation' function.
Monad #
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 SongProgram<T>, characterized by this Match method:
public TResult Match<TResult>( Func<SongInstruction<SongProgram<T>>, TResult> free, Func<T, TResult> pure) { return imp.Match(free, pure); }
A SelectMany method is required to make this type a proper monad:
public SongProgram<TResult> SelectMany<TResult>( Func<T, SongProgram<TResult>> selector) { return Match( i => SongProgram.Free(i.Select(p => p.SelectMany(selector))), selector); }
The code is already verbose enough as it is, so I've used i for instruction and p for program.
Lifted helpers #
Although not strictly required, I often find it useful to add a helper method for each case of the instruction type:
public static SongProgram<IReadOnlyCollection<User>> GetTopListeners(int songId) { return Free(SongInstruction.GetTopListeners(songId, Pure)); } public static SongProgram<IReadOnlyCollection<Scrobble>> GetTopScrobbles(string userName) { return Free(SongInstruction.GetTopScrobbles(userName, Pure)); }
This just makes the user code look a bit cleaner.
Song recommendations as a DSL #
Using the composition from Song recommendations from C# combinators as a starting point, it doesn't take that many changes to turn it into a SongProgram-valued function.
public static SongProgram<IReadOnlyList<Song>> GetRecommendations(string userName) { // 1. Get user's own top scrobbles // 2. Get other users who listened to the same songs // 3. Get top scrobbles of those users // 4. Aggregate the songs into recommendations return SongProgram.GetTopScrobbles(userName) .SelectMany(scrobbles => UserTopScrobbles(scrobbles) .Traverse(scrobble => SongProgram .GetTopListeners(scrobble.Song.Id) .Select(TopListeners) .SelectMany(users => users .Traverse(user => SongProgram .GetTopScrobbles(user.UserName) .Select(TopScrobbles)) .Select(Songs))) .Select(TakeTopRecommendations)); }
Notice how much it resembles the original GetRecommendationsAsync method on the RecommendationsProvider class. Instead of songService.GetTopScrobblesAsync it just has SongProgram.GetTopScrobbles, and instead of songService.GetTopListenersAsync it has SongProgram.GetTopListeners.
To support this composition, however, a traversal is required.
Traverse #
The traversal needs a Select function on SongProgram, so we'll start with that.
public SongProgram<TResult> Select<TResult>(Func<T, TResult> selector) { return SelectMany(x => SongProgram.Pure(selector(x))); }
This is the standard implementation of a functor from a monad.
It turns out that it's also useful to define a function to concatenate two sequence-valued programs.
private static SongProgram<IEnumerable<T>> Concat<T>( this SongProgram<IEnumerable<T>> xs, SongProgram<IEnumerable<T>> ys) { return xs.SelectMany(x => ys.Select(y => x.Concat(y))); }
This could, perhaps, be a public function, but in this situation, I only need it to implement Traverse, so I kept it private. The Traverse function, on the other hand, is public.
public static SongProgram<IEnumerable<TResult>> Traverse<T, TResult>( this IEnumerable<T> source, Func<T, SongProgram<TResult>> selector) { return source.Aggregate( Pure(Enumerable.Empty<TResult>()), (acc, x) => acc.Concat(selector(x).Select(xr => new[] {xr}.AsEnumerable()))); }
Given a sequence of values, Traverse applies selector to each, and collects all resulting programs into a single sequence-valued program. You see it in use in the above GetRecommendations composition.
Interpreter #
That last missing piece is an interpreter that can evaluate a program. Since I already have a class called FakeSongService, adding an Interpret method was the easiest implementation strategy.
public T Interpret<T>(SongProgram<T> program) { return program.Match( i => i.Match( t => Interpret(t.Item2(GetTopListernes(t.Item1))), t => Interpret(t.Item2(GetTopScrobbles(t.Item1)))), x => x); }
Here, GetTopListernes and GetTopScrobbles are two private helper functions:
private IReadOnlyCollection<User> GetTopListernes(int songId) { var listeners = from kvp in users where kvp.Value.ContainsKey(songId) select new User(kvp.Key, kvp.Value.Values.Sum()); return listeners.ToList(); } private IReadOnlyCollection<Scrobble> GetTopScrobbles(string userName) { var scrobbles = users .GetOrAdd(userName, new ConcurrentDictionary<int, int>()) .Select(kvp => new Scrobble(songs[kvp.Key], kvp.Value)); return scrobbles.ToList(); }
The implementation closely mirrors the original Fake interface implementation, where users and songs are class fields on FakeSongService. This class was first shown in Characterising song recommendations.
It's now possible to rewrite all the tests.
Refactoring the tests #
Since the original GetRecommendationsAsync method was task-based, all tests had to run in task workflows. This is no longer necessary, as this simplified FsCheck property demonstrates:
[<Property>] let ``One user, some songs`` () = gen { let! user = Gen.userName let! songs = Gen.arrayOf Gen.song let! scrobbleCounts = Gen.choose (1, 100) |> Gen.arrayOfLength songs.Length return (user, Array.zip songs scrobbleCounts) } |> Arb.fromGen |> Prop.forAll <| fun (user, scrobbles) -> let srvc = FakeSongService () scrobbles |> Array.iter (fun (s, c) -> srvc.Scrobble (user, s, c)) let actual = RecommendationsProvider.GetRecommendations user |> srvc.Interpret Assert.Empty actual
Originally, this test had to be defined in terms of the task computation expression, but now it's a pure function. In the act phase the test calls RecommendationsProvider.GetRecommendations user and pipes the returned program to srvc.Interpret. The result, actual, is a plain IReadOnlyCollection<Song> value.
Similarly, I was able to migrate all the example-based tests over, too.
[<Fact>] let ``One verified recommendation`` () = let srvc = FakeSongService () srvc.Scrobble ("cat", Song (1, false, 6uy), 10) srvc.Scrobble ("ana", Song (1, false, 5uy), 10) srvc.Scrobble ("ana", Song (2, true, 5uy), 9_9990) let actual = RecommendationsProvider.GetRecommendations "cat" |> srvc.Interpret Assert.Equal<Song> ([ Song (2, true, 5uy) ], actual)
Once all tests were migrated over to the new GetRecommendations function, I deleted the old RecommendationsProvider class as well as the SongService interface, since none of them were required any longer.
Conclusion #
The lack of proper syntactic sugar, similar to do notation in Haskell, or computation expressions 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.
