This [1] might help 'get it' with regards to monads. Very easy to digest.
You mention LINQ and the List abstraction. Yes IEnumerable<T> is a monad (LINQ isn't in itself - it [the grammar] is the equivalent of 'do' notation in Haskell). Monads are simply 'wrapper types' that follow a couple of rules:
1. You must be able to construct one from the un-wrapped value (return in Haskell, new List<T>(...) in C#)
2. It must implement the bind function.
If you understand 'map' (or Select in LINQ) then bind is very similar, except instead of returning a mapped version of the wrapped value, it returns a mapped version of the wrapped value, re-wrapped.
So in C# parlance (because I assume from your comment you use this daily):
IEnumerable<R> Map<T, R>(this IEnumerable<T> self, Func<T, R> mapper)
{
foreach(var x in self)
{
yield return mapper(x);
}
}
IEnumerable<R> Bind<T, R>(this IEnumerable<T> self, Func<T, IEnumerable<R>> binder)
{
foreach(var x in self)
{
foreach(var y in binder(x))
{
yield return y;
}
}
}
You may recognise that as SelectMany in LINQ. Select and SelectMany are special case function names in C# that allow the formation of LINQ expressions:
var res = from x in list
select x + 1;
Equates to:
var res = list.Select( x => x + 1);
And:
var res = from x in list1
from y in list2
select x + y;
Equates to:
var res = list1.SelectMany(x => list2.Select(y => x + y));
The result is a 'flattened' IEnumerable<T> - and that's why this is also known as flat-map.
It's been a while since I've done any Haskell, so forgive me if I get some of the syntax wrong here. But the LINQ statement above translates very similarly:
do x <- list1
y <- list2
return x + y
(I know there's a list comprehension syntax in Haskell, but I assume this is still right, Haskellers?)
The syntax is saying 'get the value out of its wrapper (the list) for me, so I can use it as-is (the add operation), then put the result back in a new wrapper'.
So why do we do all of this? It's so you can write the functions once that behave on the wrapped types, whether they're integers, strings or any type. The monad concept allows you to create a 'chain' of behaviour that from the outside is opaque, but internally it's operating on the raw wrapped values, as-is; and that makes all of the existing functions available. This is one of the key benefits.
A good analogy is to call them 'programmable semi-colons', because what makes each monad type what it is, is the behaviour of bind and return. So a list monad (as seen above) knows how to iterate the collection - so you don't have to write a for loop every time, an option monad knows when to not invoke the bind function if it's in a None state - so you don't have to test it yourself with an 'if' every time, the state monad knows how to propagate state changes - so you don't have to have extra context arguments on every function down the hierarchy, etc.
They remove boilerplate and capture common patterns. That is the other key benefit. At its core is an abstract idea, and I think that's why it's sometimes quite hard to grasp; but it's just a design pattern. Forget the category theory side of it, you don't need to know any of that to use use them or write new ones.
If you're more used to C# than Haskell, then you may want to check out my 'C# functional language extensions' library [2] that has C# implementations of the following monads:
Option
Either
State
Reader
Writer
And a few others, but that should be enough to get started. It may help you get your head around it in a language you're more familiar with?
Thanks for taking the time to write all that up. I think (too early to say) that seeing all this expressed in C#/Java(script)/Ruby/Python syntax is key for someone like me.
I learned LINQ/Select(Many) and later all the map/filter/reduce functional goodness by playing with Clojure and never had a problem and never heard the word "monad" and was fine, totally fine.
Later watching a video on Rx (MS's reactive extensions) and hearing Erik Meijer talk about monads and Haskell and how Rx was inspired by that is what led me to try to learn Haskell. I just didn't see the "connection" between the functional and reactive patterns I was applying daily without any kind of mental problem and the Haskell stuff which was supposedly "the same", yet so....abstract?
I need to read your sample code and the links more carefully, but maybe this is the "key" I was lacking. Thanks !!!!
My pleasure. I guess to help a bit more (because the list monad tends to be easier to comprehend) is to see how other types are implemented. So here's a very basic implementation of the Option/Maybe monad:
public class Option<T>
{
public readonly bool HasValue;
public readonly T Value;
internal Option(bool hasValue, T value)
{
HasValue = hasValue;
Value = value;
}
public Option<U> Select<U>(Func<T, U> map) =>
HasValue
? Option.Some<U>(map(Value))
: Option.None<U>();
public Option<V> SelectMany<U,V>(Func<T, Option<U>> bind, Func<T,U,V> project) =>
HasValue
? bind(Value).Select(u => project(Value,u))
: Option.None<V>();
}
public static class Option
{
public static Option<T> Some<T>(T value) =>
new Option<T>(true, value);
public static Option<T> None<T>() =>
new Option<T>(false, default(T));
}
The SelectMany implementation is slightly more complicated than I showed before. This is an optimisation that C# does to group the bind and map together. So it may look slightly scary as a function. But hopefully you can see that if the Option<T> has a value then it first invokes bind, then uses the result of the bind (an Option<U>) to project the final result. Here's a more imperative version of it:
public Option<V> SelectMany<U, V>(Func<T, Option<U>> bind, Func<T, U, V> project)
{
if (HasValue)
{
var u = bind(Value);
if (u.HasValue)
{
return Option.Some(project(Value, u.Value));
}
else
{
return Option.None<V>();
}
}
else
{
return Option.None<V>();
}
}
You can see that with the IEnumerable<T> version of Select and SelectMany it encapsulates list iteration. With the Option monad it doesn't do that. It instead checks the HasValue field, and if it's false then it doesn't run the map or bind functions.
The second static class: Option, contains the 'return' functions: Some or None. These wrap a value of type T in an Option<T>.
Now if we use Option<T> in a LINQ expression:
var option1 = Option.Some(10);
var option2 = Option.Some(10);
var none = Option.None<int>();
var res1 = from x in option1
from y in option2
select x + y;
// res1.HasValue == true res1.Value == 20
var res2 = from x in option1
from y in none
select x + y;
// res2.HasValue == false
var res3 = from x in none
from y in option2
select x + y;
// res3.HasValue == false
This is the same as using do notation in Haskell:
do x <- option1
y <- option2
return (x + y)
If we were to do that imperatively it would look like this:
var res = Option.None<int>();
if( option1.HasValue )
{
if( option2.HasValue )
{
res = Option.Some(option1.Value + option2.Value);
}
}
Clearly more cluttered and error prone and importantly, not composable. This is where the notion of 'programmable semi-colons' comes from. It appears that the monad is running behaviour 'between the lines', and it is.
Hopefully that clears the fog. I'll keep an eye on this thread for a few days, so feel free to drop any questions in here or on my project page.
You mention LINQ and the List abstraction. Yes IEnumerable<T> is a monad (LINQ isn't in itself - it [the grammar] is the equivalent of 'do' notation in Haskell). Monads are simply 'wrapper types' that follow a couple of rules:
1. You must be able to construct one from the un-wrapped value (return in Haskell, new List<T>(...) in C#)
2. It must implement the bind function.
If you understand 'map' (or Select in LINQ) then bind is very similar, except instead of returning a mapped version of the wrapped value, it returns a mapped version of the wrapped value, re-wrapped.
So in C# parlance (because I assume from your comment you use this daily):
You may recognise that as SelectMany in LINQ. Select and SelectMany are special case function names in C# that allow the formation of LINQ expressions: Equates to: And: Equates to: The result is a 'flattened' IEnumerable<T> - and that's why this is also known as flat-map.It's been a while since I've done any Haskell, so forgive me if I get some of the syntax wrong here. But the LINQ statement above translates very similarly:
(I know there's a list comprehension syntax in Haskell, but I assume this is still right, Haskellers?)The syntax is saying 'get the value out of its wrapper (the list) for me, so I can use it as-is (the add operation), then put the result back in a new wrapper'.
So why do we do all of this? It's so you can write the functions once that behave on the wrapped types, whether they're integers, strings or any type. The monad concept allows you to create a 'chain' of behaviour that from the outside is opaque, but internally it's operating on the raw wrapped values, as-is; and that makes all of the existing functions available. This is one of the key benefits.
A good analogy is to call them 'programmable semi-colons', because what makes each monad type what it is, is the behaviour of bind and return. So a list monad (as seen above) knows how to iterate the collection - so you don't have to write a for loop every time, an option monad knows when to not invoke the bind function if it's in a None state - so you don't have to test it yourself with an 'if' every time, the state monad knows how to propagate state changes - so you don't have to have extra context arguments on every function down the hierarchy, etc.
They remove boilerplate and capture common patterns. That is the other key benefit. At its core is an abstract idea, and I think that's why it's sometimes quite hard to grasp; but it's just a design pattern. Forget the category theory side of it, you don't need to know any of that to use use them or write new ones.
If you're more used to C# than Haskell, then you may want to check out my 'C# functional language extensions' library [2] that has C# implementations of the following monads:
Option
Either
State
Reader
Writer
And a few others, but that should be enough to get started. It may help you get your head around it in a language you're more familiar with?
[1] http://adit.io/posts/2013-04-17-functors,_applicatives,_and_...
[2] https://github.com/louthy/language-ext