South Africa’s biggest forum. Discuss, discover, and connect with thousands of members.
![[)roi(]](/forum/data/avatars/m/8/8711.jpg?1563828683){kind=avatar}
if (predicate) { ... }foreach (var element in collection) { ... }try { ... } catch (Exception e) { ... }public static int Increment(int x) => x + 1;
public static int Square(int x) => x * x;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.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]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.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.Select statement.public static List<int> IncrementM(int x) => new List<int> { x + 1 };
public static List<int> SquareM(int x) => new List<int> { x * x };int, which we similarly increment and square, however we now return a new List encapsulating the result.Select when it comes to processing these two functions.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)
*/.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..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 2var 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, ...
}
}var result2 = numbers
.Select(IncrementM) // [[2], [3], [4], [5], [6]]
.Select(x => x.Select(SquareM)); // [[[4]], [[9]], [[16]], [[25]], [[36]]]Select, the more deeply entangled our result becomes, and the more loops we'll have to execute for any proceeding computation..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.Linq, Microsoft has used a different name for a monad, so instead of FlatMap, the extension method is called SelectMany:var result3 = numbers
.SelectMany(IncrementM) // [2, 3, 4, 5, 6]
.SelectMany(SquareM); // [4, 9, 16, 25, 36]
Console.WriteLine("[{0}]", string.Join(", ", result3));List, only to remove it when we flatten the result at the end, from a 2D Array to a 1D Array.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.
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.
My pleasure; happy to hear it's helpful.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.
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.
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.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:Monad's function signature facilitates this.Functor and a Monad:public IEnumerable<B> Map<A, B>(this IEnumerable<A> @this, Func<A, B> f) => ...
public IEnumerable<B> FlatMap<A, B>(this IEnumerable<A> @this, Func<A, IEnumerable<B>> f) => ...
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.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.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:IEnumerable with element(s)Empty IEnumerable; with no elementIEnumerable 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.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 ExceptionMonad 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.IEnumerable would be empty, so any subsequent computations would be skipped because iterating over an empty IEnumerable is the same as avoiding the computation entirelytry catch all subsequent imperative computes would be skipped, because the computation would jump into the catch block.if else statement that checks for a null or some other predicate.Monad a bit. 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.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...monad to manipulate the state of an array allows to model some useful computations.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, 5monad function takes a predicate of A and returns a function that takes A and returns an IEnumerable<A>; a monadic function signatureIEnumerable containing an element when the Predicate is trueIEnumerable when the Predicate is false.IEnumerable, and the SelectMany / FlatMap performs a Flatten after the Map -- the flatten process removes any empty IEnumerables.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]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]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.Compose extension method: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]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);a -> m ba 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.IncrementM is an IEnumerable<int> and SquareM requires an input parameter of an int.Kleisli Composition which in Haskell is defined as the <=< operator (or fish operator).a -> m b, and composes them monadically, passing the input to the 1st function, then binding the output from that to the 2nd function.SelectMany / FlatMap.public static Func<IEnumerable<A>, IEnumerable<B>> SelectMany<A, B>(this Func<A, IEnumerable<B>> f) => a => a.SelectMany(f);Kleisli Composition.// 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());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.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]Filter, IncrementM and SquareM are reduced to a single function, executing in a single SelectMany, optimising away unnecessary compute cycles.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>());