Functional Thread 8 - Monadic Computations & Nullable

[)roi(]

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
6,282
Reaction score
405
Location
ッ
Previous Thread
In the last functional thread we explored the following two FP algebras:
  • Yoneda
  • Coyoneda
Algebras which provided us a solution to encapsulate our code in a data structure that internally employs Lazy Transformations without the requirement to modify any of our data types; more specifically data types that defer data transformations by compositing all the changes, and in providing a way to delay the compute until it is required.

For reference, you can find that thread here:
https://mybroadband.co.za/forum/threads/functional-thread-7-lazy-transformations.1007038/
Click to expand...

Monadic Computations
In functional programming, monadic computations are useful to encapsulate effectual style computations that need to produce an end result. More than that it provides a mechanism that allows us to structure our typically imperative style code more generically whilst also automating away the boilerplate code that typically encapsulates conditional programming.

In short, we will be exploring a few different ways that the Monad algebra can be employed, and to briefly contrast this against the Functor and Applicative Functor algebras in terms of the versatility of each.

Target Audience
This thread is targeted at intermediate developers; hence we'll be building on a few of the data types created in the FP thread 6, part 1 and part 2, for example:
  • Maybe,
  • Either,
  • etc.
Note:
  • This is going to be a fairly short thread, but it will include quite a bit of code.
  • There again is no need to understand the mathematics behind this to use it and the implementations in C# will be relatively easy to understand without a maths background.
  • We will also as a bonus be looking at how we can make our custom FP data types like Maybe, Either, ... work alongside the Linq specific syntax, for example: from x in xs
Click to expand...
 
Last edited:
Continuing from the Functional Thread 6 Part 2 on Exception handling.
We walked through a composition process with the FlatMap aka Bind method which can be used to not only manage effectual state across separate functions, but also as an alternative way to manage exceptions; a concept that is called Railway Oriented Programming.

This thread will focus on an alternative way to use a monadic algebra in your code; one that lends itself to monadic computations / operations.

Challenge
We have 5 data type variables, that could either have some value or none.
C#: 
var ma = Some(2);
var mb = Some(3);
var mc = Some(4);
var md = Some(5);
var me = Some(6);

If all 5 variables have values then compose these values with the sum function, and return this as a new Maybe Some containing the result.
C#: 
var sum = Fun((int a, int b, int c, int d, int e) => a + b + c + d + e);
... and if 1 or more of the 5 variables has no values, then return a Maybe None.
The Fun function call is a syntactic sugar combinator for lifting lambda functions so that can work with the var keyword as oppose to the more verbose Func<int, int, int, int, int, int> form.

Here's the code for Fun combinator
C#: 
public static partial class ƒ {
    #region Lift to Func Form
    public static Func<A> Fun<A>(Func<A> fn) => fn;
    public static Func<A, B> Fun<A, B>(Func<A, B> fn) => fn;
    public static Func<A, B, C> Fun<A, B, C>(Func<A, B, C> fn) => fn;
    public static Func<A, B, C, D> Fun<A, B, C, D>(Func<A, B, C, D> fn) => fn;
    public static Func<A, B, C, D, E> Fun<A, B, C, D, E>(Func<A, B, C, D, E> fn) => fn;
    public static Func<A, B, C, D, E, F> Fun<A, B, C, D, E, F>(Func<A, B, C, D, E, F> fn) => fn;
    public static Func<A, B, C, D, E, F, G> Fun<A, B, C, D, E, F, G>(Func<A, B, C, D, E, F, G> fn) => fn;
    public static Func<A, B, C, D, E, F, G, H> Fun<A, B, C, D, E, F, G, H>(Func<A, B, C, D, E, F, G, H> fn) => fn;
    #endregion
}
Click to expand...

The Imperative approach
Considering that the 5 variables are sum types; which for Maybe implies that we have 2 possible outcomes.

A standard imperative approach will conditionally evaluate each of our variables; an evaluation of a condition imbedded within another; up to the point where we can compute the sum all of the variables, else we return None.
C#: 
Maybe<int> mr0;
if (ma.IsSome) {
  if (mb.IsSome) {
    if (mc.IsSome) {
      if (md.IsSome) {
        if (me.IsSome) {
          mr0 = Some(sum(ma.value, mb.value, mc.value, md.value, me.value));
        } else {
          mr0 = me;
        }
      } else {
        mr0 = me;
      }
    } else {
      mr0 = me;
    }
  } else {
    mr0 = mb;
  }
} else {
  mr0 = ma;
}
mr0.Map(x => x / 2).Print("\nmresult :- Imperative"); // transformation of result



The FlatMap approach
To achieve the same result using FP's FlatMap, we embed each FlatMap call within another, similar to Imperative's conditional approach. You can think of FlatMap as a process, that unboxes the value in the Maybe data type, and once we've unboxed everything, we compute the sum and return the result as a Maybe Some of the computed sum.

We don't need to make any special provision for the else conditional, because that's an integral algebraic behaviour of our monadic FlatMap extension method.
C#: 
var mr1 = ma.FlatMap(a => mb
  .FlatMap(b => mc
  .FlatMap(c => md
  .FlatMap(d => me
  .FlatMap(e => Some(sum(a, b, c, d, e)))))))
  .Map(x => x / 2); // transformation of result
mr1.Print("mresult :- FP FlatMap");



