Skip to content

Instantly share code, notes, and snippets.

@johnazariah
Last active March 28, 2024 08:50
Show Gist options
  • Star 61 You must be signed in to star a gist
  • Fork 7 You must be signed in to fork a gist
  • Save johnazariah/d95c03e2c56579c11272a647bab4bc38 to your computer and use it in GitHub Desktop.
Save johnazariah/d95c03e2c56579c11272a647bab4bc38 to your computer and use it in GitHub Desktop.
Maybe Monad in C#

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.
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)));
}
// 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)
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)}");
}
}
@yahorsi
Copy link

yahorsi commented May 2, 2019

Why this kind of thing is not in C#/CLR yet (((

@rulrok
Copy link

rulrok commented Oct 3, 2019

I've recently learned about F# for DDD but I already wished I could easily replicate that functional mindset/capability on C#.
I tried implementing a new domain project on a production running solution, but I'm still not confident on my overall F# comprehension to make that jump.

As I'm really exited about the F# language, I am trying to bring these concepts to my C# project.

Would it make sense to have a version of GetOrElse which doesn't take a foldFunc (which it would be only a x => x).

Also, I was thinking about a way of also not having to define the default value explicitly.
Would it make sense to have it working like the .HasValue of Nullable<T> and have a .Value which would return default(T)?

@ericrey85
Copy link

ericrey85 commented Oct 5, 2019

@rulrok, I will try to answer your questions.

1 - Would it make sense to have a version of GetOrElse which doesn't take a foldFunc (which it would be only a x => x).

Yes, you could do that if you find yourself using GetOrElse several times and the foldFunc is always x => x (which by the way is the signature of the Identity function).

2 - Also, I was thinking about a way of also not having to define the default value explicitly.
Would it make sense to have it working like the .HasValue of Nullable and have a .Value which would return default(T)?

You can, I do not recommend it for reference types, since by doing default(T) you would be folding to NULL (defeating the purpose of the Maybe Monad). Also, if you do it for value types, just be aware that default(T) could return something different if you ever upgrade the .NET framework (relying on framework specific implementations is always a risk because of this). In any case, do not remove the original GetOrElse, which gives you control over how to produce the default value you want to fold to in case of the Monad being None (missing value). For example, a few days ago I created an async method that would try to retrieve the default value using a network call if the first operation trying to get the value resulted in a "None" Maybe.

@ericrey85
Copy link

ericrey85 commented Oct 5, 2019

I wrote a Combine function that behaves in a similar way than SelectMany<A, B, C> but that folds the final value in case there is one, or uses a delegate to produce a default value otherwise.

public R Combine<B, R>(Maybe<B> mb, Func<T, B, R> select, Func<R> defaultValueFactory) => Bind(a => mb.Map(b => select(a, b))).Match(x => x, defaultValueFactory);

Usage:

var intMonad = Maybe<int>.Some(42);
var doubleMonad = Maybe<double>.Some(32.1);

var result = intMonad.Combine(doubleMonad, (a, b) => a + b, () => -1);
// result : Double [74.1]

@johnazariah
Copy link
Author

@rulrok, @ericrey85 thank you for your comments!

My belated notes, below:

@rulrok: You could do a variant of GetOrElse which provided a default value. I would avoid the variant of Get which throws on None. The variant that returns default kind of defeats the purpose of the Maybe, because we don't do runtime checks with this approach, but once you return default, you force the caller to do a runtime check.

@ericrey85: I love the Combine :)

@johnazariah
Copy link
Author

Why this kind of thing is not in C#/CLR yet (((

Thanks for your kind words, @yahorsi :)

@bert2
Copy link

bert2 commented Feb 8, 2020

Did you know that nullable reference/value types can be extended to form a maybe monad? The implementation is a bit awkward due to the NRT vs Nullable<T> dichotomy, but that's transparent to the users. Check out the unit tests of this nuget package to see what I mean: https://github.com/bert2/Nullable.Extensions

@johnazariah
Copy link
Author

Did you know that nullable reference/value types can be extended to form a maybe monad? The implementation is a bit awkward due to the NRT vs Nullable<T> dichotomy, but that's transparent to the users. Check out the unit tests of this nuget package to see what I mean: https://github.com/bert2/Nullable.Extensions

You're absolutely right!

In fact, IMHO C# has been moving ever-so-slowly to normalize functional style, and the whole nullable reference/value type - along with the ?. operator and variants are effectively monadic composition on Maybe. The nature of the language is that each monad has its own syntax (async-await, LINQ, and ?.) but because they are all monads, they can all be written in LINQ syntax!

Thanks for your comments!

@willowell
Copy link

