Functional Thread 10 : Monadic Composition

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,932
In the thread on Lazy Transformations we explored using a combination unary function composition together with Yoneda / Coyoneda data types to transform a type for lazily evaluation of transformations in order to avoid unnecessary compute operations.

In this thread we'll be looking at how to achieve the same for monadic computations; I'll start with a short refresher of what are monadic computations and why they are important algebra in Functional Programming.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,932
Monads

From Wikipedia
In functional programming, a monad is a design pattern that allows structuring programs generically while automating away boilerplate code needed by the program logic. Monads achieve this by providing their own data type, which represents a specific form of computation, along with one procedure to wrap values of any basic type within the monad (yielding a monadic value) and another to compose functions that output monadic values (called monadic functions).

This allows monads to simplify a wide range of problems, like handling potential undefined values (with the Maybe monad), or keeping values within a flexible, well-formed list (using the List monad). With a monad, a programmer can turn a complicated sequence of functions into a succinct pipeline that abstracts away auxiliary data management, control flow, or side-effects.

Both the concept of a monad and the term originally come from category theory, where it is defined as a functor with additional structure.[a] Research beginning in the late 1980s and early 1990s established that monads could bring seemingly disparate computer-science problems under a unified, functional model. Category theory also provides a few formal requirements, known as the monad laws, which should be satisfied by any monad and can be used to verify monadic code.

What is a monad?
Wikipedia has certainly improved upon their description of monads; it is still however what I would consider a very generalised and high-level description; meaning I don't think it practical helps the understand; so my addition to this will focus more on the practical explanation of monads.

A monad is at its root an abstraction of repeating patterns of behaviour in program logic; for example:
C#:
if (predicate) { ... }
...but and also less explicitly with iteration...
C#:
foreach (var element in collection) { ... }
...and also far less concretely in patterns like exception handling:
C#:
try { ... } catch (Exception e) { ... }
It can essentially be thought of as an abstraction of a process with a binary outcome; a parcel of code that depending on the outcome of a compute will branch either between a happy path and failure path. A end to end monadic process more so abstractly models an interdependency between processes.

The fact that the monad abstraction is tied to such basic parcels of code is why the monad pattern is diversely applicative, because it's essentially a refactoring out of a set of repeating patterns that many would not typically ascribe as code repetition.

The low level nature of this abstraction also means that the implementation of the monad pattern will vary based on the data type, however as we are modelling a repeating behaviour, the operation will be consistent, in as much as all the implementations of a monad will need to pass a single set of algebraic laws to ensure behavioural consistency.

In the next post I will show a few monadic functions, in order to help you become more familiar with the difference between the function signature a monad function versus a signature of a more traditional function. More so I will use the opportunity to hopefully further expand your understanding of what is a monad, by trying to explain what happens under the covers, and in turn hopefully convey why this abstract nature of the monad algebra perfectly encapsulates the logic patterns I referenced as examples above.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,932
A monad is like a functor with but with a subtle but abstractly powerful difference, and as usual an example will help to highlight that difference.

Let's start by looking at the behaviour of a Functor

Let's define two functions:
C#:
public static int Increment(int x) => x + 1;
public static int Square(int x) => x * x;
Next let's explore how we can use these two function with the List data type; I've selected the List data type because it is one of the types that Microsoft has conformed to algebras like Functor and Monad -- it all happens with the seemingly magical addition of the Linq framework.

Let's define a list of integers and transform it with our two functions:
C#:
var numbers = new List<int> { 1, 2, 3, 4, 5 };
var result1 = numbers
   .Select(Increment) // [2, 3, 4, 5, 6]
   .Select(Square); // [4, 9, 16, 25, 36]

Console.WriteLine("[{0}]", string.Join(", ", result1));
// [4, 9, 16, 25, 36]
Linq's Select extension method is an implementation of the Functor algebra for the List data type. In other languages and/or implementation this is more typically called map or fmap.

In short Linq's Select, aka Functor iterates over the elements in numbers and applying a transformation to the elements, for example: Increment function to increment each of the elements in numbers and then a separate Select to Square the result of the increment.
The comments are reflective of the end result of each Select statement.

This whilst being a powerful feature; replacing the need for many loops; has a specific limitation with regards to the type of transformations that are possible.


Let's illustrate the limitation of a functor
...by subtly adjusting the signature of the previous two functions.

C#:
public static List<int> IncrementM(int x) => new List<int> { x + 1 };
public static List<int> SquareM(int x) => new List<int> { x * x };
We now have two functions that similar the previous functions require an input of a single parameter of type int, which we similarly increment and square, however we now return a new List encapsulating the result.

Why this is needed will become apparent later on; let's for now just explore the limitation of Select when it comes to processing these two functions.

C#:
var result2 = numbers
   .Select(IncrementM) // [[2], [3], [4], [5], [6]]
   .Select(SquareM); // Error CS0411

/*
Error CS0411:
The type arguments for method 'Enumerable.Select<TSource, TResult>(IEnumerable<TSource>, Func<TSource, TResult>)'
cannot be inferred from the usage.
Try specifying the type arguments explicitly. (CS0411) (Compositional)
*/
The 1st .Select(IncrementM) operation worked just fine, returning a 2D Array structure containing our incremented values. The 2nd .Select(SquareM); fails with a CS0411 error; which really doesn't help to explain the problem. To understand; we need to examine what elements the SquareM function is being provided by Linq's Select. As I said previously Select can be thought in the same way as a loop iterating over the internal elements.

The error occurs because of the output of the .Select(IncrementM) which unlike the previous functions has embedded the computed values in a internal List; meaning that the input to our 2nd Select operation is a List<int>; from a List within a List, this in turn mean that our 2nd Select is passing a List containing a 2 to the SquareM function; which is incompatible; because it expects just a 2

As the following example demonstrates; we need a 2nd loop to get at the elements in a 2D array:
C#:
var input = new List<List<int>> {
    new List<int> { 2 },
    new List<int> { 3 },
    new List<int> { 4 },
    new List<int> { 5 },
    new List<int> { 6 }
};

foreach (var element in input) {
  // element is a List<int>, so to access the value inside we would need another loop
  foreach (var innerElement in element) {
    // now we have access to 2, 3, ...
  }
}
In Linq, we can modify our code to do this as follows:
C#:
var result2 = numbers
  .Select(IncrementM) // [[2], [3], [4], [5], [6]]
  .Select(x => x.Select(SquareM)); // [[[4]], [[9]], [[16]], [[25]], [[36]]]
Which works, but the 3D array structure of the result should be indicative of a growing problem, the more we execute functions of this type of signature with Select, the more deeply entangled our result becomes, and the more loops we'll have to execute for any proceeding computation.

So how do we fix this.
If you look at the difference between the result from the 1st .Select(IncrementM) and the previous example using the more traditional function signature .Select(IncrementM); you should agree the problem is that the IncrementM version returns as an List within an List, and an easy way to get the IncrementM version to return the same result, would be to flatten the result from a 2D Array to a 1D Array -- which surprise, surprise is exactly what a Monad does; hence it's more formally called a FlatMap; an transformative operation like Map / Select, except that it flattens the structure at the end; making our 2D array into a 1D Array.

Here's the same process using FlatMap:
In Linq, Microsoft has used a different name for a monad, so instead of FlatMap, the extension method is called SelectMany:
C#:
var result3 = numbers
   .SelectMany(IncrementM) // [2, 3, 4, 5, 6]
   .SelectMany(SquareM); // [4, 9, 16, 25, 36]

Console.WriteLine("[{0}]", string.Join(", ", result3));
You're probably again wondering why this is important and why one would ever want to construct a function that returns a value embedded in a List, only to remove it when we flatten the result at the end, from a 2D Array to a 1D Array.

The first thing to acknowledge is that Monad being an abstract concept is going to mean that the reason is also a bit abstract; and will require a bit more explanation and examples to clarify. However I will say bear with me, because this seemingly abstract and pointless behaviour is what underpins the power of the Monad, and is the very reason why it's such a powerful concept and applicable for a wide variety of computing problems.

Next Post
The next post will examine this abstract behaviour of the Monad and will hopefully finally reveal for you a bit of the hidden power behind monadic operations. I'll most certainly explain why functions being able to return a result embedded in a data type is important, and why this behaviour allows us to model any imperative computing process using monadic functions.
 
Last edited:

Johnatan56

Honorary Master
Joined
Aug 23, 2013
Messages
24,955
You're probably again wondering why this is important and why one would ever want to construct a function that returns a value embedded in a List, only to remove it when we flatten the result at the end, from a 2D Array to a 1D Array.
Hah, I had a problem like this a few days ago, pretty nice that you're writing up this explanation, you seem to be spying on my code. :p
Thanks though for all the functional threads, I've learnt a lot through them and I find your explanations a lot better than most other places.
 

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,932
Hah, I had a problem like this a few days ago, pretty nice that you're writing up this explanation, you seem to be spying on my code. :p
Thanks though for all the functional threads, I've learnt a lot through them and I find your explanations a lot better than most other places.
My pleasure; happy to hear it's helpful.

