-
-
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 run
I 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
,chain
etc. APIs (leverage ecosystem of Maybe tools for easier composition); can distinguish between "foundundefined
" vs. "did not find it".minimum([]) === Nothing
parseBool('hello') === Nothing
,parseBool('truedat') === Just([true, 'dat'])
- (already mentioned): upgrade
findIndex
to return maybe values (Nothing
instead of-1
,Just idx
instead ofidx
) - (already mentioned): upgrade
find
to 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 seedb
and a producerb -> Maybe (a, b)
function, and begins constructing a data type from a single value up. It's the opposite ofreduce
! TheMaybe
part is used to indicate whether to keep producing (onJust
results) or stop (onNothing
). - In a tic-tac-toe game, each cell can be a
Maybe Mark
whereNothing
corresponds 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:
Maybe
data typeMaybe
as a concept is necessary or notMaybe
can 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 a
DatatypeConsider a function
head
(note: slightly different from thehead
example 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
head
a function onNonEmpty
lists – a data type that always contains at least one element by construction. Now the caller ofhead
must provide a special input, but is guaranteed ana
return value.Use a Different Output Type (Cool)
We cannot always make good on a promise to return an
a
from 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 ofhead
must 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 String
value, thenhead = strings => strings[0]
could return aString
orundefined
. In a sense, that means our actual (unenforced) JS type forhead
is[a] -> (a | undefined)
.Maybe a
vs.a | undefined
There is an interesting parallel here.
If a
Maybe a
is eitherJust a
orNothing
, and our JS function returns eithera
orundefined
… 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 theMaybe
type solves this issue by tying togetherJust a
andNothing
values.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 | String
and returningInt | Float | Undefined | Null
etc.Inversion of Control (Major Benefit)
In JS, programmers frequently forget that a function like
head
might 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
head
on anArray String
might use.slice
on the return value, and it seems to work, because aString
is usually returned. But the one timehead
returnsundefined
, we have an error.Returning a
Maybe String
value (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.slice
on it – because maybe values don't haveslice
! Your way of interacting with aMaybe String
is to use functions that are explicitlyMaybe
-aware, or to manually check if you have aJust
orNothing
value.This is a major benefit to the
Maybe
concept. 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).head
type[String]
.toUpperCase()
.map(s => s.toUpperCase())
[a] -> a
'hi'
'HI'
– worked[a] -> a
undefined
[a] -> Maybe a
Just('hi')
Just('HI')
– worked[a] -> Maybe a
Nothing
Nothing
– worked(Note in the table above I said "mental model" of the
head
type. The actualhead
type 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
Maybe
FunctorThe type of functor
map
function is that it "upgrades" ana -> b
function to work on 0+ value(s) "in a context":Now, the context for
Maybe
is that the value we want to operate might be in aJust
OR might not exist (Nothing
). Ourmap
function works regardless, and we obey themap
type in that same context in -> same context out. Mapping anArray
results in an array; mapping aMaybe
results in aMaybe
.The
Just
andNothing
Functors?In Haskell we literally define a single
fmap
function forMaybe
which 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
map
methods, one that lives onJust
values and one which lives onNothing
values.If instead of a single
Maybe
functor, we imagine a universe in which there are two separate functorsJust
andNothing
, the functor laws andmap
type still hold. Same context in, same context out;Just
maps toJust
andNothing
maps toNothing
.So, it doesn't seem like we need any
Maybe
type at all so far.Just a
andNothing a
could be types, andJust
/Nothing
could be functors. The context for theJust
functor is that a value is wrapped inside aJust
object. The context for theNothing
functor is that there is no value at all, somap
is a noop.However… look what happens to our
head
function: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
Maybe
if 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
Just
vals, and might beNothing
? The answer is that such a function is really only useful if we ensure that bothJust
andNothing
values 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
head
on a list of Strings, and we want to collapse (fold, catamorphise, whatever) theJust String | Nothing
into a singleString
(with a default).The above function knows specifics about the shape of
Just
values vsNothing
values. The more utility functions we write for the combo ofJust
orNothing
vals – the bigger our "Just or Nothing" toolset gets, in terms of both methods and functions – the odder it seems that we treatJust a
andNothing
as two different types.So even in vanilla JS, if we are going to deal with and document (via comments)
Just
andNothing
values together all the time, thenMaybe
as 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 hasmap
Just(4)
is a functor because it hasmap
This 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
.Array
context is that it is an abstract template, e.g.[_, _, _]
Maybe
context is that it is an abstract template, e.g.Just(_)
.It is only when you fill in the "type template"
Array
orMaybe
with an actual type (likeInt
) that you get a collection of runtime values:Array Int
includes[1, 2, 3]
Maybe Int
includesJust(4)
Now here's the kicker: these "type templates" or rather type constructors like
Array
andMaybe
, which have kind* -> *
, are the part that are actually functors. In other words, when we say that "Array
is 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
/3
are transformed.Just(4).map(inc) // Just(5)
: the abstract contextJust(_)
is the functor, the value4
is 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
map
are 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.map
method but the abstract shell around the value that is unchanged by mapping.As a corollary, the type
Array String
is NOT a functor, but its values ARE mappable; whereas, the type constructorArray
IS a functor, but it has no values. Oof! This is true for all functors, by the way.Maybe Int
is a type with mappable values;Maybe
is 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
Maybe
ApplicativeMonads 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
of
because 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
of
to check the value, e.g. via a null check (as you suggested). That would break the above law!This law (and others) guarantees that
of
is 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) !== Nothing
There 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 – iffind
returnsundefined
, does that mean "found undefined" or "did not find what you wanted"? There is no way to tell.If on the other hand
find
returnedMaybe
values, 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
Maybe
as 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.
findIndex
returns-1
on not found, because valid indexes are always0
or 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
Just
andNothing
Applicatives?Earlier we asserted that if we allow union types, we don't need
Maybe
– that we could have a mix ofJust
andNothing
vals as inputs and outputs, and they would still obey both the functor laws andmap
type.Does that logic still hold for Applicatives? Let's look at the
ap
function.Important point again:
ap
promises same two applicative contexts in, same applicative context out. We have just lost the concept of useful separateJust a
andNothing
types! We cannot doJust(inc).ap(Nothing)
becauseap
claims that we need the same applicative context on both sides. One reason is so that theap
type can tell you what applicative context we will get back, without tracing runtime implementation logic.If we group
Just a
andNothing
together into a single typeMaybe a
, this problem goes away:Ah, the context is preserved and predictable the whole way through. We know that using
ap
with 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
map
deals with upgrading vanilla functions to work despite being blocked by some annoying context:And
ap
deals 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 wemap
with a function that generates more context.Array
MonadFor 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 Int
value.What's cool about the above is that if our initial value was
Nothing
, then the subsequentmap
s were all noops and we end up withNothing
(but no thrown errors). So right away we have a nice use case for theMaybe
concept 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
Maybe
vals?Oops! When we tried to
map
ourMaybe (Array String)
to convert theArray String
to its first String element,head
returned aMaybe String
(because of course there might not be a String in that sublist). But this was a map, so thatMaybe String
ends up back in the context theArray String
started –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)", butmap
doesn't go "deep enough" – so our API has broken down at this point.One thing we could do is
map
usingmap
.This does work, but the further we go, the more we now have to nest
map
itself. 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
+join
ends up being more famous thanjoin
itself. We call itchain
, akabind
,>>=
, andflatMap
.head
keeps producing more "maybeness" all over the place – at each step it might beJust
and it might beNothing
– butchain
keeps simplifying to just one level of maybeness.map
let us sequence functions likew -> x
,x -> y
,y -> z
even though our values were wrapped in functor contexts like[w]
,[x]
, and[y]
.chain
lets us sequence functions likew -> [x]
,x -> [y]
, andy -> [z]
- wheremap
would 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
Maybe
give you?Just
orNothing
types alone would not match the required types (because the context must be preserved, and e.g.chain
can switch from Just to Nothing!)Nothing
Cheers, —G.