Maybe Monad in C#

Readme.md

The Maybe monad in C#

I've often wanted to use the F# option type in C#. So I wrote the Maybe class which works like it.

Discriminated Union

Maybe<T> is a discriminated union type with two possible value constructors: Some and None.

The presence of a value of type T is signified by lifting it into a Maybe<T> using the Some constructor. Conversely, the absence of a value is signified by the use of the None constructor.

The discriminated union is implemented using an abstract class with a private, closed set of heirs.

Since the set of heirs is both private and closed, there is no way of directly deciding what the type of a given instance of Maybe<T> is. This necessitates a matching mechanism which invokes a handler based on the type of the instance.

Note that this means that there is no type comparison, nor is there any if-then-else checking.

Examples

• Creating a Maybe to signify the absence of any value

var none = Maybe<int>.None;
// none : Maybe<int> [None]

• Creating a Maybe to signify the presence of a value of type string

var key = Maybe<string>.Some("The key to the kingdom");
// key : Maybe<string> [Some("The key to the kingdom")]

• Given an instance of Maybe<int>, add 1 to the value if it is present and return the incremented value, or 0 if no value is present

// arg : Maybe<int> [??]
var result = arg.Match(v => v + 1, () => 0);
// result : Maybe<int> [(n + 1) -or- 0]

• Given an instance of Maybe<string>, print the value if it is present or the string "Missing"

// arg : Maybe<string> [??]
arg.Iter(Console.WriteLine, () => Console.WriteLine("Missing"));

Value Semantics

Instances of the Maybe class exhibit value semantics. This means that two instances of Some with the same value will report equality when compared, even if their references are not. This is done by implementing the IEquatable<Maybe<T>> and IStructuralEquatable interfaces, and providing custom == and != operators.

The following examples all print True:

Console.WriteLine($"None   == None   : {Maybe<int>.None == Maybe<int>.None}");
Console.WriteLine($"Some 5 == Some 5 : {Maybe<int>.Some(5) == Maybe<int>.Some(5)}");
Console.WriteLine($"Some 6 != Some 5 : {Maybe<int>.Some(6) != Maybe<int>.Some(5)}");
Console.WriteLine($"Some 2 != None   : {Maybe<int>.Some(2) != Maybe<int>.None}");
Console.WriteLine($"None   != Some 2 : {Maybe<int>.None != Maybe<int>.Some(2)}");

Functor

The Maybe class can implement a map function, essentially making it a Functor.

Map

• Given an instance of Maybe<int>, increment any present value and return it

// arg : Maybe<int> [??]
var result = arg.Map(v => v + 1);
// result : Maybe<int> [Some (n + 1) -or- None]

Foldable

The Maybe class can be structurally folded and its value liberated.

GetOrElse

• Given an instance of Maybe<string>, extract any present string value, otherwise return the empty string.

// arg : Maybe<string> [??]
var result = arg.GetOrElse(x => x, String.Empty);
// result : string [value -or- String.Empty]

• Given an instance of Maybe<int>, extract the string representation of any value present, otherwise an empty string.

// arg : Maybe<int> [??]
var result = arg.GetOrElse(x => x.ToString(), String.Empty);
// result : string [value -or- String.Empty]

Fold

Fold with traditional arguments provided for sake of completeness.

Monad

The Maybe class can be treated as a monad, and computations on the value can be composed safely using the Return and Bind methods

Return

• Given an integer, lift it into an instance of Maybe<int>

var result = Maybe<int>.Return(42);
// result : Maybe<int> [Some(42)]

Bind

• Given an instance of Maybe<int>, and a function which takes an int to Maybe<bool>, chain them together so that function is only invoked when an integer value is present

var result = Maybe<42>.Bind(v => Maybe<bool>.Some(v % 2 == 0));
// result : Maybe<bool> [Some(true)]

LINQ extension

C# provides a mechanism for obtaining LINQ Syntactic Sugar for monadic composition.

• Given two instances of Maybe<int>, return their sum

var result = from a in Maybe<int>.Some(4)
    from b in Maybe<int>.Some(6)
    select a + b;
// result : Maybe<int> [Some(10)]

Changelog

• EDIT: Feb 7 2020 - Incorporated Combine from @ericrey85. Thank you!
• EDIT: Feb 7 2020 - Added GetOrDefault as suggested to @rulrok.

LinqExtensions.cs

public static partial class LinqExtensions
{
    public static Maybe<C> SelectMany<A, B, C>(this Maybe<A> ma, Func<A, Maybe<B>> f, Func<A, B, C> select) => ma.Bind(a => f(a).Map(b => select(a, b)));
}

Maybe.cs

