Struct implementation of immutable Maybe<T> monad

Question

I have developed the following implementation of an immutable struct Maybe<T> monad for use in my game project; as an practical exposition on monads to present to my local User Group; and an a demonstration of the use of Static Code Analysis for verification in conjunction with TDD. I am interested in any and all comments on coding style, and completeness and correctness of the implementation.

The base Maybe<T> class:

/// <summary>An immutable value-type Maybe&lt;T> monad.</summary>
/// <typeparam name="T">The base type, which can be either a class or struct type,
/// and will have the Equality definition track the default for the base-type:
/// Value-equality for structs and string, reference equality for other classes.
/// </typeparam>
/// <remarks
/// >Being a value-type reduces memory pressure on <see cref="System.GC"/>.
/// 
/// Equality tracks the base type (struct or class), with the further proviseo
/// that two instances can only be equal when <see cref="HasValue"/> is true
/// for both instances.
/// </remarks>
public struct Maybe<T> : IEquatable<Maybe<T>> {
  #region static support for IEquatable<Maybe<T>>
  static Maybe() {
    _valueIsStruct = typeof(ValueType).IsAssignableFrom(typeof(T));
    _equals = ValueIsStruct ? (Func<T,T,bool>)ValEquals 
                            : (Func<T,T,bool>)RefEquals;
    _nothing = new Maybe<T>();
  }
  static bool  ValueIsStruct { [Pure]get {return _valueIsStruct;} } static bool _valueIsStruct;
  static readonly Func<T,T,bool> _equals;
  [Pure]private static bool ValEquals(T lhs, T rhs) { return lhs.Equals(rhs); }
  [Pure]private static bool RefEquals(T lhs, T rhs) {
    return typeof(string).IsAssignableFrom(typeof(T)) ? lhs.Equals(rhs)
                                                      : object.ReferenceEquals(lhs, rhs);
  }
  #endregion

  public static Maybe<T> Nothing {
    [Pure]get { Contract.Ensures( ! Contract.Result<Maybe<T>>().HasValue);

                Contract.Assume( ! _nothing.HasValue ); 
                return _nothing;
    }
  } static Maybe<T> _nothing;

  ///<summary>Create a new Maybe&lt;T>.</summary>
  public Maybe(T value) : this() {
    value.ContractedNotNull("value");

    _value    = value;
    _hasValue = true;
  }

  ///<summary>The monadic Bind operation from type T to type Maybe&lt;TResult>.</summary>
  [Pure]public Maybe<TResult> Bind<TResult>(Func<T, Maybe<TResult>> selector) {
    selector.ContractedNotNull("selector");

    return ! HasValue  ?  Maybe<TResult>.Nothing  :  selector(_value);
  }

  ///<summary>Extract value of the Maybe&lt;T>, substituting <paramref name="defaultValue"/> as needed.</summary>
  [Pure]public T Extract(T defaultValue) {
    defaultValue.ContractedNotNull("defaultValue");
    Contract.Ensures(Contract.Result<T>() != null);

    return ! HasValue  ?  defaultValue  :  _value;
  }

  ///<summary>Wraps a T as a Maybe&lt;T>.</summary>
  [Pure]public static implicit operator Maybe<T>(T value) {
    Contract.Assume( ValueIsStruct.Implies(value != null) );
    return ValueIsStruct ? new Maybe<T>(value)
         : value == null ? Maybe<T>.Nothing
                         : new Maybe<T>(value);
  }

  ///<summary>Returns whether this Maybe&lt;T> has a value.</summary>
  public bool HasValue { [Pure]get {                          return _hasValue;} } readonly bool _hasValue;
  ///<summary>If this Maybe&lt;T> has a value, returns it.</summary>
  internal  T Value    { [Pure]get {Contract.Requires(HasValue); return _value;} } readonly    T _value;

