Monad Data Structures

[00:00:00]
>> Kyle: Now that you're feeling more comfortable with the idea of operations at a data structure level, we're gonna zero in on, perhaps one of the most famous of all the functional programming confusions out there, which is the Monad. And I'm gonna go ahead and tell you right now, this is the very first time that I've ever put this information into a course, because it's a set of information, a set of learnings that is continually evolving for me.

[00:00:26]
And this is by no means, an exhaustive look at all things monad, it's not the mathematical approach, but I just want essentially to get it so that monads are not a scary thing. I just wanna demystify the concept of a monad, because it is not, as so many people have said, a burrito or an onion, or any of these other silly sorts of metaphors.

[00:00:48]
And it's also not some sort of scary concept that we have to run away screaming. It is a very useful concept in the larger canon of functional programming theory. And really what it boils down to is that a Monad is a way of creating a functional, friendly data structure.

[00:01:06]
We've looked at lists, we've looked at objects, we could talk about binary trees, but another kind of data structure is one that might hold just one single discreet value. And you might think, why do I need a data structure for one single discrete value like the number 42?

[00:01:21]
And the reason is, because data structures are not just about the values they hold, but about the behaviors that they create around those values. A monad is a wrapper, if you will, around the value with a set of behaviors in it that is going to make that value much easier to interoperate with other values in a very specific kind of way.

[00:01:43]
One of the characteristics of a monad is that it turns that single value into a functor. That's not the completeness of a monad, but it does turn that value into a functor. Remember that term, I said it earlier when we were talking about lists and I said, any value where we can map an operation over it is a functor.

[00:02:03]
So if a monad has a map method on it, then it's a functor. What might we wanna do with a single value in a map? We might wanna transform that value into some other value, that's a way of modeling state change, where I have a value and it becomes another value, we can model that as a mapping operation.

[00:02:24]
I know some of you have heard this term before, monad is just a monoid in the category of endofunctors, and that's generally thrown around as kind of like a joke, because it's like, how many crazy weird words can we throw into a sentence and still be valid? I don't think that's an useful definition, I know that it actually means something to functional programmers.

[00:02:45]
But I don't think it's an useful definition, cuz it uses a lot of things that none of us are familiar with. First of all, we barely can understand that a monad is a data structure, and then we throw in monoid, what's that? And then category, crap, we're talking about category theory, and now endofunctors?

[00:03:01]
I heard you say functor, but what on earth is an endofunctor? That sounds like a planet in the Star Wars movie, okay? That's not a real thing that we could connect to something that we have any sort of intuition about. So this is a bad definition, but let me try to give you a lamer or a more approachable sort of definition.

[00:03:20]
It's just a pattern for pairing some piece of data with a set of predictable behaviors that let it interact with other pairings of data and behavior, in other words monads. So monads are a way to take a value and make it behave in such a way that is gonna be predictable with other values that are also monads.

[00:03:41]
It's not actually that scary, it's just a set of formalized techniques for making values easy to interact in a very specific, and it turns out mathematical sort of a way. Now, monads in languages like Haskell have a very specific way of looking. When we're in a non functional programming language like JavaScript, we have to do a bit of interpretation.

[00:04:04]
And there are actually a lot of different ways that I could code up a monad, and different kinds of monads, obviously, but there's a lot of different ways that I could code up a monad. And I just wanna tell you right off the bat, that I'm definitely being very informal here, as informal as I can do and still be even remotely true to the spirit of a monad.

[00:04:24]
So this is not code that I want you to go take and put in production, and then say, hey everybody, I've got a full blown monad. You wanna use a library that has implemented these things and has all of the is dotted and ts crossed in terms of working with stuff, but I just want to illustrate this concept of a monad.

[00:04:43]
And I've got a code snippet here, but you'll notice I've got a bunch of code hidden right now, because what I want you to see, I'm showing you the first of, this is maybe the most basic of the monads that we could talk about, which is called, Just, it's literally called, Just.

[00:04:59]
And what Just is as a monad, is just a wrapper around a single value. Now that single value can be even something like an object or an array, it doesn't have to be the number 42, but from the perspective of the monad it's a single discreet entity. And you might wanna do a thing where the single discreet entity to make it into another single discreet entity wrapped in a monad.

[00:05:23]
Just like with arrays, every time we do a map we get another array, if you do a monad and you call a map on it, you're gonna get another monad. Same sort of deal here. So, you'll notice that a Just instance, a monad that is a Just monad, has a map method, a chain method and an AP, an ap method.