The Linq approach
Let's tackle the same thing with Linq special syntax, from like our FLatMap unboxes our values.
select in this code either is substituted with the extension method Select or SelectMany. The extension methods that make our Maybe data type support the Linq syntax, follows after this example.
C#: 
var mr2 = from x in (from a in ma
                     from b in mb
                     from c in mc
                     from d in md
                     from e in me
                     select sum(a, b, c, d, e))
                 select x / 2; // transformation of result
mr2.Print("mresult :- Linq");


Linq extension methods for Maybe
For basic support we need to define at least 2 extension methods to support the above Linq operation.
C#: 
#region Linq Conformance
public static Maybe<R> Select<A, R>(this Maybe<A> @this, Func<A, R> fn) => @this.Map(fn);
public static Maybe<R> SelectMany<A, B, R>(this Maybe<A> @this, Func<A, Maybe<B>> fn, Func<A, B, R> select) => @this.FlatMap(a => fn(a).FlatMap(b => select(a, b).ToMaybe()));
#endregion


The Monadic Lifting approach
The final approach to this problem is to use the Monadic lifting ability of our Maybe data type.
C#: 
var mr3 = sum.LiftM(ma, mb, mc, md, me).Map(x => x / 2);
mr3.Print("mresult :- FP LiftM");
Which is the most terse approach to this challenge; just 2 lines of code versus 24 with for the Imperative approach


But how does LiftM work?
It's actually quite simple we have created a new set of extension methods for our Maybe data type; which essentially are a generic version of the FlatMap approach above. Here's the code for extension methods that cater for up to 10 input data types.

C#: 
#region Monad - Lift a function & data type encapsulated parameters values
public static Maybe<R> LiftM<A, B, R>(this Func<A, B, R> @this, Maybe<A> a, Maybe<B> b) => a.FlatMap(m1 => b.FlatMap(m2 => Some(@this(m1, m2))));
public static Maybe<R> LiftM<A, B, C, R>(this Func<A, B, C, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => Some(@this(xa, xb, xc)))));
public static Maybe<R> LiftM<A, B, C, D, R>(this Func<A, B, C, D, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c, Maybe<D> d) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => Some(@this(xa, xb, xc, xd))))));
public static Maybe<R> LiftM<A, B, C, D, E, R>(this Func<A, B, C, D, E, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c, Maybe<D> d, Maybe<E> e) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => Some(@this(xa, xb, xc, xd, xe)))))));
public static Maybe<R> LiftM<A, B, C, D, E, F, R>(this Func<A, B, C, D, E, F, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c, Maybe<D> d, Maybe<E> e, Maybe<F> f) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => Some(@this(xa, xb, xc, xd, xe, xf))))))));
public static Maybe<R> LiftM<A, B, C, D, E, F, G, R>(this Func<A, B, C, D, E, F, G, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c, Maybe<D> d, Maybe<E> e, Maybe<F> f, Maybe<G> g) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => Some(@this(xa, xb, xc, xd, xe, xf, xg)))))))));
public static Maybe<R> LiftM<A, B, C, D, E, F, G, H, R>(this Func<A, B, C, D, E, F, G, H, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c, Maybe<D> d, Maybe<E> e, Maybe<F> f, Maybe<G> g, Maybe<H> h) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => Some(@this(xa, xb, xc, xd, xe, xf, xg, xh))))))))));
public static Maybe<R> LiftM<A, B, C, D, E, F, G, H, I, R>(this Func<A, B, C, D, E, F, G, H, I, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c, Maybe<D> d, Maybe<E> e, Maybe<F> f, Maybe<G> g, Maybe<H> h, Maybe<I> i) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap(xi => Some(@this(xa, xb, xc, xd, xe, xf, xg, xh, xi)))))))))));
public static Maybe<R> LiftM<A, B, C, D, E, F, G, H, I, J, R>(this Func<A, B, C, D, E, F, G, H, I, J, R> @this, Maybe<A> a, Maybe<B> b, Maybe<C> c, Maybe<D> d, Maybe<E> e, Maybe<F> f, Maybe<G> g, Maybe<H> h, Maybe<I> i, Maybe<J> j) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap(xi => j.FlatMap(xj => Some(@this(xa, xb, xc, xd, xe, xf, xg, xh, xi, xj))))))))))));
#endregion
Quite a lot of generic code, but as with everything FP this code employs the DRY principle; which means that we can take advantage of the terseness of the LiftM method call across all uses of the Maybe data type in our code base.

At this point it should be obvious that the imperative approach is considerably more verbose, that our LiftM method.

