Monads shmonads and functional programming
Pub
Share
I will be necessarily somewhat long, slightly wrong and mostly fuzzy while trying to introduce these concepts in just a page or two...
Monads (and related concepts from category theory, like Functor, Applicative etc) are the next level of abstraction in Functional Programming, beyond functions, but let's dive right in and progress through these concepts.
Functions
A function is basically a transformation: it turns an A into a B. In functional programming, one can take the function itself and do stuff with it, like composing it with other functions or passing it to other, higher-level functions.
Functions f : A => B allow you to think and program in a certain way: the functional programming way, where you can pass functions around to other methods like sort whatnot, such as list.sortWith(greaterThan). Once you get used to this functional programming, you can move on to higher types, higher functions and from there to monads.
There are many advantages to the functional style, my favourite being composability: it allows us to truly think in terms of composable sub-programs.
The functional style is also a perfect match for reactive programming.
Read more on functional programming, especially the section about what makes a good or pure function:
- no side effects
- referentially transparent
Functors
Functors F[A] lift a simple function to something more - the signature tells you their secret:
map[B] (f : A => B) : F[A] => F[B]
... they essentially gobble up your function f and return something higher level - pause and reflect on this for a second.
This map or fmap, you could think of it as taking a simple Unix command like sed s/Complex/Simple/ and apply it to something, as in cat blog.txt | sed s/Complex/Simple/.
In scala, you are used to a slightly different version of the same idea:
List(1,2,3) map (_ + 4)
Why are they useful? Many reasons...
For instance – you are normally "forbidden" from using state between two calls to f – you should know that by now. However, inside a functor you could, for the duration of the entire transformation F[A] => F[B]… you could have some state there… this is the beauty of an internalized iterator versus the one you’re used to. That state would be well encapsulated there in that transformation, so it could be used.
How that transformation is executed, is up to the specific functor you use. Some can optimize it, some can be dumb while some can use state (like cache a DB connection between calls or whatever).
Let’s have a quick random example: I could have my own functor, working on lists, which keeps the elements sorted. If I apply a random function to it, the result has to be also sorted. You can see the problem? my functor will keep it sorted while an externalized loop may or may not keep it sorted, depending on the programmer.
MySortedList (1,2,3) map (rand(_)) will always be sorted, while List (1,2,3) map (rand(_)) is not…
Without functions and functors, there is no way you could express and enforce that idea – I don’t think…
Read more on functors here.
Monads
Monads go even further than functors. Monads have certain laws which give them good properties which are very useful once you get used to thinking in these terms, you can look those laws up here.
Monads use an operation flatMap (in scala) rather than map, with a signature like the following:
flatMap (f : A => M[B]) : M[A] => M[B]
As you can see, they also return a transformation, but a yet higher level one, higher than functors, which includes flattening. But because it includes flattening, it can do both the transformation and the flattening in whichever way it wants. Flattening essentially turns an M[M[B]] into an M[B]... but it is not a separate operation, it is part of flatMap - now you can figure out the roots of the name, eh?
f:Neighbourhood => List[Person]
and then
val everyone = flatMap(f)(allNeighbourhoods).
Why monads are more useful than functors – look at the thing they're gobbling up: it’s an f : A => M[B] rather than f : A => B – the functors limit you to the shape of the functor, sort of speak – basically if you start with a list of ID’s you will end up with a list of Johns of the same size (or more or less, if the functor is cheating, like a Set would).
Monads are one better, you can start with a list of 5 student ID’s and end up with either 45 grades in a school year or 2 missing registrations… yes, f : A => B has to return exactly one and the same B for an A, while an f : A => M[B] could return for instance empty (called unit) he he…
F would return the number of people in each neighbourhood, we would always get a list of numbers from a list of Neighbourhoods, a list of the exact same size as the one with Neighbourghoods.
But the Monad ca return just the "bad apples", so then the resulting list is not tied to the size of the original list.
allBadApples = flatMap(badApple)(allNeighbourhoods).
Read more on monads.
Note on syntax
The world of monads and functors may be a funny one, especially when it comes to figuring out "who's the monad, man?"...
Instead of
map[B] (f : A => B) : F[A] => F[B]
and
flatMap (f : A => M[B]) : M[A] => M[B]
You will commonly see these signatures:
map[B] (f : A => B) : F[B]
and
flatMap (f : A => M[B]) : M[B]
The difference is that the ones we used earlier are a theoretically proper "functor" or "monad", i.e. decoupled from the underlying collection or shape while the ones just above use the type constructor of the class it belongs to complete the Functor/Monad. This is what you will see on a Seq or a List or such and it denotes the implicit Functor or Monad associated with that type.
Laziness
The first set of signatures is necessarily lazy, since they return another function, while the second set of signatures not necessarily - in fact, the second set kind of implies that it's strict - it is up to the M[A] to implement any laziness, if possible.
Keep reading
There’s a lot more to it, as others are trying to convey – try to read as much as you can – there’s no one angle that makes it easy to jump to monad abstractions…
If you are confused by the signatures I used above, it’s ok – no, you don’t have to learn Haskell – there’s an entire series of blog posts to explain the gap...
Note that the random sample above is not kosher since rand() is not a pure function: it never returns the same B for a given A... but it makes a good point.
Consolidating older blogs: this was posted originally on Nov 2012.
See more in: Cool Scala Subscribe You need to log in to post a comment!