Free monad approach in C# by Mark Seemann

[TysonMN]

At least a few times @louthy, you have mentioned trying find an acceptable way to implement free monads in C#. In case you hadn't see this, Mark Seemann wrote a blog post about one way this can be done. Unfortunately, one reason that he wrote that post is to show people that the approach he presents isn't acceptable. Maybe it will give you an idea though.

[seerek]

I'm slowly educating myself on functional programming and for some time I'm reading what @louthy, @ploeh and others are writing about Free Monad and I'm surprised that no one noticed that we have it under our nose, built in into C# compiler. As long as I understand, Free monad is just abstract syntax tree that can be parsed/interpreted depending on the context.

This is exactly what Expression is for, and IQueryable is best example of it. See my quickly sketched example where I've implemented code mentioned in the Question you've mentioned.

using System;
using System.Linq.Expressions;

namespace ConsoleApp7
{
    static class Program
    {
        static void Main()
        {
            var definition = Prg(null, null);
            var program = definition.Compile();

            program(new Consl(), new AuthImpl());
            Console.ReadLine();
        }

        static Expression<Action<UI, Auth>> Prg(UI u, Auth a)
        {
            Expression<Func<UI>> x = () => u;
            Expression<Func<Auth>> y = () => a;

            return from ui in x
                   from auth in y
                    let uid = ui.Ask("What's your user ID?")
                    let pwd = ui.Ask("Password, please.")
                    let user = auth.Login(uid, pwd)
                    let hasPerm = auth.HasPermission(user, Permission.KnownSecret)
                    let message = hasPerm ? "UUDDLRLRBA" : "Go away!"
                   select ui.Tell(message);
        }

        static Expression<Func<A, B, C>> SelectMany<A, B, C>(this Expression<Func<A>> left, Expression<Func<A, Expression<Func<B>>>> right, Expression<Func<A, B, C>> projection)
        {
            return projection;
        }

        static Expression<Func<A, B, D>> Select<A, B, C, D>(this Expression<Func<A, B, C>> left, Expression<Func<C, D>> projection)
        {
            var a = Expression.Parameter(typeof(A), "a");
            var b = Expression.Parameter(typeof(B), "b");

            return Expression.Lambda<Func<A, B, D>>(Expression.Invoke(projection, Expression.Invoke(left, a, b)), a, b);
            //return (a, b) => projection(left(a, b));
        }

        static Expression<Action<A, B>> Select<A, B, C>(this Expression<Func<A, B, C>> left, Expression<Action<C>> action)
        {
            var a = Expression.Parameter(typeof(A), "a");
            var b = Expression.Parameter(typeof(B), "b");

            return Expression.Lambda<Action<A, B>>(Expression.Invoke(action, Expression.Invoke(left, a, b)), a, b);
            //return (a, b) => action(left(a, b));
        }

    }

    interface UI
    {
        void Tell(string msg);
        string Ask(string prompt);
    }

    class Consl : UI
    {
        public void Tell(string msg) => Console.WriteLine(msg);

        public string Ask(string prompt)
        {
            Console.WriteLine(prompt);
            return Console.ReadLine();
        }
    }

    interface Auth
    {
        User Login(string id, string pwd);
        bool HasPermission(User u, Permission p);
    }

    class AuthImpl : Auth
    {
        public User Login(string id, string pwd) => new User();

        public bool HasPermission(User u, Permission p) => true;
    }

    public struct Permission
    {
        public static Permission KnownSecret = new Permission();
    }

    public struct User
    {
    }
}

As you can see, I've not parsed the expression, just compiled it and run, but if there will be such need we can either parse it, or replace parts of it using our own implementation of ExpressionVisitor. Of course we are limited by C# compiler which doesn't allow Expressions to have multiple statements and to workaround it I've wrote SelectMany() and Select() methods that allowed me to compose multiple statements into one using LINQ (as I understand, composition was main problem of @louthy).

This, while very readable makes code hard to parse. Why?

return from ui in x
                   from auth in y
                    let uid = ui.Ask("What's your user ID?")
                    let pwd = ui.Ask("Password, please.")
                    let user = auth.Login(uid, pwd)
                    let hasPerm = auth.HasPermission(user, Permission.KnownSecret)
                    let message = hasPerm ? "UUDDLRLRBA" : "Go away!"
                   select ui.Tell(message);

is compiled into