Haskell Types re LiftM
FYI here is the type definition for our LiftM types in Haskell.
Code: 
liftM :: Monad m => (a1 -> r) -> m a1 -> m r
liftM2 :: Monad m => (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
liftM3 :: Monad m => (a1 -> a2 -> a3 -> r) -> m a1 -> m a2 -> m a3 -> m r
...
Click to expand...

In the next post we'll look at similar challenge but this time we'll build this around the IEnumerable List data type.
 
Last edited:
Let's compare the same computation using Either type
C#: 
var ea = Right<string, int>(2);
var eb = Right<string, int>(3);
var ec = Right<string, int>(4);
var ed = Right<string, int>(5);
var ee = Right<string, int>(6);


The Imperative approach
C#: 
Either<string, int> er0;
if (ea.IsRight) {
  if (eb.IsRight) {
    if (ec.IsRight) {
      if (ed.IsRight) {
        if (ee.IsRight) {
          er0 = Right<string, int>(sum(ea.right, eb.right, ec.right, ed.right, ee.right));
        } else {
          er0 = ee;
        }
      } else {
        er0 = ed;
      }
    } else {
      er0 = ec;
    }
  } else {
    er0 = eb;
  }
} else {
  er0 = ea;
}
er0.Map(x => x / 2).Print("\neresult :- Imperative");


The FlatMap approach
C#: 
var er1 = ea.FlatMap(a => eb
  .FlatMap(b => ec
  .FlatMap(c => ed
  .FlatMap(d => ee
  .FlatMap(e => Right<string, int>(sum(a, b, c, d, e)))))))
  .Map(x => x / 2);
er1.Print("eresult :- FP FlatMap");


The Linq approach
C#: 
var mr2 = from x in (from a in ma
                     from b in mb
                     from c in mc
                     from d in md
                     from e in me
                     select sum(a, b, c, d, e))
                 select x / 2; // transformation of result
mr2.Print("mresult :- Linq");


The Monadic Lifting approach
C#: 
var er3 = sum.LiftM(ea, eb, ec, ed, ee).Map(x => x / 2);
er3.Print("eresult :- FP LiftM");


Comparison between Either and Maybe
If we compare the 4 Either approaches to the same approaches for Maybe type, we can summarise that only the Linq and Monadic Lifting approaches utilise the same code for both types. I'd like you to also observe how much of the syntax is different between the Imperative approach for Either and Maybe.


Linq extension methods for Either
C#: 
public static Either<L, R2> Select<L, R, R2>(this Either<L, R> @this, Func<R, R2> fn) => @this.Map(fn);
public static Either<L, R2> SelectMany<L, R, R1, R2>(this Either<L, R> @this, Func<R, Either<L, R1>> fn, Func<R, R1, R2> select) => @this.FlatMap(a => fn(a).FlatMap(b => select(a, b).ToEither<L, R2>()));


LiftM extension methods for Either
C#: 
public static Either<L, R> LiftM<A, B, L, R>(this Func<A, B, R> @this, Either<L, A> a, Either<L, B> b) => a.FlatMap(m1 => b.FlatMap(m2 => Right<L, R>(@this(m1, m2))));
public static Either<L, R> LiftM<A, B, C, L, R>(this Func<A, B, C, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => Right<L, R>(@this(xa, xb, xc)))));
public static Either<L, R> LiftM<A, B, C, D, L, R>(this Func<A, B, C, D, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c, Either<L, D> d) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => Right<L, R>(@this(xa, xb, xc, xd))))));
public static Either<L, R> LiftM<A, B, C, D, E, L, R>(this Func<A, B, C, D, E, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c, Either<L, D> d, Either<L, E> e) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => Right<L, R>(@this(xa, xb, xc, xd, xe)))))));
public static Either<L, R> LiftM<A, B, C, D, E, F, L, R>(this Func<A, B, C, D, E, F, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c, Either<L, D> d, Either<L, E> e, Either<L, F> f) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => Right<L, R>(@this(xa, xb, xc, xd, xe, xf))))))));
public static Either<L, R> LiftM<A, B, C, D, E, F, G, L, R>(this Func<A, B, C, D, E, F, G, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c, Either<L, D> d, Either<L, E> e, Either<L, F> f, Either<L, G> g) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => Right<L, R>(@this(xa, xb, xc, xd, xe, xf, xg)))))))));
public static Either<L, R> LiftM<A, B, C, D, E, F, G, H, L, R>(this Func<A, B, C, D, E, F, G, H, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c, Either<L, D> d, Either<L, E> e, Either<L, F> f, Either<L, G> g, Either<L, H> h) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => Right<L, R>(@this(xa, xb, xc, xd, xe, xf, xg, xh))))))))));
public static Either<L, R> LiftM<A, B, C, D, E, F, G, H, I, L, R>(this Func<A, B, C, D, E, F, G, H, I, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c, Either<L, D> d, Either<L, E> e, Either<L, F> f, Either<L, G> g, Either<L, H> h, Either<L, I> i) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap(xi => Right<L, R>(@this(xa, xb, xc, xd, xe, xf, xg, xh, xi)))))))))));
public static Either<L, R> LiftM<A, B, C, D, E, F, G, H, I, J, L, R>(this Func<A, B, C, D, E, F, G, H, I, J, R> @this, Either<L, A> a, Either<L, B> b, Either<L, C> c, Either<L, D> d, Either<L, E> e, Either<L, F> f, Either<L, G> g, Either<L, H> h, Either<L, I> i, Either<L, J> j) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap(xi => j.FlatMap(xj => Right<L, R>(@this(xa, xb, xc, xd, xe, xf, xg, xh, xi, xj))))))))))));
 
Last edited:
Let's compare this with the List type
C#: 
var la = List(2, 3);
var lb = List(3, 4);
var lc = List(4, 5);
var ld = List(5, 6);
var le = List(6, 7);


The Imperative approach
C#: 
var lr0 = List<int>();
foreach (var a in la) {
  foreach (var b in lb) {
    foreach (var c in lc) {
      foreach (var d in ld) {
        foreach (var e in le) {
          lr0.Add(sum(a, b, c, d, e));
        }
      }
    }
  }
}
lr0.Map(x => x / 2).Print("\nlresult :- Imperative");