  /// <summary>The invariants enforced by this struct type.</summary>
  [SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")]
  [SuppressMessage("Microsoft.Performance", "CA1822:MarkMembersAsStatic")]
  [ContractInvariantMethod]
  [Pure]private void ObjectInvariant() {
    Contract.Invariant( HasValue  ==  _hasValue );
    Contract.Invariant( HasValue.Implies(_value != null) );
    Contract.Invariant( ValueIsStruct.Implies(_value != null) );
  }

  #region Value Equality with IEquatable<T> and "excluded middle" present w/ either side has no value.
  /// <inheritdoc/>
  [Pure]public override bool Equals(object obj) { 
    var other = obj as Maybe<T>?;
    return other.HasValue  &&  other.Equals(obj);
  }

  /// <summary>Tests value-equality, returning <b>false</b> if either value doesn't exist.</summary>
  [Pure]public bool Equals(Maybe<T> other) {
    return this.HasValue  &&  other.HasValue  &&  _equals(this._value,other._value);
  }
  /// <summary>Tests value-inequality, returning <b>false</b> if either value doesn't exist.</summary>
  [Pure]public bool NotEquals(Maybe<T> other) {
    return !this.HasValue  ||  !other.HasValue  ||  _equals(this._value,other._value);
  }

  /// <inheritdoc/>
  [Pure]public override int GetHashCode() { return Bind(v=>v.GetHashCode().ToMaybe()).Extract(0); }

  /// <inheritdoc/>
  [Pure]public override string ToString() {
    Contract.Ensures(Contract.Result<string>() != null);
    return Bind<string>(v => v.ToString()).Extract("");
  }

  /// <summary>Tests value-equality, returning <b>false</b> if either value doesn't exist.</summary>
  [Pure]public static bool operator == (Maybe<T> lhs, Maybe<T> rhs) { return lhs.Equals(rhs); }

  /// <summary>Tests value-inequality, returning <b>false</b> if either value doesn't exist..</summary>
  [Pure]public static bool operator != (Maybe<T> lhs, Maybe<T> rhs) { return ! lhs.NotEquals(rhs); }
  #endregion
}

The LINQ-supporting extensions:

/// <summary>Extension methods for Maybe&lt;T> to support LINQ "Comprehension" and "Fluent" syntax.</summary>
/// <remarks>
/// Unoptimized implementations of both Select() and SelectMany() have been retained
/// as comments for documentation purposes, to emphasize the evolution to the
/// optimized forms currently in use.
/// 
/// The intent is also to use this class as a tutorial for the exposition on
/// generating the ptimized forms from the standard Monad implementations.
/// </remarks>
public static partial class MaybeExtensions {
  /// <summary>Amplifies a T to a Maybe&lt;T>.</summary>
  /// <remarks>The monad <i>unit</i> function.</remarks>
  [Pure]public static Maybe<T> ToMaybe<T>(this T @this) { return @this; }

  /// <summary>LINQ-compatible implementation of Bind/Map as Select.</summary>
  [Pure]public static Maybe<TResult> Select<T,TResult>(
    this Maybe<T> @this,
    Func<T,TResult> projector
  ) {
    projector.ContractedNotNull("projector");

    return ! @this.HasValue ? Maybe<TResult>.Nothing    // Optimized implementation
                            : projector(@this.Value);

    //return @this.Bind(v => projector(v).ToMaybe());   // Always available from Bind()
  }

  /// <summary>LINQ-compatible implementation of Bind as SelectMany.</summary>
  [Pure]public static Maybe<TResult> SelectMany<T, TResult>(
    this Maybe<T> @this,
    Func<T, Maybe<TResult>> selector
  ) {
    selector.ContractedNotNull("selector");

    return @this.Bind(selector);
  }

  /// <summary>LINQ-compatible implementation of Bind/FlatMap as SelectMany.</summary>
  [Pure]public static Maybe<TResult> SelectMany<T, TSelection, TResult>(
    this Maybe<T> @this,
    Func<T, Maybe<TSelection>> selector,
    Func<T,TSelection,TResult> projector
  ) {
    selector.ContractedNotNull("selector");
    projector.ContractedNotNull("projector");

    return ! @this.HasValue                         // Optimized implementation
        ? Maybe<TResult>.Nothing
        : selector(@this.Value).Select(e => projector(@this.Value,e));

    //return @this.Bind(          aval =>           // Always available from Bind()
    //       selector(aval).Bind( bval =>
    //       projector(aval,bval).ToMaybe() ) );

    //return @this.Bind(           aval =>          // Available from Bind() & Select()
    //       selector(aval).Select(bval =>
    //       projector(aval,bval) ) );
  }
}

Finally, some CodeContract extension to support the static analysis, normally run with RUNTIME_NULL_CHECKS not defined:

/// <summary>Extension methods to enhance Code Contracts and integration with Code Analysis.</summary>
public static class ContractExtensions {
#if RUNTIME_NULL_CHECKS
  /// <summary>Throws <c>ArgumentNullException{name}</c> if <c>value</c> is null.</summary>
  /// <param name="value">Value to be tested.</param>
  /// <param name="name">Name of the parameter being tested, for use in the exception thrown.</param>
  [ContractArgumentValidator]  // Requires Assemble Mode = Custom Parameter Validation
  public static void ContractedNotNull<T>([ValidatedNotNull]this T value, string name) where T : class {
    if (value == null) throw new ArgumentNullException(name);
    Contract.EndContractBlock();
  }
#else
  /// <summary>Throws <c>ContractException{name}</c> if <c>value</c> is null.</summary>
  /// <param name="value">Value to be tested.</param>
  /// <param name="name">Name of the parameter being tested, for use in the exception thrown.</param>
  [SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "value")]
  [SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "name")]
  [ContractAbbreviator] // Requires Assemble Mode = Standard Contract Requires
  [Pure]public static void ContractedNotNull<T>([ValidatedNotNull]this T value, string name) {
    Contract.Requires(value != null, name);
  }