// The following #pragma disables are justified because the abstract base class doesn't provide override but the sealed children do
#pragma warning disable CS0660 // Type defines operator == or operator != but does not override Object.Equals(object o)
#pragma warning disable CS0661 // Type defines operator == or operator != but does not override Object.GetHashCode()
    public abstract class Maybe<T> : IEquatable<Maybe<T>>, IStructuralEquatable
    {
        public static explicit operator Maybe<T>(T value) =>
            Some(value);

        public static Maybe<T> Some(T value) =>
            new Choices.Some(value);

        public static Maybe<T> None { get; } = new Choices.None();

        public abstract R Match<R>(Func<T, R> someFunc, Func<R> noneFunc);

        public abstract void Iter(Action<T> someAction, Action noneAction);

        public Maybe<R> Map<R>(Func<T, R> map) =>
            Match(
                v => Maybe<R>.Some(map(v)),
                () => Maybe<R>.None);

        public R Fold<R>(Func<R, T, R> foldFunc, R seed) =>
            Match(t => foldFunc(seed, t), () => seed);

        public R GetOrElse<R>(Func<T, R> foldFunc, R seed) =>
            Fold((_, t) => foldFunc(t), seed);

        public T GetOrDefault(T defaultValue) =>
            Fold((_, t) => t, defaultValue);

        public static Maybe<T> Return(T value) =>
            Some(value);

        public Maybe<R> Bind<R>(Func<T, Maybe<R>> map) =>
            Match(
                v => map(v).Match(
                    r => Maybe<R>.Some(r),
                    () => Maybe<R>.None),
                () => Maybe<R>.None);

        #region Value Semantics
        public static bool operator ==(Maybe<T> x, Maybe<T> y) =>
            x.Equals(y);

        public static bool operator !=(Maybe<T> x, Maybe<T> y) =>
            !(x == y);

        bool IEquatable<Maybe<T>>.Equals(Maybe<T> other) =>
            Equals(other as object);

        public abstract bool Equals(object other, IEqualityComparer comparer);

        public abstract int GetHashCode(IEqualityComparer comparer);
        #endregion

        private Maybe() { }

        private static class Choices
        {
            public sealed class Some : Maybe<T>
            {
                private T Value { get; }

                public Some(T value) =>
                    Value = value;

                public override R Match<R>(Func<T, R> someFunc, Func<R> noneFunc) =>
                    someFunc(Value);

                public override void Iter(Action<T> someAction, Action noneAction) =>
                    someAction(Value);

                public override string ToString() =>
                    $"Some ({Value})";

                #region Value Semantics
                public override bool Equals(object obj) =>
                    obj is Some s
                        ? Value.Equals(s.Value)
                        : false;

                public override bool Equals(object other, IEqualityComparer comparer) =>
                    other is Some s
                        ? comparer.Equals(Value, s.Value)
                        : false;

                public override int GetHashCode() =>
                    "Some ".GetHashCode() ^ Value.GetHashCode();

                public override int GetHashCode(IEqualityComparer comparer) =>
                    "Some ".GetHashCode() ^ comparer.GetHashCode(Value);
                #endregion
            }

            public sealed class None : Maybe<T>
            {
                public override R Match<R>(Func<T, R> someFunc, Func<R> noneFunc) =>
                    noneFunc();

                public override void Iter(Action<T> someAction, Action noneAction) =>
                    noneAction();

                public override string ToString() =>
                    "None";

                #region Value Semantics
                public override bool Equals(object obj) =>
                    obj is None;

                public override int GetHashCode() =>
                    "None".GetHashCode();

                public override bool Equals(object other, IEqualityComparer comparer) =>
                    Equals(other);

                public override int GetHashCode(IEqualityComparer comparer) =>
                    GetHashCode();
                #endregion
            }
        }
    }
#pragma warning restore CS0661 // Type defines operator == or operator != but does not override Object.GetHashCode()
#pragma warning restore CS0660 // Type defines operator == or operator != but does not override Object.Equals(object o)

Program.cs

class Program
{
    static void Main(string[] args)
    {
        var result = from a in Maybe<int>.Some(4)
                     from b in Maybe<int>.Some(6)
                     select a + b;
        Console.WriteLine(result);

        Console.WriteLine($"None   == None   : {Maybe<int>.None == Maybe<int>.None}");
        Console.WriteLine($"Some 5 == Some 5 : {Maybe<int>.Some(5) == Maybe<int>.Some(5)}");
        Console.WriteLine($"Some 6 != Some 5 : {Maybe<int>.Some(6) != Maybe<int>.Some(5)}");
        Console.WriteLine($"Some 2 != None   : {Maybe<int>.Some(2) != Maybe<int>.None}");
        Console.WriteLine($"None   != Some 2 : {Maybe<int>.None != Maybe<int>.Some(2)}");
    }
}

After thinking about this more, the hash function must map two int's of Ts hash function to the same number since the cardinality of Maybe<T> is 1 greater than the cardinality of T. I don't think it really matters which two numbers you pick to map to the same thing though. In my implementation I have None always yield a hash of 0, and then if the hash of Some(value) yields 0, I remap that to Int32.MinValue.

It would be good if it's a serializable object.

Accepting PRs :)

…

On Wed, 31 Aug 2022, 18:37 Gokay, ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ It would be good if it's a serializable object. — Reply to this email directly, view it on GitHub <https://gist.github.com/d95c03e2c56579c11272a647bab4bc38#gistcomment-4285451>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAGKWZ7P56LSPJBHXA2F6HTV34KT3ANCNFSM4HJ6VCSQ> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>