The FlatMap approach
C#: 
var lr1 = la.FlatMap(a => lb
  .FlatMap(b => lc
  .FlatMap(c => ld
  .FlatMap(d => le
  .FlatMap(e => List(sum(a, b, c, d, e)))))))
  .Map(x => x / 2);
lr1.Print("lresult :- FP FlatMap");


The Linq approach
C#: 
var lr2 = (from x in (from a in la
                            from b in lb
                            from c in lc
                            from d in ld
                            from e in le
                            select sum(a, b, c, d, e))
                select x / 2);
lr2.Print("lresult :- Linq");


The Monadic Lifting approach
C#: 
var lr3 = sum.LiftM(la, lb, lc, ld, le).Map(x => x / 2);
lr3.Print("lresult :- FP LiftM");


Comparison between List, Either and Maybe
If we compare the 4 List approaches to the same approaches for Either and Maybe types, we can summarise again that only the Linq and Monadic Lifting approaches utilise the same code for both types.

And observe specifically how different the code is for the Imperative approach; we had to change the code because the List type can have zero or more elements as opposed to Either and Maybe which are typically single values. Monadic operations over types like List which can have zero or more elements will result in a many to many computation.

Hopefully that gives you some ideas about why the FP approaches are typically more terse, but also quite a bit easier to maintain, especially if code changes may involve similar computation across different types.

Linq extension methods for List
These are already defined by Microsoft as part of the .Net framework.

LiftM extension methods for IEnumerable
C#: 
public static IEnumerable<R> LiftM<A, B, R>(this Func<A, B, R> @this, IEnumerable<A> a, IEnumerable<B> b) => a.FlatMap(xa => b.FlatMap(xb => List(@this(xa, xb))));
public static IEnumerable<R> LiftM<A, B, C, R>(this Func<A, B, C, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => List(@this(xa, xb, xc)))));
public static IEnumerable<R> LiftM<A, B, C, D, R>(this Func<A, B, C, D, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c, IEnumerable<D> d) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => List(@this(xa, xb, xc, xd))))));
public static IEnumerable<R> LiftM<A, B, C, D, E, R>(this Func<A, B, C, D, E, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c, IEnumerable<D> d, IEnumerable<E> e) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => List(@this(xa, xb, xc, xd, xe)))))));
public static IEnumerable<R> LiftM<A, B, C, D, E, F, R>(this Func<A, B, C, D, E, F, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c, IEnumerable<D> d, IEnumerable<E> e, IEnumerable<F> f) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => List(@this(xa, xb, xc, xd, xe, xf))))))));
public static IEnumerable<R> LiftM<A, B, C, D, E, F, G, R>(this Func<A, B, C, D, E, F, G, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c, IEnumerable<D> d, IEnumerable<E> e, IEnumerable<F> f, IEnumerable<G> g) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => List(@this(xa, xb, xc, xd, xe, xf, xg)))))))));
public static IEnumerable<R> LiftM<A, B, C, D, E, F, G, H, R>(this Func<A, B, C, D, E, F, G, H, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c, IEnumerable<D> d, IEnumerable<E> e, IEnumerable<F> f, IEnumerable<G> g, IEnumerable<H> h) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => List(@this(xa, xb, xc, xd, xe, xf, xg, xh))))))))));
public static IEnumerable<R> LiftM<A, B, C, D, E, F, G, H, I, R>(this Func<A, B, C, D, E, F, G, H, I, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c, IEnumerable<D> d, IEnumerable<E> e, IEnumerable<F> f, IEnumerable<G> g, IEnumerable<H> h, IEnumerable<I> i) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap(xi => List(@this(xa, xb, xc, xd, xe, xf, xg, xh, xi)))))))))));
public static IEnumerable<R> LiftM<A, B, C, D, E, F, G, H, I, J, R>(this Func<A, B, C, D, E, F, G, H, I, J, R> @this, IEnumerable<A> a, IEnumerable<B> b, IEnumerable<C> c, IEnumerable<D> d, IEnumerable<E> e, IEnumerable<F> f, IEnumerable<G> g, IEnumerable<H> h, IEnumerable<I> i, IEnumerable<J> j) => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap(xi => j.FlatMap(xj => List(@this(xa, xb, xc, xd, xe, xf, xg, xh, xi, xj))))))))))));
 
Last edited:
Johnatan56 said:
Thanks, was actually using this today.
Click to expand...
Pleasure. I'll be publishing an updated project with these code changes including LiftM implementation for Maybe, IEnumerable, Either, Validation and also for some types I haven't covered yet Identity, Reader, Writer and depending on time quite possibly also the:
  • State monad,
  • State / Action / Reducer, Transducer patterns.
...and also a few more combinators functions; e.g. syntactic sugar to define Lambda functions and actions.

If future I'll also be introducing the concept of transformers i.e. computations that allow us to utilise transforms that allow transitions between the different data types and / or for inversion of embedded data types List of Maybe elements.

I also have on the radar Functional Optics, like Lenses, Prisms, ... which are essentially getters and setters on steroids.
 
Last edited:
That pretty much covers the purpose of this short thread. I'll be sharing a link to an updated project including these code examples in the coming week.

As an extra bonus bit of code I will be hopefully in the coming week be sharing a working example of a FP computation structure that kind of emulates a Free Monad. I say emulate because due to the limitations of C# generics we can't model a generic Free Monad data type in C#. The code example should however help you to at least understand how a Free Monad differs from a standard covariant Monad like SelectMany and FlatMap.
 
