How does the Maybe monad act as a short circuit?

Question

I'm trying to get a deeper understanding of Monads. Therefore I started digging a little into the Maybe Monad.

There is one thing that I just don't seem to get right. Read this:

"So the Maybe Bind acts a short circuit. In any chain of operations, if any one of them returns Nothing, the evaluation will cease and Nothing will be returned from the entire chain."

From: http://mikehadlow.blogspot.com/2011/01/monads-in-c-5-maybe.html

And this:

"For the Maybe<T> type, binding is implemented according to as simple rule: if chain returns an empty value at some point, further steps in the chain are ignored and an empty value is returend instead"

From: "Functional Programming in C#" http://www.amazon.com/Functional-Programming-Techniques-Projects-Programmer/dp/0470744588/

Ok, let's look at the code. Here is my Maybe Monad:

public class Maybe<T>
{
    public static readonly Maybe<T> Empty = new Maybe<T>(); 

    public Maybe(T value)
    {
        Value = value;
    }

    private Maybe()
    {
    }

    public bool HasValue()
    {
        return !EqualityComparer<T>.Default.Equals(Value, default(T));
    }

    public T Value { get; private set; }

    public Maybe<R> Bind<R>(Func<T, Maybe<R>> apply)
    {
        return HasValue() ? apply(Value) : Maybe<R>.Empty;
    }
}

public static class MaybeExtensions
{
    public static Maybe<T> ToMaybe<T>(this T value)
    {
        return new Maybe<T>(value);
    }
}

And here is my example code using the monad:

class Program
{
    static void Main(string[] args)
    {
        var node = new Node("1", new Node("2", new Node("3", new Node("4", null))));

        var childNode = node.ChildNode
            .ToMaybe()
            .Bind(x => x.ChildNode.ToMaybe())
            .Bind(x => x.ChildNode.ToMaybe())
            .Bind(x => x.ChildNode.ToMaybe())
            .Bind(x => x.ChildNode.ToMaybe())
            .Bind(x => x.ChildNode.ToMaybe());

        Console.WriteLine(childNode.HasValue() ? childNode.Value.Value : "");

        Console.ReadLine();
    }
}

public class Node
{
    public Node(string value, Node childNode)
    {
        Value = value;
        ChildNode = childNode;
    }

    public string Value { get; set; }
    public Node ChildNode { get; private set; }
}

It's clear to see that we are trying to dig deeper into the node tree than possible. However, I fail to see how it is acting according to the quotes I mentioned. I mean, of course I have factored out the null checks and the example works. However, it doesn't break the chain early. If you set breakpoints you will see that every Bind() operation will be used thus without a value for the last operations. But it means, if I dig 20 level deep and it actually only goes down 3 levels I still will check 20 levels or am I wrong?

Compare this to the non-monad approach:

        if (node.ChildNode != null
            && node.ChildNode.ChildNode != null
            && node.ChildNode.ChildNode.ChildNode != null)
        {
            Console.WriteLine(node.ChildNode.ChildNode.ChildNode.Value);
        }

Isn't this actually what should be called a short circuit? Because in this case the if really breaks at the level where the first value is null.

Can anybody help me to get this clear?

UPDATE

As Patrik pointed out, yes it is true each bind will be invoked even if we only have 3 levels and try to go 20 levels deep. However, the actual expression provided to the Bind() call won't be evaluated. We can edit the example to make the effect clear:

        var childNode = node.ChildNode
            .ToMaybe()
            .Bind(x =>
                      {
                          Console.WriteLine("We will see this");
                          return x.ChildNode.ToMaybe();
                      })
            .Bind(x => x.ChildNode.ToMaybe())
            .Bind(x => x.ChildNode.ToMaybe())
            .Bind(x => x.ChildNode.ToMaybe())
            .Bind(x =>
                      {
                          Console.WriteLine("We won't see this");
                          return x.ChildNode.ToMaybe();
                      });

Answer 1

I have an implementation of the maybe monad in c# that differs a little from yours, first of all it's not tied to null checks, I believe my implementation more closesly resembles what happens in a standard maybe implementation in for example Haskel.

My implementation:

public abstract class Maybe<T>
{
    public static readonly Maybe<T> Nothing = new NothingMaybe();

    public static Maybe<T> Just(T value)
    {
        return new JustMaybe(value);
    }

    public abstract Maybe<T2> Bind<T2>(Func<T, Maybe<T2>> binder);

    private class JustMaybe
        : Maybe<T>
    {
        readonly T value;

        public JustMaybe(T value)
        {
            this.value = value;
        }

        public override Maybe<T2> Bind<T2>(Func<T, Maybe<T2>> binder)
        {
            return binder(this.value);
        }
    }

    private class NothingMaybe
        : Maybe<T>
    {
        public override Maybe<T2> Bind<T2>(Func<T, Maybe<T2>> binder)
        {
            return Maybe<T2>.Nothing;
        }
    }
}

As you see here the bind function of the NothingMaybe just returns a new nothing so passed in binder expression is never evaluated. It's short circuiting in the sense that no more binder expressions will be evaluated once you got into the "nothing state", however the Bind-function itself will be invoked for each monad in the chain.

This implementation of maybe could be used for any type of "uncertain operation", for example a null check or checking for an empty string, this way all those different types of operations can be chained together:

public static class Maybe
{
    public static Maybe<T> NotNull<T>(T value) where T : class
    {
        return value != null ? Maybe<T>.Just(value) : Maybe<T>.Nothing;
    }

    public static Maybe<string> NotEmpty(string value)
    {
        return value.Length != 0 ? Maybe<string>.Just(value) : Maybe<string>.Nothing;
    }


}

string foo = "whatever";
Maybe.NotNull(foo).Bind(x => Maybe.NotEmpty(x)).Bind(x => { Console.WriteLine(x); return Maybe<string>.Just(x); });

This would print "whatever" to the console, however if the value was null or empty it would do nothing.

Answer 2

As I understand it, all Bind methods will be invoked, but the provided expressions will be evaluated only if the previous one returns a value. This means that Bind methods that are invoked after one that returns null (or more correctly: default(T)) will be very cheap.

Answer 3

We can do this more cunningly.

Write interface derived from IEnumerable

public interface IOptional<T>: IEnumerable<T> {}

This will save compatibility with LINQ methods

public class Maybe<T>: IOptional<T>
{
    private readonly IEnumerable<T> _element;
    public Maybe(T element)
        : this(new T[1] { element })
    {}
    public Maybe()
        : this(new T[0])
    {}
    private Maybe(T[] element)
    {
        _element = element;
    }
    public IEnumerator<T> GetEnumerator()
    {
        return _element.GetEnumerator();
    }
    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

After this we can use full power of LINQ and do like this

var node = new Node("1", new Node("2", new Node("3", new Node("4", null))));

var childNode =
    new Some<Node>(node.ChildNode)
        .SelectMany(n => new Maybe<Node>(n.ChildNode))
        .SelectMany(n => new Maybe<Node>(n.ChildNode))
        .SelectMany(n => new Maybe<Node>(n.ChildNode))
        .SelectMany(n => new Maybe<Node>(n.ChildNode))
        .SelectMany(n => new Maybe<Node>(n.ChildNode));

Console.WriteLine(childNode.Any() ? childNode.First().Value : "");