Here's another bonus:
I've recently made the decision to open source a new repository incorporating most of the functional API I use in production; shared as a set of Nugets and a github repository. Practical caveat is that only the latest C# language syntax will be supported, for example: C# 7.0 / 8.0 and .Net Core 2.2 and 3.0

Being that its a relatively new thing; a lot of the API is still WIP; but my ultimate goal is to tie most of my production code to this once it's a lot closer to feature complete.

The following parts can be considered "feature complete":
  • Identity - The Identity type is a trivial type to access functor, monad, applicative functor, etc. algebras.
  • Maybe - The Maybe type encapsulates an optional value. A value of type Maybe a either contains a value of type a (represented as Just a), or it is empty (represented as Nothing)
  • Result - The Result type is similar to the Either type except that the left disjunction is fixed to capture of a C# Exception.
  • Either - The Either type encapsulates a logical disjunction of two possibilities: either Left or Right.
  • Validation - The Validation data type is isomorphic to Either, but has an instance of Applicative that accumulates on the error side.
They all include conformance for the Monoid, Functor, Monad, Applicative Functor, Traverse, Sequence, Kleisli algebras and also are operable with Linq's query syntax, for example:

from xxx in yyy
select xxx;
The following types are a rough draft (WIP)
  • Reader - The Reader type (also called the Environment monad). Represents a computation, which can read values from a shared environment, pass values from function to function, and execute sub-computations in a modified environment.
  • State - The State monad wraps computations in the context of reading and modifying a global state object.
  • Coyoneda - The Coyoneda is a contravariant functor suitable for Yoneda reduction.
  • Yoneda - The yoneda is a covariant Functor suitable for Yoneda reduction.
  • Tagged - The Tagged union type is comparable to Swift enums with generically associated values.
  • Store - The Store is modelled on the Redux concept.
  • Reducer - The Reducer is modelled on the Redux concept.
  • Subscriber - The Subscriber is modelled on the Redux concept.
  • Action - The Tagged type fulfils the role of the Action in the Redux concept.

The roadmap:
  • Add-ons / enhancements to Microsoft's API including for example: Linq's IEnumerable API, Task API, Nullable, Tuples, ImmutableList, etc.
  • A base static library including most of the common combinator functions that are used in Haskell.
  • Functionally designed wrapper APIs for 3rd frameworks for example: SQLClient, SQLite, Newtonsoft JSON, etc.
  • Functional Optics; covering Lens, Prisms, Telescope, ... essentially the Getters and Setters of immutable functional code.
  • Unit tests; including math rule based validation of the functional algebras.
  • etc...
Examples:
To bridge the divide I'm also planning to add:
  • A broad set of working examples of how to use these datatypes in a codebase
  • Github WIKI on Functional Programming.


Nuget:
https://www.nuget.org/packages?q=endofunk

Github repository:
https://endofunk.github.io/Endofunk-FX/
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,932
Abstract behaviour of a Monad
Picking up from the previous post on Monads; let's try to make some sense of the abstract behaviour of the Monad in order to understand why it's a perfect algebra to safely model an imperative computation.

In order to understand why it's function signature is powerful requires us to first understand the state that data types encapsulate. An array data type encapsulates state that is separate from the type of elements it contains; it's state is a logical disjunction, it's state can be either:
  • Empty
  • Non empty; 1 or more elements

Which means that aside from manipulating the elements within the array; we can also manipulating the state -- because the Monad's function signature facilitates this.

Let's again compare the difference between the function signatures of a Functor and a Monad:

Functor (Select / Map):
C#:
public IEnumerable<B> Map<A, B>(this IEnumerable<A> @this, Func<A, B> f) => ...
Functor (map) 2.png



Monad (SelectMany / FlatMap):
C#:
public IEnumerable<B> FlatMap<A, B>(this IEnumerable<A> @this, Func<A, IEnumerable<B>> f) => ...
Monad (flatmap) 2.png

Both functions take an IEnumerable aka collection type or array, and both types are a higher order function; meaning they require a function for the transformation. The function is where the difference resides.