Last edited:
...as an added bonus let's explore the difference between C#'s Nullable type and our FP Maybe type. Nullable has some really nice syntactical affordances; for example, we can define a variable as int? which is the same as Nullable<int>; secondly it supports conditional evaluation by using the ? operator and also null coalescing using the ?? operator.

So why do we need Maybe if we have Nullable?
If we compare the purpose of Maybe to Nullable, we will find a lot of similarities:
  • Both types are generic over a single element type, Maybe<T> versus Nullable<T>
  • Both types are essentially sum types that either have some value or none aka null.

Let's compare the basic internal structure of each
To test this conclusion, let's compare the internal type definition for Maybe against Nullable.

Maybe
C#: 
public readonly struct Maybe<A> : IEquatable<Maybe<A>> {
    internal readonly A value;
    private enum State {
      None, Some
    }
    private readonly State state;
    ...
}

Nullable
C#: 
public struct Nullable<T> where T : struct    {
  private bool hasValue;
  internal T value;
  ...
}

Aside for the subtle difference in how state is tracked; enum versus bool these two types are essentially the same because they both are a struct that is generic over a single type, and they store a single generic value.

So why do we not just use Nullable instead of Maybe?
We could essentially add on all the missing FP parts to Nullable using extension methods, for example:
C#: 
// Add an extension method for Map i.e. functor conformance
public static U? Map<T, U>(this T? @this, Func<T, U> f) {
  return @this.HasValue ? f(@this.Value) : default;
}
There's a problem though; this code won't compile? The compiler raises the following errors:
  • Error CS0453: The type 'U' must be a non-nullable value type in order to use it as parameter 'T' in the generic type or method 'Nullable<T>'
  • Error CS0453: The type 'T' must be a non-nullable value type in order to use it as parameter 'T' in the generic type or method 'Nullable<T>'
...and if we look at the snippet of code for Nullable above, we can see why. T is constrained to a type of struct; which is not the case with Maybe.

So couldn't we just add this constraint to our Map method?
Sure, let's try that....
C#: 
public static partial class ƒ {
  public static U? Map<T, U>(this T? @this, Func<T, U> f)
    where T : struct
    where U : struct {
    return @this.HasValue ? f(@this.Value) : default;
  }
}
...and success this compiles without a problem, Nullable now conforms to the functor algebra.

Let's do some testing
C#: 
int? xcv = 6;
var xcv_r = xcv.Map(x => x + 1)
               .Map(x => x * 3);
Print(xcv_r); // 21
...and surprise, surprise that works perfectly, returning 21 as we would expect.

We can even support Linq syntax queries
C#: 
public static partial class ƒ {
  public static U? Map<T, U>(this T? @this, Func<T, U> f)
    where T : struct
    where U : struct {
    return ƒ.Map(@this, f);
  }
}

Let's test that with Linq
C#: 
int? xcv2 = 10;
var xcv2_r = from x in xcv2
             select x + 1;
Print(xcv2_r); // 11
...and again that works as expected, returning 11.

So far in everything looks great; so why do we have a Maybe type? On the surface everything appears to be ok, but it's actually not. The type constraints i.e. where T : struct and where U : struct are problematic.

To demonstrate this let's look at another usage example for Nullable's new Map extension method:

C#: 
int? xcv = 6;
var xcv_r = xcv.Map(x => x + 1)
               .Map(x => x * 3)
               .Map(x => x.ToString());
Print(xcv_r);
It's the same code as before, except now we have an additional Map call that converts x to a string, .... and oops, this again won't compile. The error is as follows:
  • Error CS0453: The type 'string' must be a non-nullable value type in order to use it as parameter 'U' in the generic type or method 'ƒ.Map<T, U>(T?, Func<T, U>)'
It won't work because the string type is class, and the Nullable type in it's definition has type constrained it's value to struct; which sadly means that our Map method is not all that useful, because we can only Map between other struct types. Our Maybe type does not have this restriction and hence can quite easily Map to any type we choose.

So why did Microsoft add this restriction to Nullable?
Surely the concept of boxing values in a type like Nullable is just as important for class types as it is for struct types?

...well guess what we're not the only one's who have asked this question before:
Nullable support for class types aka reference types is coming in C# 8.0. So theoretically we should be able to replace Maybe with Nullable in our C# 8.0 codebase. I haven't had a chance to test this yet; problem is that the current preview version available for Visual Studio for macOS has issues switching to the C# 8.0 compiler.

Update:
I have tested the changes that were introduced in C# 8.0 with regards to nullable support for reference types. and it works perfectly as long as we defined the extension methods with reference types constrained to class, for example:
C#: 
#nullable enable

public static partial class ƒ {
  public static U? MapToRef<T, U>(this T? @this, Func<T, U> f)
    where T : class
    where U : class {
    return (@this == null) ? null : f(@this);
  }

  public static U? MapToValue<T, U>(this T? @this, Func<T, U> f)
    where T : struct
    where U : struct {
    return ([email protected]) ? (U?)null : f(@this.Value);
  }

  public static U? MapToRef<T, U>(this T? @this, Func<T, U> f)
    where T : struct
    where U : class {
    return ([email protected]) ? null : f(@this.Value);
  }

