Here is the C# Monad, where is the problem?

Question

Reading a Previous SO Question I was confused to find Eric Lippert saying that an interface cannot be defined in C# for all Monads, using an implementation as below:

typeInterface Monad<MonadType<A>> { static MonadType<A> Return(A a); static MonadType<B> Bind<B>(MonadType<A> x, Func<A, MonadType<B>> f); }

My problem is all the problems listed in the question seem to have easy solutions:

no "higher kinded types" => use parent interfaces
no static method in interface. => why use static?! just use instance methods

Monad is a pattern allowing chaining of operations on wrapped types it seems easy to define a C# interface for all Monads allowing us to write a generic class for all monads Where's the problem?

using System; using System.Linq; public class Program { public static void Main() {//it works, where's the problem? new SequenceMonad<int>(5) .Bind(x => new SequenceMonad<float>(x + 7F)) .Bind(x => new SequenceMonad<double>(x + 5D)) ; } interface IMonad<T>{ IMonad<T> Wrap(T a); IMonad<U> Bind<U>(Func<T, IMonad<U>> map); T UnWrap();//if we can wrap we should be able to unwrap } class GenericClassForAllMonads<T> {//example writing logic for all monads IMonad<U> DoStuff<U>(IMonad<T> input, Func<T, IMonad<U>> map) { return map(input.UnWrap()); } } class SequenceMonad<T> : IMonad<T> where T:new() {//specific monad implementation readonly T[] items;//immutable public SequenceMonad(T a) { Console.WriteLine("wrapped:"+a); items = new[] { a }; } public IMonad<B> Bind<B>(Func<T, IMonad<B>> map) { return map(UnWrap()); } public T UnWrap() { return items == null? default(T) : items.FirstOrDefault(); } public IMonad<T> Wrap(T a) { Console.WriteLine("wrapped:"+a); return new SequenceMonad<T>(a); } } }

So in order to wrap a value in a Monad you first have to create one? Does that really make sense? — juharr
– juharr, Commented Jan 26, 2020 at 19:05
Now the problem is that the interface can not guarantee that the class has a constructor that will wrap the value. Eric never said you could not write monads in C#, just that you cannot create an interface that will guarantee that a class that implements it satisfies the requirements. — juharr
– juharr, Commented Jan 27, 2020 at 3:16
More precisely the requirement is that you pass a value in and you get a monad that wraps that value out. That can be a constructor or a static method, but neither can be defined in an interface. That leaves instance methods, that either create a new monad or mutate an existing one. But understand that in a functional sense that is something that takes a monad and a value and returns a monad wrapping the value (but the requirement was to only pass in the value). — juharr
– juharr, Commented Jan 27, 2020 at 3:28
"If we can wrap then we should be able to unwrap" is not a monad law. "We can unwrap" is a comonad law, and "there is often an unwrap" is a fact about commonly used monads, not a requirement. — Eric Lippert
– Eric Lippert, Commented Jan 27, 2020 at 23:25
I note that your sequence monad does not implement the sequence monad. The characteristic behaviour of the sequence monad is that the bind operation's behaviour is map-and-concatenate. That is, if we have a sequence of ints s equal to {1, 2, 3}, then s.Bind(x => Repeat(x, 2)) is the sequence {1,1,2,2,3,3}, for example. Your implementation does not have any concatenation logic in it. — Eric Lippert
– Eric Lippert, Commented Jan 28, 2020 at 1:00

Eric Lippert · Accepted Answer · 2020-01-28 08:07:15Z

it seems easy to define a C# interface for all monads. Where's the problem?

Your proposal is:

interface IMonad<T> { IMonad<T> Wrap(T a); IMonad<U> Bind<U>(Func<T, IMonad<U>> map); }

I've omitted the "unwrap" because the existence of an extraction operation is not a requirement of a monad. (Many monads have this operation, but not all do. If you require an extract operation, you are probably actually using a comonad.)

You ask why this is wrong. This is wrong in several ways.

The first way it is wrong is: there is no way to create a new instance of the monad via Wrap without already having an instance! You have a chicken-and-egg problem here.

The "wrap" or "unit" or "return" operation -- whatever you want to call it -- is logically a static factory; it's how you make a new instance of the monad. It's not an operation on an instance. It is a requirement of a static method on a type. (Or, the requirement that a type implement a particular constructor, which is effectively the same thing. Either way, it is not supported in C# at this time.)

Let's eliminate Wrap from consideration in the next point. Why is Bind wrong?

The second way it is wrong is you do not have the right restrictions in place. Your interface says that a monad of T is a thing that provides a bind operation that returns a monad of U. But that is not restrictive enough! Suppose we have a monad Maybe<T> : IMonad<T>. Now suppose we have this implementation:

class Wrong<T> : IMonad<T> { public IMonad<U> Bind<U>(Func<T, IMonad<U>> map) { return new Maybe<U>(); } }

That satisfies the contract, which tells us that the contract is not the real monad contract. The monad contract should be that Wrong<T>.Bind returns Wrong, not IMonad! But we have no way of expressing in C# "bind returns an instance of the class which defines bind".

Similarly it is wrong because the Func that is provided by the caller must be required to return Wrong, not IMonad. Suppose we have a third monad, say, State<T>. We could have

Wrong<Frog> w = whatever; var result = w.Bind<Newspaper>(t=>new State<Newspaper>());

And now this is all messed up. Wrong<T>.Bind must take a function that returns some Wrong and must itself return Wrong of the same type, but this interface allows us to have a bind that takes a function that returns State<Newspaper> but the bind returns Maybe<Newspaper>. This is a total violation of the monad pattern. You have not captured the monad pattern in your interface.

The C# type system is not strong enough to express the constraint "when the method is implemented it must return an instance of the class that did the implementation". If C# had a "this_type" compile-time annotation then Bind could be expressed as an interface, but C# does not have that annotation.

Wow! Can't believe you've answered me yourself :) Thank You! now I finally get it. Thanks a lot for taking time to explain in details.
@EricLippert Does the C# proposal spec for default implementations on interfaces change this at all? I understand that part of the spec is to include static members on interfaces. Draft Proposal By "change this at all" I specifically mean, does it solve the chicken and egg problem you described by providing a static factory method on the IMonad type itself?
@JustinBlakley: It solves the problem of how to make a contract that says "this type has a particular static member", but it doesn't solve the problem in the last paragraph of the answer, and that's the tricky bit. What we really need to represent the monad pattern is "if type C<T> implements contract M<T> then C<T> has a method that takes a Func<T, C> and returns C> We have no way to say that.
Apparently they are making efforts in this direction. It is useful to mention that this will change with the introduction of covariant returns in C# 9.0 so returning a more specific type (Wrong<T> instead of IMonad<T>) will be legal.
@HarunCerim: I am not quite sure what you are getting at here; how does return type covariance help here? The monad higher-kinded type describes a restriction that must be imposed by the type system for a type to be a legal monad; return type covariance by contrast removes a restriction from the type system. Can you explain further, because I think I am missing something.

Collectives™ on Stack Overflow

Here is the C# Monad, where is the problem?

1 Answer 1

6 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Linked

Related