Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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); 
        }
    }
}
like image 772
anony mous Avatar asked Jan 26 '20 18:01

anony mous


People also ask

Why is it called the C?

After language 'B', Dennis Ritchie came up with another language which was based upon 'B'. As in alphabets B is followed by C and hence he called this language as 'C'.

What is C is used for?

C programming language is a machine-independent programming language that is mainly used to create many types of applications and operating systems such as Windows, and other complicated programs such as the Oracle database, Git, Python interpreter, and games and is considered a programming foundation in the process of ...

Why C came into existence?

C was originally developed for UNIX operating system to beat the issues of previous languages such as B, BCPL, etc. The UNIX operating system development started in the year 1969, and its code was rewritten in C in the year 1972.

What are labels in C?

C. In C a label identifies a statement in the code. A single statement can have multiple labels. Labels just indicate locations in the code and reaching a label has no effect on the actual execution.


1 Answers

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.

like image 80
Eric Lippert Avatar answered Oct 12 '22 02:10

Eric Lippert