  public static U? MapToValue<T, U>(this T? @this, Func<T, U> f)
    where T : class
    where U : struct {
    return (@this == null) ? (U?)null : f(@this);
  }
}
The only part which is not perfect is the way in which C# determines duplicate methods for method overloading; which means that to support mapping between value and reference types we have no choice but use a different Map method name to avoid the following error:
  • error CS0111: Type 'ƒ' already defines a member called 'Map' with the same parameter types
Which means we pick the Map method name by the output type, for example:
  • MapToRef for an output to a reference type from either an input of a value type or reference type.
  • MapToValue for an output to a value type from either an input of a value type or reference type.
Usage examples:
C#: 
string? name = "billy";
var result = name.MapToValue(x => x.Length); // 5

int? age = 24;
var result2 = age.MapToRef(x => x.ToString()); // "24"

Naturally we should be able to do the same for the Applicative Functor and Monad conformances; which essentially means it should be possible to avoid the need to use the Maybe type entirely.

I'll need to flesh this out to be sure. Only perceive issue at this stage is for Linq, where we are restricted to the method name Select and SelectMany.

Anyway hope you enjoyed this brief exploration of Nullable versus Maybe.

Note:
Both Swift and Kotlin call their Maybe type Optional
Rust calls it's Maybe type Option
...and all of them use the ? operator as syntactic sugar for defining Maybe types, and for chained evaluation.

...and if you were wondering where the concept of Maybe is derived from; it's from Haskell:
Click to expand...
 
Last edited:
Update for Nullable
We can use an optional defaulted parameter value as a work around for the extension method name clash:
  • error CS0111: Type 'ƒ' already defines a member called 'Map' with the same parameter types
Which allows use to overload all the variations required to Map between Nullable value types and Nullable reference types, for example:
C#: 
public static partial class ƒ {
  #region Functor
  public static U? Map<T, U>(this T? @this, Func<T, U> f) where T : struct where U : struct => ([email protected]) ? (U?)null : f(@this.Value);
  public static U? Map<T, U>(this T? @this, Func<T, U> f, bool arb = false) where T : struct where U : class => ([email protected]) ? null : f(@this.Value);
  public static U? Map<T, U>(this T? @this, Func<T, U> f) where T : class where U : struct => (@this == null) ? (U?)null : f(@this);
  public static U? Map<T, U>(this T? @this, Func<T, U> f, bool arb = false) where T : class where U : class => (@this == null) ? null : f(@this);
  #endregion

  #region Monad
  public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f) where T : struct where U : struct => ([email protected]) ? (U?)null : f(@this.Value);
  public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f, bool arb = false) where T : struct where U : class => ([email protected]) ? null : f(@this.Value);
  public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f) where T : class where U : struct => (@this == null) ? (U?)null : f(@this);
  public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f, bool arb = false) where T : class where U : class => (@this == null) ? null : f(@this);
  #endregion

  #region Linq Conformance
  public static U? Select<T, U>(this T? @this, Func<T, U> f) where T : struct where U : struct => @this.Map(f);
  public static U? Select<T, U>(this T? @this, Func<T, U> f, bool arb = false) where T : struct where U : class => @this.Map(f);
  public static U? Select<T, U>(this T? @this, Func<T, U> f) where T : class where U : struct => @this.Map(f);
  public static U? Select<T, U>(this T? @this, Func<T, U> f, bool arb = false) where T : class where U : class => @this.Map(f);
  #endregion
}
As you can see we've added 4 extensions methods per FP algebra conformance to deal with the struct to class and class to struct Map transformations, and on 2 of the Map methods we have added an Arb i.e. arbitrary parameter of type bool which has a default value of false, making it optional + it has no effect on the result, so it doesn't matter what is passed in.

Similarly I added extension methods for Monad conformance and Linq Select, and surprisingly Linq's syntax works perfectly fine even with the defaulted Arb parameter.

Usage Examples
C#: 
int? input = 6;
var result = input.Map(x => 1 + 1)
                  .Map(x => x * 3)
                  .Map(x => x.ToString()); // "21"
          
int? input2 = 10;
var result2 = from x in input2
              select (x + 1).ToString(); // "10"
      
Telephone? tel = new Telephone("abc", 12345);
var result3 = from t in tel
              select t.Category; "abc"
        
string? name = "billy bob";
var result3 = name.Map(x => x.Length); // 9

Naturally this can be extended to cover all the base algebras and the algebraic lifters LiftA and LiftM; and also the variants (function 1st, data type second); all of which I'll probably flesh out before sharing the updated project.

...and if you wondering, why do we even bother with this for something as trivial as a type that can either have a value / instance or be null; it's because it avoids the need for any conditional boiler plate if (abc != null) { ... } else { ... } when we want use and/or transform the element wrapped by our Nullable data type. Secondly it streamlines the API that we use to transform any element or data types in our codebase; meaning the win is not only for terseness but also readability. Thirdly this style of API aligns quite well with Kotlin, Rust and Swift implementations.
 
Last edited:
Further Update for Nullable
With regards to the this error:
  • error CS0111: Type 'ƒ' already defines a member called 'Map' with the same parameter types
Another solution is to separate the conflicting extension methods into 2 static classes; other than that I think it's a neater solution, and bonus we avoid the defaulted / unused parameter that would just end up making the API confusing.

Note:
If you were wondering how other languages typically deal with; they determine duplicates by examing the entire signature of the method including it's return type; whereas C# only evaluates the method name and input parameters.
Click to expand...