[00:05:45]
That's it, those three. But there are definitely often more methods on different kinds of monads. But those are the kind of three core methods that are gonna be on all the monads, and by the way, chain is often referred to with other names. So how would we implement those map, chain and ap?

[00:06:05]
Before I even show you the implementation, I just want you to see, is just an object with three methods on it. And it's gonna be closed over a single value that we passed in, cuz those methods are gonna have closure and access to val from line 1. So it's just a value wrapped in some closure with three methods exposed.

[00:06:25]
It's not really that complex of a concept to be honest with you. It's really just a formalized way of making that value be able to interact with other values. Okay, let's take a look at how we might implement map, chain and ap. And remember, map, chain and ap here are definitely, I'm giving you the simplest shortcut way of illustrating what they do.

[00:06:49]
Here's a map function that takes a function, calls our closed over val, line 7, we call our closed over val with that function, and whatever that thing returns, we just make another Just out of it. Just like in an array map we have to make a new array in a monad map we have to make another monad, and the kind of monad that we're gonna make is the kind of monad that we're already in.

[00:07:14]
Arrays make arrays, objects make objects, monads make monads.
>> Kyle: So, if I had the number 42, and I'm not inside of a monad, and I called map on that monad with a mapper function that imcremented it, what am I gonna get? A monad that has 43 in it.

[00:07:35]
That's all that means, that's the functor nature of a monad, that we can map over that value and produce another monad from it. Now let's look at chain, again, chain kinda cutting some corners here, is not intended to be mathematically accurate, it's just to illustrate the idea here.

[00:07:52]
Chain is oftentimes referred to in other implementations as either bind, or sometimes, and I actually prefer, flatMap. We've talked about map before, but we haven't really talked about flatMap in this course, and I just wanna briefly mention what flatMap does. FlatMap is actually a strange name, because it's the reverse, it really ought to be called map flat.

[00:08:14]
Because what flatMap does is, it maps over a data structure and then, as it's doing that mapping, it's flattening it one level, what do I mean by flattening? Well, the best way for you to visualize that is with arrays. If I had a single dimensional array of numbers and I did a map over it, I'd end up with another single dimensional array of numbers.

[00:08:35]
But what if my mapper function returned back tuples? Instead of taking the number 3 and returning back 4, what if it returned back 4,5 for example? You know, an array or 4 and 5. Well, now I'd have a two-dimensional array, wouldn't I? I'd have an array of tuples, and you might want an array of tuples, but you also might want just one flat array of all the numbers having been combined.

[00:09:03]
So that flatMap is a way of taking that nested data type, like an array inside of an array, and flattening it out one level. So if our mapper returned tuples, and we did flatMap instead of map, we'd get just a single dimensional array of all the numbers kind of squished or flattened out into one big array.

[00:09:26]
So, when we talk about flatMap in terms of monad, that's like doing a mapping, getting a monad, and then flattening it out into the underlying value from the monad. Here I'm shortcutting, and just not even going to the trouble of making the monad, I'm just doing the FN call, and whatever it returns we're giving it out.

[00:09:49]
That's not technically true to the spirit of Monad but it gives you an idea that, if I call chain on a monad, I'm gonna get whatever the return value is of that mapper function. It's supposed to be another monad, but in this case we could end up not being another monad entirely, and then, that's where we'd start violating those monad laws.

[00:10:09]
The third one is ap, and this one is the strangest of all. This is one I really haven't fully wrapped my brain around, but I just want to give you a glimpse of how we know that ap is a little bit strange, because ap takes in another monad.

[00:10:24]
You say, monad1.ap and you pass in monad2, okay? But what we do with monad2, or in this case the another monad is, we call.map on it with our monad's value. So we call somebody else's map with our value. The thing that that should raise, that should be interesting in your brain is, what does map always require?

[00:10:56]
>> Kyle: No, what does map, whenever we call a map, what do we always pass to it? We always pass?
>> Speaker 2: An array?
>> Kyle: A mapper function, we always have to pass a mapper function to map, just like we always have to pass a predicate function to filter. So here we are passing our value to .map, line 16.

[00:11:17]
That implies that our value to use this has to be a function. That's the strange part, our value would not be able to be the number 42 or this would throw an error. Our number couldn't be an array, our value couldn't be a string, our value that our monad is wrapped around, if we call a .ap on it, we have to have a function as our value.

[00:11:42]
So what kind of function might we have in our monad? Well, we might have a curried function that's got some value remembered in it, and it's gonna be used as the mapper for another monad. So .ap is the strangest of the three in my opinion, map and chain seem to have a pretty straight forward intuition.

[00:12:04]
.App requires you to think about that currying thing, and we're gonna look at that in just a moment.