#endif

  /// <summary>Decorator for an object which is to have it's object invariants assumed.</summary>
  [SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "t")]
  [Pure]internal static void AssumeInvariant<T>(this T t) { }

  /// <summary>Asserts the 'truth' of the logical implication <paramref name="condition"/> => <paramref name="contract"/>.</summary>
  [Pure]public static bool Implies(this bool condition, bool contract) {
    Contract.Ensures((! condition || contract)  ==  Contract.Result<bool>() );
    return ! condition || contract;
  }

  /// <summary>Returns true exactly if lower &lt;= value &lt; lower+height</summary>
  /// <param name="value">Vlaue being tested.</param>
  /// <param name="lower">Inclusive lower bound for the range.</param>
  /// <param name="height">Height of the range.</param>
  [Pure]public static bool InRange(this int value, int lower, int height) {
    Contract.Ensures( (lower <= value && value < lower+height)  ==  Contract.Result<bool>() );
    return lower <= value && value < lower+height;
  }
}

/// <summary>Decorator for an incoming parameter that is contractually enforced as NotNull.</summary>
[AttributeUsage(AttributeTargets.Parameter, AllowMultiple = false)]
public sealed class ValidatedNotNullAttribute : global::System.Attribute {}

This code and it's unit-tests and demo program runs clean through static Code Analysis with these settings:

Update - Corrected an Error in != operator

Contrary to the spec., I noticed that ternary logic was not being properly implemented. To correct this the method NotEquals() was added, with the operator != defined with it. When so desired, an excluded middle can be recovered by negating either the Equal() method or the == operator.

Answer 1

Your code formatting is mind-blowing. It is so unconventional, that it looks chaotic (even though there is probably a system to it). I had a really hard time reviewing it, even though the business logic itself is fairly simple. I think you should use common .Net coding style, if you want to share your code with other .Net developers. Otherwise they will have a really hard time reading it (which is probably part of why your question did not get much attention).

---

Value-equality for structs and string, reference equality for other classes

Both value types and reference types have Equals(object) method, why can't you use it in both cases? By default it will call ReferenceEquals internally for reference types anyway. But if I ever want to override the default equality implementation in my T class, I will be able to do it. Your current implementation does not allow it by enforcing reference comparison. You could also take it one step further and check if T implements IEquatable<T> interface, and if it does - call IEquatable<T>.Equals instead, again, for both value and reference types.

---

Your equality methods implementations break some of the common conventions.

• Two null objects should be equal to each other. Object.Equals(null, null) returns true. ((int?)null).Equals((float?)null) returns true. Etc. Its generally advised to follow this behavior in custom equality implementations, because it's the behavior people are expecting.

• Your NotEquals() method should return the same result as !Equals(). If it does, then you should use !Equals() internally instead of !this.HasValue || !other.HasValue || .... If it doesn't, then you are doing something wrong. I'm also not sure why would you need NotEquals() method in the first place, it just bloats the API. The consumers of your class should be perfectly capable of applying ! operator to Equals method themselves.

---

return Bind<string>(v => v.ToString()).Extract("");

Empty string is not very informative. I would rather have "Nothing: " + typeof(T) instead.

---

obj as Maybe<T>?

is a lot slower than if (obj is Maybe<T>) { (Maybe<T>)obj } and not much of an improvement when it comes to readability. So you probably should not use as operator with nullables. Unless you are actually expecting a nullable, ofc.

---

What looks fishy to me is that your monad is an actual data type. I can't imagine a scenario where I would want to hold a reference to a monad, or, even worse, a collection of monads. Monad is an abstraction of computation: you construct a monad chain, you execute it and then you garb the result of the computation. That's it. Even if you want to hold a reference to a chain for some reason, that's what delegates are for. If you use older versions of C#, the basic implementation of Maybe monad is a two-liner:

static TResult Maybe<TInput, TResult>(this TInput source, Func<TInput, TResult> projector)
    where TResult : class where TInput : class
{
    if (source == null) return null;
    return projector(source);
}

In later versions of C# you can just use ?. operator instead. Maybe monad is supposed to be simple. As simple as a regular null check. Yet you made it look really complex for a reason, that is unclear to me.

Answer 2

I'd like to expand on @NikitaB's answer, more specifically:

Your code formatting is mind-blowing. It is so unconventional, that it looks chaotic (even though there is probably a system to it).

---