Here's the 2 sets of extension methods for this approach:
C#: 
  public static partial class ƒ {
    #region Functor
    public static U? Map<T, U>(this T? @this, Func<T, U> f) where T : struct where U : struct => ([email protected]) ? (U?)null : f(@this.Value);
    public static U? Map<T, U>(this T? @this, Func<T, U> f) where T : class where U : struct => (@this == null) ? (U?)null : f(@this);
    #endregion

    #region Monad
    public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f) where T : struct where U : struct => ([email protected]) ? (U?)null : f(@this.Value);
    public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f) where T : class where U : struct => (@this == null) ? (U?)null : f(@this);
    #endregion

    #region Linq Conformance
    public static U? Select<T, U>(this T? @this, Func<T, U> f) where T : struct where U : struct => @this.Map(f);
    public static U? Select<T, U>(this T? @this, Func<T, U> f) where T : class where U : struct => @this.Map(f);
    #endregion
  }

  public static partial class ƒ2 {
    #region Functor
    public static U? Map<T, U>(this T? @this, Func<T, U> f) where T : struct where U : class => ([email protected]) ? null : f(@this.Value);
    public static U? Map<T, U>(this T? @this, Func<T, U> f) where T : class where U : class => (@this == null) ? null : f(@this);
    #endregion

    #region Monad
    public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f) where T : struct where U : class => ([email protected]) ? null : f(@this.Value);
    public static U? FlatMap<T, U>(this T? @this, Func<T, U?> f) where T : class where U : class => (@this == null) ? null : f(@this);
    #endregion

    #region Linq Conformance
    public static U? Select<T, U>(this T? @this, Func<T, U> f) where T : struct where U : class => @this.Map(f);
    public static U? Select<T, U>(this T? @this, Func<T, U> f) where T : class where U : class => @this.Map(f);
    #endregion
  }

The reason I didn't consider this at 1st is because I typically use the public static partial class ƒ for 2 purposes; 1 is to create extension methods, and the 2nd reason is the create static syntactic sugar methods to simplify the use of the API, here is an example of the syntactic sugar for the Either type:
C#: 
public static partial ƒ {
    #region Syntactic Sugar - Just / None
    public static Maybe<A> Some<A>(A value) => Maybe<A>.Some(value);
    public static Maybe<A> None<A>() => Maybe<A>.None();
    public static Maybe<A> ToMaybe<A>(this A a) => Some(a);
    #endregion
}
...and we use this as follows:
C#: 
using static <namespace>.ƒ;

class MainClass {
  public static void Main(string[] args) {

    // Instead of declaring an Maybe like this:
    var input1a = May<int>.Some(24);

    // We can declare it like this
    var input1b = Some(24);

    // Or like this
    var input1c = 24.ToMaybe();
  }
}
So to retain this behaviour and not have to increase the number of using static ... statements at the top of our code; we can keep the syntactic sugar parts in 1 public static partial class and separate the extension methods in as many static classes as is required to avoid the naming conflicts; because for the most part we'll never refer to the static class that extension methods are declared in anyway.


Final Update on Nullable
I have concluded that whilst it's technically possible to extend Nullable to be as versatile as Maybe, it really is not a very practical one, and yes this is directly related to Microsoft's choice to treat Nullable different between value types and reference types. The problem relates specifically to the type constraints where value type must be constrained to struct and reference type constrained to class; which resulted in double the number of permutations of the functor, applicative functorand monad base algebras, but so too their Linq derivatives.

That's nothing, because the real "fun" :sick: begins when we try to define the Monadic Computational Lifters aka LiftM and similarly the Applicative Functor Lifters aka LiftA; these would result in an estimated total permutations of 660, and each would potential have a name clash, so we'd have to encapsulate each of them in a separate static class.

It's going to be messy and bloated to say the least. Definitely not something that looks to be worth the effort (to scribe manually), especially when we have a working Maybe that is substantially easier to maintain.

Here's an example of how convoluted the code becomes for LiftM with the type constraints, and this is only for everything as a struct; it certainly doesn't even broach the complexity of dealing with the varying permutations of struct and class across each generic derivative.

