-
-
Save getify/2dc45c9a82cfd93358fbffd21bdd601d to your computer and use it in GitHub Desktop.
| // is Just(..) a monad? Well, it's a monad constructor. | |
| // Its instances are certainly monads. | |
| function Just(v) { | |
| return { map, chain, ap }; | |
| function map(fn) { | |
| return Just(fn(v)); | |
| } | |
| function chain(fn) { | |
| return fn(v); | |
| } | |
| function ap(monad) { | |
| monad.map(v); | |
| } | |
| } |
| // is Nothing() a monad? Well, it's a monad constructor. | |
| // Its instances are certainly monads. | |
| function Nothing() { | |
| return { map: Nothing, chain: Nothing, ap: Nothing }; | |
| } |
| // This is how Maybe(..) is usually implemented. | |
| // But Maybe(..) here doesn't construct pure/valid monad instances, | |
| // since its map() does a value-type check, which is a no-no. | |
| function Maybe(v) { | |
| return { map, chain, ap }; | |
| function map(fn) { | |
| if (v == null) return Nothing(); | |
| return Just(fn(v)); | |
| } | |
| function chain(fn) { | |
| return fn(v); | |
| } | |
| function ap(monad) { | |
| return monad.map(v); | |
| } | |
| } | |
| var identity = v => v; | |
| var prop = k => o => o[k]; | |
| var myObj = { something: { other: { and: 42 } } }; | |
| Maybe( myObj ) | |
| .map( prop("something") ) | |
| .map( prop("other") ) | |
| .map( prop("and") ) | |
| .chain( identity ); // 42 |
| // This is a more "pure" / accurate implementation of Maybe: | |
| // But, is Maybe here a monad? It's not even a constructor of a monad, | |
| // it's a namespace that holds methods that can make different kinds | |
| // of monads. | |
| var Maybe = { Just, Nothing, of: Just }; | |
| var identity = v => v; | |
| // we moved the empty check from Maybe into prop() | |
| var isEmpty = v => v == null; | |
| var prop = k => o => isEmpty(o[k]) ? Nothing() : Maybe.of(o[k]); | |
| var myObj = { something: { other: { and: 42 } } }; | |
| Maybe.of( myObj ) | |
| .chain( prop("something") ) | |
| .chain( prop("other") ) | |
| .chain( prop("and") ) | |
| .chain( identity ); // 42 |
PS the final example of the maybe monad, when I mentioned "bailing out" with Nothing, is very analogous to Promise.then returning a rejected promise.
promiseA
.then(returnsGoodPromise1) // runs
.then(returnsRejectedPromise) // runs
.then(returnsGoodPromise2) // does not run
.then(returnsGoodPromise3) // does not run
maybeA
.chain(returnsJustVal1) // runs
.chain(returnsNothing) // runs
.chain(returnsJustVal2) // does not run
.chain(returnsJustVal3) // does not runI also wanted to say that I've been focused entirely on the "canonical" Maybe a data type here, but that isn't to say that the "magic" null/undefined chaining thingy isn't possibly useful in a JS context. It just isn't a monad, in the sense that it obeys all the laws we want monads to obey. Those laws are what let us treat our programs like symbolic equations, giving us more power to write and refactor without thinking through implementations.
The flip of that coin is that the thing which makes Maybe monadic is not that it does special things with null/undefined, but that in a sequence of maybe-generating steps, the chain function squishes Just (Just x) -> Just x, Just Nothing -> Nothing, and Nothing (as type Maybe (Maybe x)) to Nothing (as type Maybe x). The upshot of which means that returning a Nothing short-circuits the remaining steps, and returning a Just continues the sequence of computations, and at the end you have a single layer of Just or Nothing. Your return value acts as a signal for whether to continue or not!
Any special handling for null/undefined, e.g. returning a Nothing when you encounter them, is on you as a human developer to opt into. But on the other hand, there are other kinds of Nothing depending on context! So if you have a function which divides numbers… you could say that safeDivide(x, 0) returns Nothing. That isn't related to null or undefined (in JS, 5/0 returns Infinity) but it lets you use the sequencing and explicit case-handling APIs discussed already.
Thanks for this great explanation @glebec. Spot On!
Thanks @abiodun0.
@getify I realized that my very last post – about reasons for Nothing besides null/undefined values - is another fruitful branch of this topic, so here's a smorgasbord of assorted Maybe tricks.
- various "finders" and list/string-processors which can fail. Advantages: can use the
map,chainetc. APIs (leverage ecosystem of Maybe tools for easier composition); can distinguish between "foundundefined" vs. "did not find it".minimum([]) === NothingparseBool('hello') === Nothing,parseBool('truedat') === Just([true, 'dat'])- (already mentioned): upgrade
findIndexto return maybe values (Nothinginstead of-1,Just idxinstead ofidx) - (already mentioned): upgrade
findto return maybe values
- certain arithmetic operations
- (already mentioned):
safeDivide(x, 0) === Nothing(instead ofInfinity),safeDivide(x, 2) === Just(x/2) squareRoot (-4) === Nothing(instead ofNaN),squareRoot(4) === Just(2)
- (already mentioned):
- constructive tools, interestingly! Maybe can be used as a signal for whether to construct or not.
- the
mapMaybe :: (a -> Maybe b) -> [a] -> [b]function combines map & filter into a single function, using Maybe as a selection interface:mapMaybe((el) => typeof el === 'string' ? Just(el + '!') : Nothing, [4, 'hi', false, 'yo'])returns['hi!', 'yo!']
- the function
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]takes an initial seedband a producerb -> Maybe (a, b)function, and begins constructing a data type from a single value up. It's the opposite ofreduce! TheMaybepart is used to indicate whether to keep producing (onJustresults) or stop (onNothing). - In a tic-tac-toe game, each cell can be a
Maybe MarkwhereNothingcorresponds to no mark andMark = X | O.- as opposed to a custom data type
GameSlot = Empty | X | O, the Maybe-wrapped version lets us leverage the existing Maybe API/toolset… this is a common theme.
- as opposed to a custom data type
- the
Those are just some that come to mind, only some of which have any bearing on or relation to null/undefined. In general the big advantage over null/undefined per se is that we are putting both failure and success cases into a wrapper with a specific API, and those wrappers / that API lets you easily compose results and express sequenced operations without dealing directly with the plumbing too much.
For example, in the tic-tac-toe model above, you could write a function flipPlayers easily (assuming your boards are also functors):
function flipPlayers (board) {
return board.map(cell => { // assuming boards are functors
return cell.map(mark => { // cells are Maybe Mark values
return mark === 'X' ? 'O' : 'X' // no need to explicitly think about blank spots – Maybe `map` handles that
}
}
}I find this extremely useful and I'm very happy I stumbled upon this.
I've read a lot of functional programming resources, mostly in the context of Javascript, and am still working though http://haskellbook.com/, but this is so well put it filled me up with inspiration and the sense that I get it.
Thanks a lot, @glebec!
Happy to hear that @harmenjanssen.
@getify — I struggled to give a concise answer which hits all the points which could be relevant. Your question is loose enough that it touches on many interrelated points of discussion, such as:
Maybedata typeMaybeas a concept is necessary or notMaybecan be a functor and/or monad, and what that gives usUltimately I failed and this post is far too long, which I regret. But as the famous quote goes, I didn't have time to write a shorter one.
The
Maybe aDatatypeConsider a function
head(note: slightly different from theheadexample shown earlier!) which attempts to read the first value of an array. In a typed setting, such a function has a problem - what does it do on the empty list?Partial Functions (Yuck)
Partial functions cannot handle every input they claim to in their type. On an unhandled case like
head [], Haskell throws a runtime exception (yuck). This is usually considered bad practice and can be warned against with compiler flags.Use a Different Input Type (Cool)
Instead of a function on lists, we could make
heada function onNonEmptylists – a data type that always contains at least one element by construction. Now the caller ofheadmust provide a special input, but is guaranteed anareturn value.Use a Different Output Type (Cool)
We cannot always make good on a promise to return an
afrom a list, but we can always return aMaybe a. If we don't have ana, we can returnNothing, and if we do have ana, we can returnJust a. Now the caller ofheadmust deal with a special output.Ignore Types (Meh) or Allow Union Return Type (Hmm…)
In vanilla JS we don't have any mechanism for specifying return type. If we have an
Array Stringvalue, thenhead = strings => strings[0]could return aStringorundefined. In a sense, that means our actual (unenforced) JS type forheadis[a] -> (a | undefined).Maybe avs.a | undefinedThere is an interesting parallel here.
If a
Maybe ais eitherJust aorNothing, and our JS function returns eitheraorundefined… aren't those kind of the same idea? Yes and no. Some of the important differences are as follows:Language-Specific Restrictions (Semi-Arbitrary)
In Haskell at least, you cannot return an untagged union like
String | Undefined. You need one thing to the right of->, and theMaybetype solves this issue by tying togetherJust aandNothingvalues.This restriction and others push us towards keeping our types explicit and focused, and therefore easier to compose. We don't end up with a soup of loosely-typed functions taking
a | Null | Stringand returningInt | Float | Undefined | Nulletc.Inversion of Control (Major Benefit)
In JS, programmers frequently forget that a function like
headmight returnundefined. It's not documented or checked statically – it tends to be very implicit, and therefore, easily overlooked (a pit of despair).A JS programmer calling
headon anArray Stringmight use.sliceon the return value, and it seems to work, because aStringis usually returned. But the one timeheadreturnsundefined, we have an error.Returning a
Maybe Stringvalue (i.e., eitherJust "some string"orNothing) instead means the programmer is now explicitly forced to acknowledge the possibility of a non-result, and to interact with an alternative API which pushes them do the right thing.When your value is of type
Maybe String, you will never call.sliceon it – because maybe values don't haveslice! Your way of interacting with aMaybe Stringis to use functions that are explicitlyMaybe-aware, or to manually check if you have aJustorNothingvalue.This is a major benefit to the
Maybeconcept. It is about inversion of control – preventing direct access to a possibly-absent value, and instead wrapping it in a more disciplined API (a pit of success).headtype[String].toUpperCase().map(s => s.toUpperCase())[a] -> a'hi''HI'– worked[a] -> aundefined[a] -> Maybe aJust('hi')Just('HI')– worked[a] -> Maybe aNothingNothing– worked(Note in the table above I said "mental model" of the
headtype. The actualheadtype might be[a] -> (a | undefined), but if nine times out of ten the function returns ana, human beings are doomed to forget the other case.)The
MaybeFunctorThe type of functor
mapfunction is that it "upgrades" ana -> bfunction to work on 0+ value(s) "in a context":Now, the context for
Maybeis that the value we want to operate might be in aJustOR might not exist (Nothing). Ourmapfunction works regardless, and we obey themaptype in that same context in -> same context out. Mapping anArrayresults in an array; mapping aMayberesults in aMaybe.The
JustandNothingFunctors?In Haskell we literally define a single
fmapfunction forMaybewhich does case analysis:(Haskellions, I know there is a more idiomatic and lazy version of this definition, but I wanted to emphasize the switch case nature of the function.)
But frequently in JS, we instead define two separate
mapmethods, one that lives onJustvalues and one which lives onNothingvalues.If instead of a single
Maybefunctor, we imagine a universe in which there are two separate functorsJustandNothing, the functor laws andmaptype still hold. Same context in, same context out;Justmaps toJustandNothingmaps toNothing.So, it doesn't seem like we need any
Maybetype at all so far.Just aandNothing acould be types, andJust/Nothingcould be functors. The context for theJustfunctor is that a value is wrapped inside aJustobject. The context for theNothingfunctor is that there is no value at all, somapis a noop.However… look what happens to our
headfunction:Hm, there's that union-based return type again. Like I said before, this is just not supported in Haskell, so in that language you need
Maybeif only to act as a "namespace" as you put it. But what about JS? Since we don't have type checking, everything is permitted.Works fine. But… what good is a function which returns values that might be
Justvals, and might beNothing? The answer is that such a function is really only useful if we ensure that bothJustandNothingvalues have the same API (e.g. they both havemap), or we write functions that know how to deal with both.Here is an example of the latter. Suppose we use
headon a list of Strings, and we want to collapse (fold, catamorphise, whatever) theJust String | Nothinginto a singleString(with a default).The above function knows specifics about the shape of
Justvalues vsNothingvalues. The more utility functions we write for the combo ofJustorNothingvals – the bigger our "Just or Nothing" toolset gets, in terms of both methods and functions – the odder it seems that we treatJust aandNothingas two different types.So even in vanilla JS, if we are going to deal with and document (via comments)
JustandNothingvalues together all the time, thenMaybeas a grouping concept becomes a good idea if for no better reason than convenience.Is it strictly required, at this point? Not if we allow union return types as a concept. But it might clean up our docs a bit.
What is a Functor, Anyway?
I want to take an aside to clear up some jargon. I have seen you write a couple of times now things like "
Just(..)returns monads" or "its instances are monads." This is, in the very strict definition of a monad, incorrect. Let's discuss why in the context of a simpler concept, namely functors. In FP langs we frequently say or write things like:[1, 2, 3]is a functor because it hasmapJust(4)is a functor because it hasmapThis is, in the strictest sense, wrong. It is a (common) abuse of terminology. Runtime JS or HS values are never functors. So… what is a functor?
Array Int, theArray"part" is a functor.Maybe Int, theMaybe"part" is a functor.Note that you cannot ever make a value of type
Array(NB: for typed arrays!), and you cannot ever make a value of typeMaybe.Arraycontext is that it is an abstract template, e.g.[_, _, _]Maybecontext is that it is an abstract template, e.g.Just(_).It is only when you fill in the "type template"
ArrayorMaybewith an actual type (likeInt) that you get a collection of runtime values:Array Intincludes[1, 2, 3]Maybe IntincludesJust(4)Now here's the kicker: these "type templates" or rather type constructors like
ArrayandMaybe, which have kind* -> *, are the part that are actually functors. In other words, when we say that "Arrayis a functor", what we mean is that the array context is preserved while the values are mapped:[1, 2, 3].map(inc) // [2, 3, 4]: the abstract context[_, _, _]is the functor, the values1/2/3are transformed.Just(4).map(inc) // Just(5): the abstract contextJust(_)is the functor, the value4is transformed.The functor is the context part only, NOT the complete runtime value of context + values(s). It is impossible in JS to fill in
const functorInstance = ????because "contexts" do not exist as values unto themselves – they are qualities of values which cannot be "instantiated."The phrase "things that have
mapare called functors" is a convenient introductory perspective, a "white lie" that helps get students grouping things conceptually. But it's also misleading because the thing that is really a functor is not the value with.mapmethod but the abstract shell around the value that is unchanged by mapping.As a corollary, the type
Array Stringis NOT a functor, but its values ARE mappable; whereas, the type constructorArrayIS a functor, but it has no values. Oof! This is true for all functors, by the way.Maybe Intis a type with mappable values;Maybeis a functor and has no values.Why does this really matter? Well, it matters insofar as having a shared precise language for discussing type theory matters. Not talking about the same thing in the same way eventually leads to confusion, and prevents us from communicating about more advanced topics. So, it is a semantic thing, but semantics begin to play a bigger role the deeper we get.
The
MaybeApplicativeMonads must also be functors and applicatives. One of the requirements of applicatives is a function
of, akapure(alsoreturn, lamentably). This function takes any single value, and puts it "into" the context.I wanted to touch on
ofbecause it came up in earlier discussion. I won't cite all of the relevant Applicative laws, but here is an illustrative one:of(f).ap(of(x))is the same asof(f(x)). This means it doesn't matter if we call the function on the value and put the result into a context, or if we put the function and value into contexts and then callap.Think about what it would mean if we allowed
ofto check the value, e.g. via a null check (as you suggested). That would break the above law!This law (and others) guarantees that
ofis not biased about the values it takes. That lack of bias makes it possible for us to refactor our code with the guarantee of the same result. Without this guarantee, we lose one of the primary motivations for typed FP: the ability to manipulate our programs symbolically, without mentally executing implementations as we do in imperative code.Just(undefined) !== NothingThere is another important point here, which is sometimes we might want null or undefined to end up inside of a
Just, instead of defaulting toNothing.Consider
Array.prototype.find, which has a weird problem – iffindreturnsundefined, does that mean "found undefined" or "did not find what you wanted"? There is no way to tell.If on the other hand
findreturnedMaybevalues, then you could tell, because that's the difference betweenJust(undefined)andNothing. They mean different things, in a genuinely-useful way.A major purpose for
Maybeas a concept is to take an existing type – likeBool– and add one more special value to it, which can definitely be distinguished from the existing values.Many JS functions come close to this idea by using the advantage that they can return a "special" value.
findIndexreturns-1on not found, because valid indexes are always0or higher. But if the thing you are looking for can be any value, how do you properly indicate whether it is found? You cannot use any existing value; you must use a wrapper likeMaybe. This can even work if the value you are looking for is itself a maybe value!The
JustandNothingApplicatives?Earlier we asserted that if we allow union types, we don't need
Maybe– that we could have a mix ofJustandNothingvals as inputs and outputs, and they would still obey both the functor laws andmaptype.Does that logic still hold for Applicatives? Let's look at the
apfunction.Important point again:
appromises same two applicative contexts in, same applicative context out. We have just lost the concept of useful separateJust aandNothingtypes! We cannot doJust(inc).ap(Nothing)becauseapclaims that we need the same applicative context on both sides. One reason is so that theaptype can tell you what applicative context we will get back, without tracing runtime implementation logic.If we group
Just aandNothingtogether into a single typeMaybe a, this problem goes away:Ah, the context is preserved and predictable the whole way through. We know that using
apwith two maybe-vals will itself result in a maybe-val (which means consumers of the return type explicitly know they will need to deal with the uncertainty of it being a Just/Nothing val).Monads
At last we come to monads. Remember that
mapdeals with upgrading vanilla functions to work despite being blocked by some annoying context:And
apdeals with what happens when you end up with a function which is itself stuck in the context:Monads deal with what happens when you end up with nested contexts.
The thing that makes monads special is
join, akaflatten(or in JS's case, sometimesflat). It is the capability of fusing nested contexts in a "sensible" (and law-abiding) way. Why do we have nested contexts to begin with? Frequently, it is because wemapwith a function that generates more context.ArrayMonadFor a concrete example, consider a solution to this classic interview question:
I won't implement the whole algorithm, but the initial processing of start-end tuples into an unsorted list of mixed start & end points can be accomplished using
map+join:From each single start-end record we produced two event records (in an array), meaning we end up with a list of lists – which we flatten down into a single list.
Sequencing Computations Generating Structure
One thing we often do with mapping is to sequence multiple computations while not having to manually deal with all that pesky context in the way. We see this all the time with arrays:
Of course, we could apply the same sequence of operations to an initial
Maybe Intvalue.What's cool about the above is that if our initial value was
Nothing, then the subsequentmaps were all noops and we end up withNothing(but no thrown errors). So right away we have a nice use case for theMaybeconcept which is that we know our return type for this chain: it is aMaybe String.But what if some of our sequenced operations returned more
Maybevals?Oops! When we tried to
mapourMaybe (Array String)to convert theArray Stringto its first String element,headreturned aMaybe String(because of course there might not be a String in that sublist). But this was a map, so thatMaybe Stringends up back in the context theArray Stringstarted –Maybe– resulting in nested maybes (Maybe (Maybe String)). On our next step we intended to try to get the first letter of the "possible (possible string)", butmapdoesn't go "deep enough" – so our API has broken down at this point.One thing we could do is
mapusingmap.This does work, but the further we go, the more we now have to nest
mapitself. Plus, our return type becomes ever more inconvenient – who wants to deal with aMaybe (Maybe (Maybe (Maybe Int)))for example? Yuck.Of course the solution is once we end up with sandwiched maybes, we should just smush them down.
And this, right here, is the use of the maybe monad. The thing that makes it special, the reason we care, is because we have a sequence of computations which keep generating extra unwanted context, BUT we also have a convenient way to fuse nested contexts down to a single layer.
This use case is so widespread that the combination of
map+joinends up being more famous thanjoinitself. We call itchain, akabind,>>=, andflatMap.headkeeps producing more "maybeness" all over the place – at each step it might beJustand it might beNothing– butchainkeeps simplifying to just one level of maybeness.maplet us sequence functions likew -> x,x -> y,y -> zeven though our values were wrapped in functor contexts like[w],[x], and[y].chainlets us sequence functions likew -> [x],x -> [y], andy -> [z]- wheremapwould start nesting unwanted layers like[[[z]]]. Or if you prefer,w -> Maybe x,x -> Maybe y, andy -> Maybe z– and we end up with aMaybe z, not aMaybe (Maybe (Maybe z)).Conclusion
I don't know if any of this helps clear things up for you. These are concepts which I have had the benefit of puzzling through in a rigid typed system (Haskell) over hundreds of pages of exercises and a lot of discussion with others. I don't think the concepts can be done justice in a gist comment, sadly! But if you do have more questions, I hope to hear back from you.
So what does
Maybegive you?JustorNothingtypes alone would not match the required types (because the context must be preserved, and e.g.chaincan switch from Just to Nothing!)NothingCheers, —G.