Let's say I can live with Java-style braces in C# code - I can't, but that's my problem not yours. There are a number of more important things that wreck your code's readability:

• Attributes go on top of a method's signature. An attribute that's stuck to the left of an identifier is usually decorating a parameter, not a member. You seem to have arbitrary rules for deciding whether a member attribute should be to the left or on top:

  [Pure]public static Maybe<T> ToMaybe<T>(this T @this) { return @this; }
  

  vs

  [ContractArgumentValidator]
  public static void ContractedNotNull<T>([ValidatedNotNull]this T value, string name)
  

  Be consistent. Stack them on top of the member - every .net dev is going to be expecting them there.

• Don't suppress warnings you don't need to suppress:

  [SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "value")]
  [SuppressMessage("Microsoft.Usage", "CA1801:ReviewUnusedParameters", MessageId = "name")]
  [ContractAbbreviator] // Requires Assemble Mode = Standard Contract Requires
  [Pure]public static void ContractedNotNull<T>([ValidatedNotNull]this T value, string name) {
      Contract.Requires(value != null, name);
  }
  

  Why clutter up your code with noisy meta-attributes that suppress warnings that you're not even getting? As far as I can tell, both name and value parameters are used here.

• Avoid verbatim identifier if possible. @this is very confusing. Extension methods need an instance parameter, specified with the this keyword - perhaps instance could be a better name, or if @this is a Maybe type, then perhaps maybe could be a better name - I've seen people use that also. But verbatim identifiers should be a last resort, not a go-to option. Again, consistency matters: why is it this Foobar @this in some places, and this Foobar value in others?

• 2-space indent looks crowded. Going to 4-space indent would already air up your code a bit, and improve readability by a notch.

• I'd recommend to always use scoping braces around scopes, but I'm not sure it would actually do any good, given the Java-style same-line opening brace.

• Nothing is a keyword in VB.NET (null in C#); the member fulfills the role of an Empty value, but calling it Nothing makes that part of the API very much confusing if your library is referenced from a VB.NET project. I've seen lots of value types with an Empty member; this is the first time I'm seeing one with a Nothing member.

• Scope-closing braces go on their own line, please. And this isn't about a C# vs Java bracing style holy war - a private field declaration gets literally burried and forgotten if it's sitting on the same line as the brace that closes a property's scope:

  public static Maybe<T> Nothing {
  [Pure]get { Contract.Ensures( ! Contract.Result<Maybe<T>>().HasValue);
  
              Contract.Assume( ! _nothing.HasValue ); 
              return _nothing;
      }
  } static Maybe<T> _nothing;
  

  Looking at that member again, I'm not sure what your indenting scheme is anymore. It looked like it was 2-spaces for a while, but this one is completely off-putting, not to mention the scope-opening brace for the getter isn't even terminating the line, which adds to the mess. Consider:

  private static Maybe<T> _nothing;
  
  public static Maybe<T> Nothing {
      [Pure]
      get {
          Contract.Ensures(!Contract.Result<Maybe<T>>().HasValue);
          Contract.Assume(!_nothing.HasValue);
          return _nothing;
      }
  }
  

  Actually.... consider:

  private static Maybe<T> _nothing;
  
  public static Maybe<T> Nothing
  {
      [Pure]
      get
      {
          Contract.Ensures(!Contract.Result<Maybe<T>>().HasValue);
          Contract.Assume(!_nothing.HasValue);
          return _nothing;
      }
  }
  

  Notice the whitespace around ! - the whitespace you had was like a gigantic flashing neon arrow sign saying "LOOK!! THIS IS A NEGATION!!" ...I mean, come on.

• Get rid of #region.

• This nested ternary deserves attention:

  return ValueIsStruct ? new Maybe<T>(value)
       : value == null ? Maybe<T>.Nothing
                       : new Maybe<T>(value);
  

  I'm not sure what you're trying to line up here, but the result is absolutely unreadable. Consider:

  return ValueIsStruct 
      ? new Maybe<T>(value)
      : value == null 
          ? Maybe<T>.Nothing
          : new Maybe<T>(value);
  

  Notice something? Two branches return a new Maybe<T>(value) - something is fishy with that ternary. Let's decompose it.

  if (ValueIsStruct)
  {
      return new Maybe<T>(value);
  }
  else
  {
      if (value == null)
      {
          return Maybe<T>.Nothing;
      }
      else
      {
          return new Maybe<T>(value);
      }
  }
  

  Okay. So we return a new Maybe<T>(value) when ValueIsStruct || value != null. Otherwise we return Maybe<T>.Nothing.

  return (ValueIsStruct || value != null)
      ? new Maybe<T>(value)
      : Maybe<T>.Nothing;
  

  There. Nested ternaries should be killed with fire.