C#: 
    #region Monad - Lift a function & actions
    public static R? LiftM<A, B, R>(this Func<A, B, R> @this, A? a, B? b) where A : struct where B : struct where R : struct => a.FlatMap(m1 => b.FlatMap<B, R>(m2 => @this(m1, m2)));
    public static R? LiftM<A, B, C, R>(this Func<A, B, C, R> @this, A? a, B? b, C? c) where A : struct where B : struct where C : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap<C, R>(xc => @this(xa, xb, xc))));
    public static R? LiftM<A, B, C, D, R>(this Func<A, B, C, D, R> @this, A? a, B? b, C? c, D? d) where A : struct where B : struct where C : struct where D : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap<D, R>(xd => @this(xa, xb, xc, xd)))));
    public static R? LiftM<A, B, C, D, E, R>(this Func<A, B, C, D, E, R> @this, A? a, B? b, C? c, D? d, E? e) where A : struct where B : struct where C : struct where D : struct where E : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap<E, R>(xe => @this(xa, xb, xc, xd, xe))))));
    public static R? LiftM<A, B, C, D, E, F, R>(this Func<A, B, C, D, E, F, R> @this, A? a, B? b, C? c, D? d, E? e, F? f) where A : struct where B : struct where C : struct where D : struct where E : struct where F : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap<F, R>(xf => @this(xa, xb, xc, xd, xe, xf)))))));
    public static R? LiftM<A, B, C, D, E, F, G, R>(this Func<A, B, C, D, E, F, G, R> @this, A? a, B? b, C? c, D? d, E? e, F? f, G? g) where A : struct where B : struct where C : struct where D : struct where E : struct where F : struct where G : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap<G, R>(xg => @this(xa, xb, xc, xd, xe, xf, xg))))))));
    public static R? LiftM<A, B, C, D, E, F, G, H, R>(this Func<A, B, C, D, E, F, G, H, R> @this, A? a, B? b, C? c, D? d, E? e, F? f, G? g, H? h) where A : struct where B : struct where C : struct where D : struct where E : struct where F : struct where G : struct where H : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap<H, R>(xh => @this(xa, xb, xc, xd, xe, xf, xg, xh)))))))));
    public static R? LiftM<A, B, C, D, E, F, G, H, I, R>(this Func<A, B, C, D, E, F, G, H, I, R> @this, A? a, B? b, C? c, D? d, E? e, F? f, G? g, H? h, I? i) where A : struct where B : struct where C : struct where D : struct where E : struct where F : struct where G : struct where H : struct where I : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap<I, R>(xi => @this(xa, xb, xc, xd, xe, xf, xg, xh, xi))))))))));
    public static R? LiftM<A, B, C, D, E, F, G, H, I, J, R>(this Func<A, B, C, D, E, F, G, H, I, J, R> @this, A? a, B? b, C? c, D? d, E? e, F? f, G? g, H? h, I? i, J? j) where A : struct where B : struct where C : struct where D : struct where E : struct where F : struct where G : struct where H : struct where I : struct where J : struct where R : struct => a.FlatMap(xa => b.FlatMap(xb => c.FlatMap(xc => d.FlatMap(xd => e.FlatMap(xe => f.FlatMap(xf => g.FlatMap(xg => h.FlatMap(xh => i.FlatMap(xi => j.FlatMap<J, R>(xj => @this(xa, xb, xc, xd, xe, xf, xg, xh, xi, xj)))))))))));
    #endregion


I may reassess this if I find the time to code generate this, but for now it's on the backburner; .... however if someone is willing to take this on as challenge let me know. I'll help where I can.

I'll instead focus on making the transition between Nullable and Maybe far easier.
 
Last edited:
Nullable <==> Maybe Extension methods
Nullable's conformance to FP algebras is complicated by the fact that Microsoft C# treats value and reference type differently; these differences compound the number of permutations that are required to add the FP algebras; the worst being the support for Monadic Lifters and similarly for Applicative Functor lifters. The required type constraints is where this becomes unpractical without code generation.

For now these two extension methods provide an easy way to transition between Nullable and Maybe to take advantage of both Maybe's FP conformances, but also for the reverse to take advantage of Nullable syntactic sugar re the ? and ?? operators.

C#: 
  public static partial class ƒ {
    #region Syntactic Sugar
    public static Maybe<A> ToMaybe<A>(this A? @this) where A : struct => [email protected] ? None<A>() : Some(@this.Value);
    public static A? ToNullable<A>(this Maybe<A> @this) where A : struct => [email protected] ? (A?)null : @this.value;
    #endregion
  }


Usage Examples:
C#: 
int? xcv = 6;
var xcv_r = xcv.ToMaybe()
               .Map(x => x + 1)
               .Map(x => x * 3)
               .ToNullable();

int? xcv2 = 10;
var xcv2_r = (from x in xcv2.ToMaybe()
              select x + 1).ToNullable();

Note:
I have not include any provision currently for C# 8.0's support of reference type i.e. where constrained to class, because for the moment at least I am not able to properly test this. Which may mean that if we Map to a reference type that we won't be able to transition back without Nullable reference type support.
Click to expand...

However adding this support should be as easy as this:
C#: 
  public static partial class ƒ2 {
    #region Syntactic Sugar
    public static Maybe<A> ToMaybe<A>(this A? @this) where A : class => [email protected] ? None<A>() : Some(@this.Value);
    public static A? ToNullable<A>(this Maybe<A> @this) where A : class => [email protected] ? (A?)null : @this.value;
    #endregion
  }
 
Last edited:
Quick update:
I'm targeting to clean up the project that encompasses all of this code in this thread and share it by this weekend. However the promised simulated example of a free monad is postponed to a future thread, due to other free time priorities...

...at the moment I've allotted quite a bit of my free time to try to make sense of a new FP algebra, namely Selective Applicative Functors; an algebra that is pitched to fit in between the flexibility of a Applicative Functor and a Monad.

Extracted summary
Declare Your Effects Statically, Select Which to Execute Dynamically
...
Code: 
class Applicative f => Selective f where
    select :: f (Either a b) -> f (a -> b) -> f b
One can think of select as a selective function application: parametricity dictates that, when given a Left a, we must execute the effects in f (a -> b), apply the obtained function to a, and return the resulting b; on the other hand, when given a Right b, we may skip the effects associated with the function, and return the given b.

It has some interesting applications that need time to comprehend, understand and experiment with. If this type of stuff interests you at all, you can find the under review research paper here:
https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors.pdf
...and a working Haskell project here: https://github.com/snowleopard/selective
 
Last edited:
You must log in or register to reply here.
Back
Top
Sign up to the MyBroadband newsletter
X