8

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); 
        }
    }
}
anony mous
  • 83
  • 6
  • So in order to wrap a value in a Monad you first have to create one? Does that really make sense? – juharr Jan 26 '20 at 19:05
  • updated the code with a complete running program, what is the problem exactly in creating the wrapper then passing in the value? why would it not make sense? how is it different than "var x = new List(); x.Add(5);" – anony mous Jan 26 '20 at 19:16
  • Well before you ended up creating two Monads every time you wanted one. Now you have a mutable Monad. – juharr Jan 26 '20 at 19:19
  • ok, updated again :) now it's immutable and honestly i don't see any need for Wrap when we can just use the constructor, so now we create immutable Monads. so where's the problem? – anony mous Jan 26 '20 at 19:52
  • 2
    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 Jan 27 '20 at 03:16
  • 1
    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 Jan 27 '20 at 03:28
  • so it is just "we don't enforce constructor signatures in interfaces". why don't they just say that! :) this can be a language feature request, no need for type classes. but really even functional language like Haskell with type classes can't enforce associative composition or neutral identity, so Monad laws can't really be enforced in any language, there's always a part left as "implementation law". the core of Monad is bind, current interface works and "wrap" can be our "implementation law". so no problem! :) – anony mous Jan 27 '20 at 06:39
  • 2
    "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 Jan 27 '20 at 23:25
  • 1
    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 Jan 28 '20 at 01:00

1 Answers1

14

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<U> returns Wrong<U>, not IMonad<U>! 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<U>, not IMonad<U>. 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<U> must take a function that returns some Wrong<U> and must itself return Wrong<U> 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.

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
  • 3
    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. – anony mous Jan 28 '20 at 05:54
  • @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](https://github.com/dotnet/csharplang/blob/master/proposals/csharp-8.0/default-interface-methods.md#modifiers-in-interfaces) 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? – Justin Blakley Jan 31 '20 at 18:27
  • 1
    @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` implements contract `M` then `C` has a method that takes a `Func>` and returns `C>` We have no way to say that. – Eric Lippert Jan 31 '20 at 18:30
  • @JustinBlakley: The value added by allowing static members in interfaces is it gives us an attack on the problem of how to make, say, a generic `Max` method. We could define an interface for "total order" where we require that the type have `< > <= >= == !=` operators. I suspect that such a system would probably let us define the operations on a *monoid* but not a *monad*. :) – Eric Lippert Jan 31 '20 at 18:33
  • 1
    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 instead of IMonad) will be legal. – hcerim Jun 29 '20 at 09:50
  • 1
    @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. – Eric Lippert Jun 30 '20 at 23:57