Higher-Kinded Types in Algebraic Free Monads with language-ext?

[kikkoi]

I can't find examples of how the free monad works with HKT in C#. I am trying to learn about algebraic effects. Maybe it would be a good idea to add an example test of algebraic free monads, similar to this one https://github.com/tonivade/purefun/blob/master/free/src/test/java/com/github/tonivade/purefun/free/FreeAlgTest.java?

[louthy]

They're not written up yet because I haven't done the full release. But the documentation is coming soon as well as a blog article on my blog. The API for the Free monad is also quite minimal right now, it may well expand to make it easier to use. However, it's not really high up my list right now.

But, here's a quick example...

Obviously, the point of free monads is to give you a monad for free from a Functor and so first I'll define an ADT and make a functor for it.

public abstract record Op<A> : K<Op, A>;
public record ReadLinesOp<A>(string Path, Func<Seq<string>, A> Next): Op<A>;
public record WriteLinesOp<A>(string Path, Seq<string> Lines, Func<Unit, A> Next) : Op<A>;

The ADT is a simple union of two operations: ReadLinesOp and WriteLinesOp. The members should be fairly obvious, apart from Next, which is what we use to map the result of the operation to another value (by default A).

Any operations that terminate the computation (like an error case) do not need a Next.

Now I'll make the Functor:

public partial class Op : Functor<Op>
{
    public static K<Op, B> Map<A, B>(Func<A, B> f, K<Op, A> ma) =>
        ma switch
        {
            ReadLinesOp<A> (var path, var next)             => new ReadLinesOp<B>(path, x => f(next(x))),
            WriteLinesOp<A> (var path, var lines, var next) => new WriteLinesOp<B>(path, lines, x => f(next(x)))
        };
}

In a future language-ext this can be auto-generated (once I have written the new SourceGen library).

Notice how the f function is used to map the next. This is the key to chaining the operations.

With those basics we can now lift the ADT into the Free monad:

public partial class Op
{
    public static Free<Op, Seq<string>> readLines(string path) =>
        Free.lift(new ReadLinesOp<Seq<string>>(path, identity));

    public static Free<Op, Unit> writeLines(string path, Seq<string> lines) =>
        Free.lift(new WriteLinesOp<Unit>(path, lines, identity));
}

Note the use of identity

Now they're usable in LINQ (they're a monad):

var repr = from lines in Op.readLines("c:\\temp\\test.txt")
           from _     in Op.writeLines("c:\\temp\\test2.txt", lines)
           select unit;

repr is a pure data representation of the operations you wish to perform, but it doesn't perform them. For that we need an interpreter. The interpreter is the place for your bespoke handling of the operations, so it's very much up to you how to handle each case of the ADT:

static IO<A> Interpret<A>(K<Free<Op>, A> ma) =>
    ma switch
    {
        Pure<Op, A>(var value) => 
            IO.Pure(value),
        
        Bind<Op, A>(var bind) =>
            bind switch
            {
                ReadLinesOp<Free<Op, A>> (var path, var next) => 
                    ReadLines(path).Map(next).Bind(Interpret),
                
                WriteLinesOp<Free<Op, A>> (var path, var lines, var next) => 
                    WriteLines(path, lines).Map(next).Bind(Interpret)
            }
    };

There are two cases for a Free monad:

• Pure - The terminating case -- this ends the interpreter and returns a value
• Bind - This knows how to chain the operations, 'next' is always Func<?, Free<Op, A>> (where ? is the return type of the operation).

So, you pattern match on the operations run them for real, map the result, and then recursively call Interpret.

Note, this example interpreter uses the IO monad but the whole point is that you can use any monad you like (or no monad at all if you want to bake down to a concrete value).

These are the IO implementations of ReadLines and WriteLines:

static IO<Seq<string>> ReadLines(string path) =>
    IO.liftAsync(() => File.ReadAllLinesAsync(path)).Map(toSeq);

static IO<Unit> WriteLines(string path, Seq<string> lines) =>
    IO.liftAsync(async () =>
                 {
                     await File.WriteAllLinesAsync(path, lines);
                     return unit;
                 });

So, with all that in place you can now run the interpreter with the repr and then run the IO to do the actions for real:

var repr = from lines in Op.readLines("c:\\temp\\test.txt")
           from _     in Op.writeLines("c:\\temp\\test2.txt", lines)
           select unit;

var comp = Interpret(repr);
comp.Run();

btw, it also possible to run the interpreter as a while loop and not risk stack issues with the recursive function

I hope that helps 👍