Hi there! I'm working on translating a toy Number Guessing Game program from Haskell to a few programming languages, including C#, as part of learning Haskell, and your Maybe monad class looks perfect! May I use your Maybe monad class as part of my C# program? If so, do you have any licensing terms for its use?

In particular, I am considering using your Maybe monad class to wrap user input.

@johnazariah
Copy link
Author

johnazariah commented Jul 7, 2020 via email

@willowell
Copy link

Thank you very much!!

@dmitrynovik
Copy link

I reckon to make it safe to be used in hash sets / dictionaries,, instead of disabling compiler warnings with pragmas one needs to do a tiny bit of work and implement the GetHashCode (it's really a one liner method).

@johnazariah
Copy link
Author

Thanks for the feedback, @dmitrynovik!

You'll notice that the pragmas are only for the abstract base class. This is because the compiler warns that abstract base class has no special implementation of GetHashCode even though all the derived classes have GetHashCode implemented.

The base class implements the == and != operators in terms of abstract methods...

@Perustaja
Copy link

Perustaja commented Dec 30, 2020

Awesome job, have you considered making something similar to Either<L, R> (Haskell) or Result<T, E> (Rust)? It's a huge pain doing some things without some form of Maybe/Option and Result/Either in C#. I am making my own version of Option and your work here has really done a lot to help show me how to work with C#. I'm working on a Result<T, E> as well, but basically just following your work and add just enough functionality to get back to work on my project before spending some free time on it.

Just wanted to say your approach is super clean and short. I'm not the greatest so it's been awesome to see your implementation!

@ericrey85
Copy link

@Perustaja you can find an implementation of Result<Success, Failure> for C# in LeanSharp https://github.com/ericrey85/LeanSharp/, there is also a NuGet package for it. Although there are other libraries that have an implementation for it as well.

@johnazariah
Copy link
Author

johnazariah commented Dec 30, 2020 via email

@ProximaB
Copy link

ProximaB commented Apr 6, 2021

Could I get your opinions on this style of programming in c# with Result type?
Do you have any open source minimal nuget package for fp programming?
Thanks

public string RefillBalance(int customerId, decimal moneyAmount)
{
    var moneyToCharge = MoneyAmount.Create(moneyAmount);
    var customer = customerRepositoryAfterAfter.GetById(customerId).ToResult("Customer can't be found");
    return Result.Combine(moneyToCharge, customer)
        .OnSuccess(() => customer.Value!.AddBalance(moneyToCharge.Value))
        .OnSuccess(() => paymentServiceAfter.ChargePayment(customer.Value!.BillingInfo, moneyToCharge.Value))
        .OnSuccess(
            () => customerRepositoryAfterAfter.Save(customer.Value!)
                .OnFailure(()=> paymentServiceAfter.RollbackLastTransaction()))
        .OnBoth(result => Log(result))
        .OnBoth(result => result.IsSuccess ? "OK" : result.Error);


}

@perokvist
Copy link

I thought this also could add to cleaner interop, but this kind of method could return null (when none) (that could be handled if you only match where you use it), but my F# foo fails me to avoid that.

Any takers for a better approach?

    let toOption<'T> (m:Maybe<'T>) : Option<'T> =
        m.GetOrElse((fun v -> Option.Some(v)), Option<'T>.None)

@johnazariah
Copy link
Author

Could I get your opinions on this style of programming in c# with Result type?
Do you have any open source minimal nuget package for fp programming?
Thanks

public string RefillBalance(int customerId, decimal moneyAmount)
{
    var moneyToCharge = MoneyAmount.Create(moneyAmount);
    var customer = customerRepositoryAfterAfter.GetById(customerId).ToResult("Customer can't be found");
    return Result.Combine(moneyToCharge, customer)
        .OnSuccess(() => customer.Value!.AddBalance(moneyToCharge.Value))
        .OnSuccess(() => paymentServiceAfter.ChargePayment(customer.Value!.BillingInfo, moneyToCharge.Value))
        .OnSuccess(
            () => customerRepositoryAfterAfter.Save(customer.Value!)
                .OnFailure(()=> paymentServiceAfter.RollbackLastTransaction()))
        .OnBoth(result => Log(result))
        .OnBoth(result => result.IsSuccess ? "OK" : result.Error);


}

I think this isn't really idiomatic C#, and it would be hard to debug it...

You'd be better off doing stuff with async/await, because Task encapsulates the Result monad...

@Clindbergh
Copy link

Note: There is also nlkl/Optional providing some more functionalities.

@johnazariah
Copy link
Author

johnazariah commented Mar 2, 2022 via email

@benlongo
Copy link

benlongo commented Mar 2, 2022

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.

@gokayokutucu
Copy link

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

@johnazariah
Copy link
Author

johnazariah commented Aug 31, 2022 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment