Monads in C# -- why Bind implementations require passed function to return a monad?

Question

Most examples of monads I saw in C# are written somewhat like that:

public static Identity<B> Bind<A, B>(this Identity<A> a, Func<A, Identity<B>> func) {
    return func(a.Value);
}

For example, see http://mikehadlow.blogspot.com/2011/01/monads-in-c-3-creating-our-first-monad.html.

The question is, what is the point of requiring func to return an Identity<B> ? If I use the following definition:

public interface IValue<A> {
    public IValue<B> Bind<B>(Func<A, B> func)
}

then I can actually use same func for for Lazy<T>, Task<T>, Maybe<T> etc without actually depending on actual type implementing IValue.

Is there something important I am missing here?

Answer 1

First off, consider the notion of composition. We can express composition as an operation on delegates easily:

public static Func<T, V> Compose<T, U, V>(this Func<U, V> f, Func<T, U> g)
{
    return x => f(g(x));
}

So if I have a function g which is (int x) => x.ToString() and a function f which is (string s) => s.Length then I can make a composed function h which is (int x) => x.ToString().Length by calling f.Compose(g).

That should be clear.

Now suppose I have a function g from T to Monad<U> and a function f from U to Monad<V>. I wish to write a method that composes these two functions that return monads into a function that takes a T and returns a Monad<V>. So I try to write that:

public static Func<T, Monad<V>> Compose<T, U, V>(this Func<U, Monad<V>> f, Func<T, Monad<U>> g)
{
    return x => f(g(x));
}

Doesn't work. g returns a Monad<U> but f takes a U. I have a way to "wrap" a U into a Monad<U> but I don't have a way to "unwrap" one.

However, if I have a method

public static Monad<V> Bind<U, V>(this Monad<U> m, Func<U, Monad<V>> k)
{ whatever }

then I can write a method that composes two methods that both return monads:

public static Func<T, Monad<V>> Compose<T, U, V>(this Func<U, Monad<V>> f, Func<T, Monad<U>> g)
{
    return x => Bind(g(x), f);
}

That's why Bind takes a func from T to Monad<U> -- because the whole point of the thing is to be able to take a function g from T to Monad<U> and a function f from U to Monad<V> and compose them into a function h from T to Monad<V>.

If you want to take a function g from T to U and a function f from U to Monad<V> then you don't need Bind in the first place. Just compose the functions normally to get a method from T to Monad<V>! The whole purpose of Bind is to solve this problem; if you wave that problem away then you don't need Bind in the first place.

UPDATE:

In most cases I want to compose function g from T to Monad<U> and function f from U to V.

And I presume you then want to compose that into a function from T to V. But you can't guarantee that such an operation is defined! For example, take the "Maybe monad" as the monad, which is expressed in C# as T?. Suppose you have g as (int x)=>(double?)null and you have a function f that is (double y)=>(decimal)y. How are you supposed to compose f and g into a method that takes an int and returns the non-nullable decimal type? There is no "unwrapping" that unwraps the nullable double into a double value that f can take!

You can use Bind to compose f and g into a method that takes an int and returns a nullable decimal:

public static Func<T, Monad<V>> Compose<T, U, V>(this Func<U, V> f, Func<T, Monad<U>> g)
{
    return x => Bind(g(x), x=>Unit(f(x)));
}

where Unit is a function that takes a V and returns a Monad<V>.

But there simply is no composition of f and g if g returns a monad and f doesn't return the monad -- there is no guarantee that there is a way to go back from the instance of the monad to an "unwrapped" type. Maybe in the case of some monads there always is -- like Lazy<T>. Or maybe there sometimes is, like with the "maybe" monad. There often is a way to do it, but there is not a requirement that you can do so.

Incidentally, notice how we just used "Bind" as a Swiss Army Knife to make a new kind of composition. Bind can make any operation! For example, suppose we have the Bind operation on the sequence monad, which we call "SelectMany" on the IEnumerable<T> type in C#:

static IEnumerable<V> SelectMany<U, V>(this IEnumerable<U> sequence, Func<U, IEnumerable<V>> f)
{
    foreach(U u in sequence)
        foreach(V v in f(u))
            yield return v;
}

You might also have an operator on sequences:

static IEnumerable<A> Where<A>(this IEnumerable<A> sequence, Func<A, bool> predicate)
{
    foreach(A item in sequence)
        if (predicate(item)) 
            yield return item;
}

Do you really need to write that code inside Where? No! You can instead build it entirely out of "Bind/SelectMany":

static IEnumerable<A> Where<A>(this IEnumerable<A> sequence, Func<A, bool> predicate)
{
    return sequence.SelectMany((A a)=>predicate(a) ? new A[] { a } : new A[] { } );  
}

Efficient? No. But there is nothing that Bind/SelectMany cannot do. If you really wanted to you could build all of the LINQ sequence operators out of nothing but SelectMany.