Algebraic Effect Monad to separate pure and impure code I want to write my C# code in a way which makes effects (state, I/O, etc) explicit in the type signature. I have started to understand monads, and have some acquaintance with algebraic effects, though not deeply so. I have attempted to implement a monad for working with algebraic effects in C#. The purpose is to allow you to provide an impure function which is an interpreter over an algebraic representation of your effects at the time that you run the monad, but not before. In theory this allows you to write all of your code in a pure way, and even pass a pure function in for the effects for the sake of unit testing etc. The monad is intended to be generic with respect to what types you use to represent your effects, and it is built with a struct in order to not be nullable.

public struct Eff&lt;TOut, TIn, TReturn&gt;
{
    private readonly Func&lt;Func&lt;TIn, TOut&gt;,TReturn&gt; _wrappedParameter;

    private Eff(Func&lt;Func&lt;TIn, TOut&gt;, TReturn&gt; wrappedParameter)
    {
        _wrappedParameter = wrappedParameter;
    }

    public static Eff&lt;TOut,TIn,TReturn&gt; Return(TReturn obj)
    {
        return new Eff&lt;TOut,TIn,TReturn&gt;(_ =&gt; obj);
    }

    public static Eff&lt;TOut,TIn,TReturn&gt; Do(TIn input, Func&lt;TOut,TReturn&gt; continuation)
    {
        return new Eff&lt;TOut, TIn,TReturn&gt;(f =&gt; continuation(f(input)));
    }

    public TReturn Run(Func&lt;TIn, TOut&gt; f)
    {
        return _wrappedParameter(f);
    }

    public Eff&lt;TOut, TIn, TReturn2&gt; Map&lt;TReturn2&gt;(Func&lt;TReturn, TReturn2&gt; g)
    {
        var wrappedParameter = _wrappedParameter;
        return new Eff&lt;TOut, TIn, TReturn2&gt;(f =&gt; g(wrappedParameter(f)));
    }

    public Eff&lt;TOut,TIn,TReturn2&gt; Bind&lt;TReturn2&gt;(Func&lt;TReturn, Eff&lt;TOut,TIn,TReturn2&gt;&gt; continuation)
    {
        var wrappedParameter = _wrappedParameter;
        return new Eff&lt;TOut, TIn, TReturn2&gt;(f =&gt; continuation(wrappedParameter(f)).Run(f));
    }
}


There are several things that could be brought up here (he concepts are so new with me that I have named things poorly; I haven't yet figured out how it would look to have multiple effect types playing together in your program; etc), but there's one thing in particular I am concerned about, which is that I am nervous that if an entire program were written inside this monad, it would have the potential to overflow the .NET stack. This is where I am most interested in getting a review. I believe that if you implement a computation expression in F# it ends up executing in a trampoline monad to keep the stack from overflowing. I am particularly concerned about this in a somewhat resource-constrained environment, say an old Windows CE device running Compact Framework 3.5 (which is actually a target platform for me).
This is not a direct and full answer, but whereas I did not end up getting the opportunity I was hoping for to try this out on a C# project (yet), I did hit a perfect case for one in an F# project. I rewrote this monad in F#, implemented some concrete operations with it, and used it. I have it running in production with no problems so far, but it isn't using the constrained environment that I was describing in the question, so it hasn't given me full confidence in that yet.

After having done that, there are two main criticisms I have of the version above:


It's not very flexible. It really only allows you to have effects that conform to one type (Func&lt;TIn,TOut&gt;). Moreover it really only allows you to have one effect of this type.
The three generic types are overkill and not necessary. The alternative will be demonstrated below.


What I came up with was this generic effect monad:

module Effect

type Eff&lt;'E,'a&gt; =
     private EffReq of ('E -&gt; 'a)

let map (f : 'a -&gt; 'b) (EffReq p : Eff&lt;'E,'a&gt;) : Eff&lt;'E,'b&gt; =
    EffReq (f &lt;&lt; p)

// Argh F# blocks us from using unit, pure, or return...!
let init (x : 'a) : Eff&lt;'E,'a&gt; =
    EffReq (fun _ -&gt; x)

let run (io : 'E) (EffReq p : Eff&lt;'E,'a&gt;) : 'a =
    p io

let join (e : Eff&lt;'E,Eff&lt;'E,'a&gt;&gt;) : Eff&lt;'E,'a&gt; =
    EffReq (fun performEff -&gt; run performEff e |&gt; run performEff)

let bind (f : 'a -&gt; Eff&lt;'E,'b&gt;) (e : Eff&lt;'E,'a&gt;) : Eff&lt;'E,'b&gt; =
    join &lt;| map f e

let request = EffReq


Specific operations can be implemented using request, e.g.:

module FileIO

open Effect

type FileIO = {
    ReadAllText : string -&gt; string
}

type IOEff&lt;'a&gt; = Eff&lt;FileIO,'a&gt;

let readAllText (path : string) : IOEff&lt;string&gt; =
    Effect.request (fun io -&gt; io.ReadAllText path)


I know this is in a different language than the original question but the conceptual aspect is the most important part.

I don't consider this implementation fully battle-hardened but it should allow me to evolve the C# version in a good direction.

Note that this is really a Reader monad: it reads from an impure environment (and because that environment is impure, technically it is able to write to it as well).