A Functor transforms an A into a B; or for example an int into a string. Whereas a Monad transforms an A into an IEnumerable<B>; or for example an int into a IEnumerable<string>. The B result for the monad is encapsulated in a data type.

This subtle difference in signatures is what gives the Monad more power; because not only can it manipulate the element A => B, but it also can manipulate the state, by return either an IEnumerable with an element, or an empty IEnumerable. This is the essence of the power of the Monad; because that behaviour is just what occurs with any imperative computation; which either returns what was expected, or returns nothing; for example:

Trying to open a file on disk, can either result in:
  • Success: IEnumerable with element(s)
  • Failure: Empty IEnumerable; with no element

Naturally an IEnumerable is not necessary the perfect data type for every imperative scenario; because it's state can only logically encode whether something succeeded (not empty) or failed (empty); it cannot for example tell us why something failed; because it's empty state has no provision to store a failure element.

This is where monadic types like Either or Result are more appropriate; because:
  • Either allows the failure (Left branch) to encapsulate any type you choose.
  • Result allows the failure to encapsulate a .Net Exception

The ability for a Monad to manipulate state has another hidden benefit; it encapsulates the logical result of an imperative computation in a functionally similar way to that of a if else, or foreach loop, or try catch, because the encapsulation of the logical disjunction ensures that a failure computation is not propagated onwards; meaning if a file could not be opened then the state of the Monad type indicates that.

For example:
  • IEnumerable would be empty, so any subsequent computations would be skipped because iterating over an empty IEnumerable is the same as avoiding the computation entirely
  • Similarly if something failed in a try catch all subsequent imperative computes would be skipped, because the computation would jump into the catch block.
  • It's also the same effect with an if else statement that checks for a null or some other predicate.

Hopefully that has helped to demystify the abstract nature of the Monad a bit.


Naturally this means that the Monad can be used in many different scenarios because it is an abstraction of a repeating pattern at such a low computational level. This is also why there are so many different monadic data types; because logical computations similarly have a high degree of variability.

Ultimately to know a Monad; is really all about learning the many ways to exploit it within your code; because the variations are quite diverse especially when used in conjunction with other algebras. That's really what the challenge of learning Monads is all about...

The challenge is to learn when and how to exploit Monads within your code.
Which is not dissimilar to any design pattern; the only difference with a monad is that unlike OOP design patterns, it has a wide and varying use case because it's an abstraction of a low level group of repeating computations.


In the next post
In the next post we'll look at how the ability of the monad to manipulate the state of an array allows to model some useful computations.
 
Last edited:

[)roi(]

Executive Member
Joined
Apr 15, 2005
Messages
5,932
Example of a Monad's ability to manipulate state?

To illustrate manipulation of state; lets look at the implementation for a monadic filter function.
C#:
public static Func<A, IEnumerable<A>> Filter<A>(Predicate<A> p) => a => p(a) ? Enumerable.Empty<A>().Append(a) : Enumerable.Empty<A>();

var numbers = new List<int> { 1, 2, 3, 4, 5 };
var result = numbers
  .SelectMany(Filter<int>(x => x % 2 != 0));

Console.WriteLine("[{0}]", string.Join(", ", result)); \\ 1, 3, 5
Filter is a monad function takes a predicate of A and returns a function that takes A and returns an IEnumerable<A>; a monadic function signature

The filter expression returns:
  • IEnumerable containing an element when the Predicate is true
  • An empty IEnumerable when the Predicate is false.

This works because elements that are not matched with the predicate, are returned as an empty IEnumerable, and the SelectMany / FlatMap performs a Flatten after the Map -- the flatten process removes any empty IEnumerables.


Using together with other Monadic functions
We can use our filter with the other monadic functions, for example:
C#:
var numbers = new List<int> { 1, 2, 3, 4, 5 };
var result = numbers
  .SelectMany(Filter<int>(x => x % 2 != 0))
  .SelectMany(IncrementM)
  .SelectMany(SquareM);

Console.WriteLine("[{0}]", string.Join(", ", result)); // [4, 16, 36]

We can also convert the filter's predicate to pointfree, for example:
C#:
public static Predicate<int> IsEven = x => x % 2 == 0;
public static Predicate<int> IsOdd = x => !IsEven(x);

var numbers = new List<int> { 1, 2, 3, 4, 5 };
var result = numbers
  .SelectMany(Filter(IsOdd))
  .SelectMany(IncrementM)
  .SelectMany(SquareM);

Console.WriteLine("[{0}]", string.Join(", ", result)); // [4, 16, 36]