return x.SelectMany(ui => y, (ui, auth) => new {ui, auth})
                .Select(@t => new {@t, uid = @t.ui.Ask("What's your user ID?")})
                .Select(@t => new {@t, pwd = @t.@t.ui.Ask("Password, please.")})
                .Select(@t => new {@t, user = @t.@t.@t.auth.Login(@t.@t.uid, @t.pwd)})
                .Select(@t => new {@t, hasPerm = @t.@t.@t.@t.auth.HasPermission(@t.user, Permission.KnownSecret)})
                .Select(@t => new {@t, message = @t.hasPerm ? "UUDDLRLRBA" : "Go away!"})
                .Select(@t => @t.@t.@t.@t.@t.@t.ui.Tell(@t.message));

which produces following expression tree:

(a, b) => (<>h__TransparentIdentifier5 => <>h__TransparentIdentifier5.<>h__TransparentIdentifier4.<>h__TransparentIdentifier3.<>h__TransparentIdentifier2.<>h__TransparentIdentifier1.<>h__TransparentIdentifier0.ui.Tell(<>h__TransparentIdentifier5.message)).Invoke(
    ((a, b) => (<>h__TransparentIdentifier4 => new { <>h__TransparentIdentifier4 = <>h__TransparentIdentifier4, message = <>h__TransparentIdentifier4.hasPerm ? "UUDDLRLRBA" : "Go away!" }).Invoke(
        ((a, b) => (<>h__TransparentIdentifier3 => new { <>h__TransparentIdentifier3 = <>h__TransparentIdentifier3, hasPerm = <>h__TransparentIdentifier3.<>h__TransparentIdentifier2.<>h__TransparentIdentifier1.<>h__TransparentIdentifier0.auth.HasPermission(<>h__TransparentIdentifier3.user, Permission.KnownSecret) }).Invoke(
            ((a, b) => (<>h__TransparentIdentifier2 => new { <>h__TransparentIdentifier2 = <>h__TransparentIdentifier2, user = <>h__TransparentIdentifier2.<>h__TransparentIdentifier1.<>h__TransparentIdentifier0.auth.Login(<>h__TransparentIdentifier2.<>h__TransparentIdentifier1.uid, <>h__TransparentIdentifier2.pwd) }).Invoke(
                ((a, b) => (<>h__TransparentIdentifier1 => new { <>h__TransparentIdentifier1 = <>h__TransparentIdentifier1, pwd = <>h__TransparentIdentifier1.<>h__TransparentIdentifier0.ui.Ask("Password, please.") }).Invoke(
                    ((a, b) => (<>h__TransparentIdentifier0 => new { <>h__TransparentIdentifier0 = <>h__TransparentIdentifier0, uid = <>h__TransparentIdentifier0.ui.Ask("What's your user ID?") }).Invoke(((ui, auth) => new { ui = ui, auth = auth }).Invoke(a, b))).Invoke(a, b))).Invoke(a, b))).Invoke(a, b))).Invoke(a, b))).Invoke(a, b))

Who knows, maybe this is more scarier then it really is, because we may find that when we override ExpressionVisitor.VistMethodCall() to replace or parse it and filter there only types we are interested in, it may end up to be not so hard.

That's just my 2 cents to show potential solution. In the feature I will probably need to invent something like this to have one definition of reports that can be rendered into HTML, Excel, PDF, so maybe I will find a way to make it more parsable.

[ploeh]

As long as I understand, Free monad is just abstract syntax tree that can be parsed/interpreted depending on the context.

This is exactly what Expression is for, and IQueryable is best example of it.

We've had a discussion about this somewhere else (Twitter, I think), and I will, for the record, repeat what I wrote in that other context.

I don't think it enables understanding of free monads to insist that C# expression trees and IQueryable is equivalent to free monads.

In related terminology, the free monoid (careful here, we're now talking about monoids, not monads) is a monoid that's available 'for free', so to speak, regardless of the data you want to aggregate. In programming, this is synonymous with a linked list, or some other synonymous pure collection type. See also this Stack Overflow answer from today.

Likewise, a free monad is a monad that's available 'for free' for any functor. You should, for example, be able to define any domain-specific grammar as a functor, and then be able to produce a monad out of that 'for free'. As is the case with the free monoid, nothing actually happens in the monad until you apply some interpreter. The interpreter specifically walks over the expressions in the DSL.

C# expression trees may be a specific 'instance' of that 'pattern', but I don't think that it's a free monad in itself. I think that it's a specific monad.

[seerek]

You should, for example, be able to define any domain-specific grammar as a functor, and then be able to produce a monad out of that 'for free'.

I'm sorry @ploeh but this was too many m- and f- words without any examples for C# programmer like me. I'm not at that level yet (although I have Category Theory for Programmers on my TODO list) So currently I'm trying to understand it from practical point of view.

First of all: Why do we need Free Monad pattern?

My understanding: To separate definition/intent from execution, but not only as direction of dependencies but even physically.

Examples:

1. IQueryable allows me to specify my query definition in my Business Logic but be executed in my data source while making sure that dependency direction looks like this: DataSource --->Business Logic. Thanks to this my data source can be easily replaced without touching my Business Logic + because query is executed close to data I don't have problems with performance (while for example filtering data in BL)
2. Imagine that you have a financial report with a lot of details for each product your company is producing and while users want to see it on web page (HTML) often they need to verify the numbers in Excel. HTML web page will show only total numbers, but in Excel users want to see formulas to quickly find why some number is wrong. I can't imagine how this can be easy achieved by simple Dependency Injection and such separation of definition from execution seems like the only way. How would I do this in C#? By writing all formulas as C# Expression and probably use default implementation for HTML version, and parse Expressions when I need to convert them into Excel formulas.

As an exercise, so that we can talk about something less abstract, I have implemented example from your presentation about Free Monads in C# using Expressions.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Linq.Expressions;
using LanguageExt;

namespace ConsoleApp8
{
    static class Program
    {
        static void Main()
        {
            var definition = TryAcceptDefinition.ReplaceRepository(typeof(ReservationRepository), typeof(MockRepository));
            var program = definition.Compile();

            int? result = program(new Reservation {Date = DateTimeOffset.Now, Quantity = 101, IsAccepted = false});

            Debug.WriteLine(result.ToOption());
        }

        public static Expression<Func<Option<Reservation>, int?>> TryAcceptDefinition = res =>
                   (from reservation in res
                    where ReservationRepository.IsReservationInFuture(reservation)
                    let reservedSeats = ReservationRepository.ReadReservations(reservation.Date).Sum(r => r.Quantity)
                    where Capacity >= reservedSeats + reservation.Quantity
                    select ReservationRepository.Create(new Reservation
                    {
                        Date = reservation.Date,
                        Quantity = reservation.Quantity,
                        IsAccepted = true
                    })
                   )
                   .MatchUnsafe(x => x, () => null);

        public static int Capacity { get; } = 100;

        private static T ReplaceRepository<T>(this T expression, Type from, Type to) where T : Expression => 
            (T) new StaticCallTypeReplacer(@from, to).Visit(expression);
    }

    internal class StaticCallTypeReplacer : ExpressionVisitor
    {
        private readonly Type @from;
        private readonly Type to;

        public StaticCallTypeReplacer(Type @from, Type to)
        {
            this.@from = @from;
            this.to = to;
        }

        protected override Expression VisitMethodCall(MethodCallExpression call)
        {
            if (call.Method.DeclaringType == @from)
                return base.VisitMethodCall(Expression.Call(null, to.GetMethod(call.Method.Name), call.Arguments));
            return base.VisitMethodCall(call);
        }
    }

    internal class Reservation
    {
        public DateTimeOffset Date { get; set; }
        public int Quantity { get; set;  }
        public bool IsAccepted { get; set; }
    }

    internal static class ReservationRepository
    {
        public static bool IsReservationInFuture(Reservation reservation)
        {
            throw new NotImplementedException();
        }

        public static IEnumerable<Reservation> ReadReservations(DateTimeOffset date)
        {
            throw new NotImplementedException();
        }

        public static int? Create(Reservation reservation)
        {
            throw new NotImplementedException();
        }
    }

    internal static class MockRepository
    {
        public static bool IsReservationInFuture(Reservation reservation) => true;

        public static IEnumerable<Reservation> ReadReservations(DateTimeOffset date) => Enumerable.Empty<Reservation>();

        public static int? Create(Reservation reservation)
        {
            return 1;
        }
    }
}

@ploeh I think, that I've achieved the same you showed on your presentation but code doesn't look so scary as your version.

To simplify it, I've wrote it as one statement so that I will not need to care about composing Expressions. You can see that TryAccept() function is calling directly ReservationRepository static methods which are (for this example needs) intentionally not implemented so that they will fail when called. In the line

var definition = TryAcceptDefinition.ReplaceRepository(typeof(ReservationRepository), typeof(MockRepository));

I'm changing the implementation to MockRepository using StaticCallTypeReplacer ExpressionVisitor. This shows that such pattern allows us to not care about passing dependencies from method to method. We can call default implementation and replace it when needed. I'm not saying it's the way to do it, because this creates dependency from our business logic to default implementation of low level details, but just wanted to show such possibility. Of course If I want, I can parse it and interpret in any other way.

Now that I showed practical use of this pattern - questions to @ploeh and others smarter than me:

1. Is it free monad?
2. If not (because of some mathematical definition) - does it matter from practical point of view? Does real Free Monad gives me something I don't have here?
3. Can we do something to make it real free monad?

[ploeh]

this was too many m- and f- words without any examples for C# programmer like me

That's why I supplied links as well 😄 I know that there's a lot to read, so I don't expect anyone to be able to absorb it all in a couple of hours. It took me months to reach just a basic understanding of category theory. I've been at it for years now, and I only feel that I can talk sensibly about monoids, functors, monads, f-algebras, catamorphisms, and a few other things. I still don't understand the Yoneda lemma, and I only have the vaguest sense of what adjunctions are.

I've written blog posts to pave the way for others, particularly C# programmers, because the most accessible resource for programmers, Category Theory for Programmers, uses Haskell for its code examples. I hope that by explaining some of those things using C# instead, I can make some of this material accessible to another audience.

I still expect readers to invest significant time in this. If there's a way to explain this in depth in a few hours, I'm not aware of it.

Why do we need Free Monad pattern?

In C#, we don't. Dependency Injection is a much simpler way to address the same concerns.

In Haskell, on the other hand, Dependency Injection is impossible because it makes everything impure. You can attempt to use Dependency Injection (DI), but your code is simply not going to compile, because DI implies impurity. (You can, technically, get around this by making your entire Haskell code base impure, but then what's the point of the language?)

There's more than one way to get around that problem in Haskell. One is to use Haskell type classes in what some people call mtl style. For various reasons, I don't like that approach, although allegedly it performs better. Regardless of my bias, though, this alternative relies on a specific language feature (type classes), so doesn't readily translate to other languages.

Another alternative is free monads. As a universal abstraction (i.e. an abstraction based on mathematics, and thus universally existing as long as one accepts the underlying axioms) this abstraction is always available. In Haskell, this alternative is still great because the language has enough capability to make it fairly painless to use it.

Since the abstraction is universal, you can translate it to F# or even, as I've demonstrated, to C#, but since these languages don't readily support this style of programming, it becomes increasingly irrelevant as you move from language to language.

Just like Haskell offers more than one way to address issues with coupling, so do F# and C#. In F#, a more natural way to address the issue is with partial application, and in C#, the most natural principle is to use DI. As I've shown, partial application is equivalent to DI.

I think, that I've achieved the same you showed on your presentation but code doesn't look so scary as your version.

Indeed, but using DI is less scary still:

public class MaîtreD
{
    public MaîtreD(int capacity, IReservationsRepository reservationsRepository)
    {
        Capacity = capacity;
        ReservationsRepository = reservationsRepository;
    }

    public int? TryAccept(Reservation reservation)
    {
        if (!ReservationsRepository.IsReservationInFuture(reservation))
            return null;

        var reservedSeats = ReservationsRepository
            .ReadReservations(reservation.Date)
            .Sum(r => r.Quantity);
        if (Capacity < reservedSeats + reservation.Quantity)
            return null;

        reservation.IsAccepted = true;
        return ReservationsRepository.Create(reservation);
    }

    public int Capacity { get; }

    public IReservationsRepository ReservationsRepository { get; }
}

While there are other ways to do this (e.g. the way that you demonstrate), I think that the trade-offs are worse. At least, while it's taken some ten years to make the OOP community understand DI (and notions are still hazy to most), at least it's starting to become fairly well-known. Most OOP languages also naturally support DI, because polymorphism is already built in.

To be clear, I don't consider a free monad to be a viable alternative in C#, but at least it has one thing going for it: it communicates intent. When you see a method with an IReservationsProgram<> return type, you're explicitly being told that, yes, this is an abstract syntax tree (AST), but it's an AST of a very specific and limited grammar limited to three specific instructions.

On the other hand, when a method returns an Expression, as a code reader, this tells you nothing about what to expect. While it's an AST, its an AST of the entire C# grammar! It's like a Haskell function that returns IO. Anything could happen inside of that function.

So what advantages does it offer?

Is it free monad?

I don't think that it is. It may be isomorphic to a free monad, just like DI and free monads are isomorphic. Probably, all three approaches are isomorphic to each other.

A free monad is a monad that always arises from a functor. Which functor is being turned into a monad here?

If not (because of some mathematical definition) - does it matter from practical point of view? Does real Free Monad gives me something I don't have here?

No, and no. In most cases, in C#, DI is the simplest way to address issues of coupling.

Can we do something to make it real free monad?

Currently, I don't see how, but I haven't given it much thought, so I'm not at all sure about this...