Avoiding unnecessary iterations
A SelectMany function is like a loop in that it iterates over each of its elements; which implies that 3 SelectMany / FlatMap function calls imply that our computation loops over each of the elements 3 times.


Composition
With standard functions we can reduce compute cost by composing the functions into a single function that performs the combination of the computes; to simplify this for use we'll create a Compose extension method:
C#:
public static Func<A, C> Compose<A, B, C>(this Func<A, B> f, Func<B, C> g) => a => g(f(a));

public static Func<int, int> Increment = x => x + 1;
public static Func<int, int> Square = x => x * x;

var numbers = new List<int> { 1, 2, 3, 4, 5 };

var result = numbers
  .Select(Increment.Compose(Square));

Console.WriteLine("[{0}]", string.Join(", ", result)); // [4, 9, 16, 25, 36]

The same problem can occur with monadic computations
To avoid unnecessary computes with Monadic functions is a bit more tricky, because of the signature of the monadic functions, for example:

C#:
public static Func<int, IEnumerable<int>> IncrementM = x => Enumerable.Empty<int>().Append(x + 1);
public static Func<int, IEnumerable<int>> SquareM = x => Enumerable.Empty<int>().Append(x * x);

In Haskell this type of function is written generically as follows:
C#:
a -> m b
Where a and b are the generic type variables for the input and output element types, for example: int. The m variable indicates that the b is encapsulated in a monadic type, for example: IEnumerable.


Standard composition doesn't work
We can immediately see that these function signatures are incompatible with standard function composition, because the output of IncrementM is an IEnumerable<int> and SquareM requires an input parameter of an int.


Solution: Kleisli Composition
From Category Theory, Monads have available a special kind of composition called Kleisli Composition which in Haskell is defined as the <=< operator (or fish operator).

This operator takes 2 functions of the monadic form a -> m b, and composes them monadically, passing the input to the 1st function, then binding the output from that to the 2nd function.

The function form a -> m b is also btw called a Kleisli Arrow; and the composition of these Kleisli Arrows forms a category; a Kleisli Category. The name Kleisli comes from the mathematician that introduced them to the world of Category Theory; namely Heinrich Kleisli.

Ok, so how do we get these two monadic functions to compose?
We firstly have to define a special extension function signature variation for SelectMany / FlatMap.
C#:
public static Func<IEnumerable<A>, IEnumerable<B>> SelectMany<A, B>(this Func<A, IEnumerable<B>> f) => a => a.SelectMany(f);
Next we need the standard form of function composition and a special variation for Kleisli Composition.
C#:
// Standard function composition extension method
public static Func<A, C> Compose<A, B, C>(this Func<A, B> f, Func<B, C> g) => a => g(f(a));

// Kleisli function composition extension method, using the new SelectMany variation
public static Func<A, IEnumerable<C>> Compose<A, B, C>(this Func<A, IEnumerable<B>> f, Func<B, IEnumerable<C>> g) => f.Compose(g.SelectMany());
The expression in the Kleisli Composition is composing the 1st monadic function with the 2nd one, except that on the 2nd function we dot chain our special variation of SelectMany / Flatmap; which converts our g function signature from Func<B, IEnumerable<C>> to Func<IEnumerable<B>, IEnumerable<C>>, making it compatible with the output from the 1st function, and hence standard composition will now works as expected.


Let's see that in practice
C#:
var numbers = new List<int> { 1, 2, 3, 4, 5 };
var result = numbers
  .SelectMany(Filter(IsOdd).Compose(IncrementM).Compose(SquareM));

Console.WriteLine("[{0}]", string.Join(", ", result)); // [4, 16, 36]
This ensure that the combination of Filter, IncrementM and SquareM are reduced to a single function, executing in a single SelectMany, optimising away unnecessary compute cycles.


BTW the filter can also be implemented as an extension method:
C#:
public static IEnumerable<A> Filter<A>(this IEnumerable<A> @this, Predicate<A> p) => @this.SelectMany(a => p(a) ? Enumerable.Empty<A>().Append(a) : Enumerable.Empty<A>());

Final Point:
Algebras like Coyoneda and Kleisli Compositions can be used to optimise your code and/or add lazy evaluation implementations for your monadic data types.
Standard .Net code is eagerly evaluated by default; however you should be aware that Microsoft has enabled lazy evaluation for its IEnumerable Linq implementation; meaning that Linq by default minimises the compute cost across multiple Linq statements.
 
Last edited:
Top