Skip to content

Instantly share code, notes, and snippets.

@getify getify/1.js
Last active Sep 27, 2019

Embed
What would you like to do?
is Maybe a "monad?
// 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
@DrBoolean

This comment has been minimized.

Copy link

DrBoolean commented May 3, 2019

"it's a namespace that holds methods that can make different kinds of monads"

That's where i think of it differently. Just and Nothing = Maybe just like Nil+Cons = List and Node+Leaf = Tree.

That can be done with an enum, abstract superclass, sum types, etc. But it's always the case that Maybe is the combination Just and Nothing

@DrBoolean

This comment has been minimized.

Copy link

DrBoolean commented May 3, 2019

Well...if done right :)

@getify

This comment has been minimized.

Copy link
Owner Author

getify commented May 3, 2019

@DrBoolean I appreciate that clarification. It sort of makes some sense to me -- not a very savvy FP programmer -- but what doesn't make sense to me is that it's literally just a convenience and semantic name, not a useful entity.

IOW, all the "magic" of Maybe here is actually inside prop(..) and the isEmpty(..) check. Maybe here could be eliminated entirely, and that code just reference Just(..) instead of Maybe.of(..), and it would be doing the "Maybe"-ness, without a Maybe entity of any sort.

So that's why it feels like Maybe is not, in the fullest sense, a monad, but a sort of pattern/interface for getting monads.

Does that confusion make any sense?

@DrBoolean

This comment has been minimized.

Copy link

DrBoolean commented May 3, 2019

Totally! I think it makes more sense if you consider a type checker prop :: Key -> { Key: a } -> Maybe a. Both Just and Nothing are of type Maybe so we can verify "you'll receive one or the other"

@glebec

This comment has been minimized.

Copy link

glebec commented May 4, 2019

@getify there is another aspect to this which I think is important. In FP we often loosely say things like "arrays are monads" or "maybe values are monadic" etc. However, speaking more strictly, it is not the values (like [1, 2, 3], Nothing, or Just(6)) that are monads, but the context (the Array or Maybe "namespace" as you put it). In mathematical terms, we say monads have kind * -> *, but that is difficult to talk about in an untyped / JS setting. So let's illustrate it via some concrete examples.

The Rules

chain :: Monad m => m a -> (a -> m b) -> m b

The promise of the chain type is:

  • If you give me a particular monad m containing 0+ value(s) of type a,
  • and a function from a to the same monad m containing 0+ value(s) of type b,
  • I will give you that same monad m containing 0+ value(s) of type b.

The thing I am trying to emphasize is same monad in, same monad out.

The Problem

Now, if you were to claim that Just(5) "is a monad", but pass chain a function that returns Nothing

//             monad a    -> (a        -> monad b  ) -> monad b
//             Just Int   -> (Int      -> Nothing  ) -> Nothing
const result = Just(5).chain((ignored) => Nothing()) // Nothing()

Then we have a contradiction. A core promise of chain is, again, same monad in, same monad out. But we started with a Just and ended with a Nothing! If you claim that the monad is Just, then chain didn't preserve the monadic context it started with, and that's a no-no.

Conversely, you could say that since we started with the "Just monad", the function we pass to chain must return only Just values. But that would kill the whole use case for Just and Nothing in the first place, so that's also a non-starter.

The Solution

Now, consider if we "group" or "namespace" Just and Nothing together under an umbrella called Maybe. Just and Nothing values would be instances of this Maybe class, and we would talk about chain with respect to this grouping. In other words, we would say "chain starts with a Maybe value, and ends with a Maybe value." Eurekua! A small shift in perspective means that chain now behaves in a 100% predictable, rule-following way.

//             monad a    -> (a        -> monad b  ) -> monad b
//             Maybe Int  -> (Int      -> Maybe b  ) -> Maybe b
const result = Just(5).chain((ignored) => Nothing()) // Nothing()

Notice above, the monad in this case is always Maybe. We aren't swapping out "which monad" we are talking about as a result of using chain, because Just(5) and Nothing both are values in the same monad (Maybe).

Discussion

Is this a semantic issue? Sure. But it's a necessary one for types to align and compose in a predictable, rule-based way. Since we don't really live and breathe types in JS it becomes somewhat tricky to be precise about FP jargon using JS examples. I hope however that the above example conveys an important reason why the typical Just cannot be a monad, and the typical Nothing cannot be a monad, but the grouping of Just and Nothing values into a single collection named Maybe can be a monad.

Addendum

An interesting thing about this perspective shift is the way we implement chain in Haskell vs. in your JS implementation. In Haskell, we define a single function chain for the Maybe entity, which has two cases - a case for if the left value is a Just vs a case for if the left value is a Nothing. In your JS implementation, you defined two separate chain implementations - one that lives on Nothing values, and one that lives on Just values. That's a perfectly valid way of going about it in JS, with the upshot being if you have an unknown variable justOrNothing you can call chain on it and things just work™. But it underscores the perspective shift I am talking about, where in Haskell etc. we consider Just and Nothing values together to all be instances of Maybe, and so we implement chain for Maybe itself. In effect with two separate JS chain methods you are simulating this abstract concept that there is a single chain method which handles both versions of Maybe values.

It's possible to write a JS implementation which uses a single Maybe class and then some sort of tag (e.g. Symbol) that distinguishes Just values from Nothing values. In that case, you would have a single chain which does a tag check to use the correct behavior, more similar to what we do in Haskell. However, that implementation isn't necessarily better or worse than what you've done with two separate factory functions. Just pointing out that as usual, there are multiple ways of doing things, and with each comes a different perspective or feel for what abstract concept we are emphasizing.

@glebec

This comment has been minimized.

Copy link

glebec commented May 4, 2019

Follow-up / Aside

Another slightly unrelated point - in JS we tend to have two different versions of Maybe that are commonly shown.

  • one which does automatic null/undefined checks, to prevent accidentally throwing errors when reading properties
  • one which is a direct copy of the pure FP version from Haskell/Elm/PureScript etc., which has no concept of specific JS vals

The former is a practical thing for idiomatic JS, so it's not useless, but it is not a mathematical monad because of this value-bias as you and @DrBoolean have been discussing.

The latter IS a monad, but might seem not as helpful in a JS context because you still need to do manual null/undefined-checks yourself.

The Solution

You can somewhat have your cake and eat it too - a true mathematical Maybe monad + convenient idiomatic handling of null/undefined – using a fromNullable constructor.

function Just(v) {
  return { chain };
  function chain (fn) {
    return fn(v);
  }
  // `ap`, `map` elided
}

function Nothing() {
  return { chain };
  function chain (fn) { return Nothing(); }
   // `ap`, `map` elided
}

function fromNullable (val) {
  if (val === null || val === undefined) return Nothing();
  return Just(val);
}

// Indexable a -> Maybe a
function head (indexable) {
  const first = indexable[0]
  return fromNullable(first);
}

Just([])
.chain(head)
.map(v => v + 5) // Nothing

Just([1, 2, 3])
.chain(head)
.map(v => v + 5) // Just(6)

The downside is now we still need to be aware of when it is possible to return null/undefined values, so we can properly wrap them with fromNullable. That means we are probably still doomed to miss some cases. However, it is at least easier and more seamless to handle and compose these null checks in a sequence of computations. That's some gain, even if it isn't as foolproof as we would like it to be.

In a typed setting the compiler makes sure we never make those kinds of mistakes to begin with. So importing Maybe into JS only gives us some, not all, of the benefits it provides in e.g. Haskell.

@getify

This comment has been minimized.

Copy link
Owner Author

getify commented May 4, 2019

@glebec Would you consider isNullable(..) fromNullable(..) to be part of the "Maybe monad"?

@glebec

This comment has been minimized.

Copy link

glebec commented May 4, 2019

@getify - not directly, no. I would consider fromNullable to be a utility function using the Maybe monad, which makes that canonical version slightly more useful in a JS context. EDIT: oops, you wrote isNullable - was that deliberate? Maybe you're talking about something other than my fromNullable example.

@getify

This comment has been minimized.

Copy link
Owner Author

getify commented May 4, 2019

@glebec

I indeed meant fromNullable(..), corrected my question.

So... if fromNullable(..) is separate from "Maybe" itself, as an entity, then I'm trying to figure out what "Maybe" really is, in the sense of what novel or uniqueness or magic it holds? The fromNullable(..) that you provided holds the "magic" selection logic of picking Just or Nothing, just like my prop(..) did above.

When you take that stuff away from Maybe, I can't really pinpoint what Maybe, as an entity, is, other than trivial namespace? Just(..) makes monads, and so does Nothing(). And fromNullable(..) selects between the two. What does "Maybe" being an entity buy us, at all?

Or is that whole point? Maybe isn't a concrete thing, it's a particular pattern or usage of other concrete things? In which case, me calling it an "interface" rather than a monad seems more... useful.

@glebec

This comment has been minimized.

Copy link

glebec commented May 4, 2019

@getify — that's a great question and I have a few very specific responses I would like to make on it, but I'm going to be unavailable for a few hours. So this post is just to let you know that I have seen your question and will respond some time later today. Cheers, —G.

@glebec

This comment has been minimized.

Copy link

glebec commented May 5, 2019

@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:

  • the strict mathematical definitions of functors, applicatives, monads
  • the use case for monads in programming
  • dealing with these concepts in different (or absent) type systems
  • the advantages of the Maybe data type
  • whether Maybe as a concept is necessary or not
  • how Maybe can be a functor and/or monad, and what that gives us

Ultimately 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 Datatype

data Maybe a = Just a | Nothing

Consider a function head (note: slightly different from the head 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?

-- Haskell
head :: [a] -> a -- head takes a list of `a`s and returns an `a`
head (x:_) = x   -- head on an list beginning with `x` returns `x`
head []    = ??? -- head on the empty list returns ???

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 on NonEmpty lists – a data type that always contains at least one element by construction. Now the caller of head must provide a special input, but is guaranteed an a 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 a Maybe a. If we don't have an a, we can return Nothing, and if we do have an a, we can return Just a. Now the caller of head 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, then head = strings => strings[0] could return a String or undefined. In a sense, that means our actual (unenforced) JS type for head is [a] -> (a | undefined).

Maybe a vs. a | undefined

There is an interesting parallel here.

head :: [a] -> Maybe a -- i.e. `Just a | Nothing`
head :: [a] ->                      (a | undefined)

If a Maybe a is either Just a or Nothing, and our JS function returns either a or undefined… 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 the Maybe type solves this issue by tying together Just a and Nothing 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 returning Int | Float | Undefined | Null etc.

Inversion of Control (Major Benefit)

In JS, programmers frequently forget that a function like head might return undefined. 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 an Array String might use .slice on the return value, and it seems to work, because a String is usually returned. But the one time head returns undefined, we have an error.

Returning a Maybe String value (i.e., either Just "some string" or Nothing) 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 have slice! Your way of interacting with a Maybe String is to use functions that are explicitly Maybe-aware, or to manually check if you have a Just or Nothing 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).

mental model of head type example return from [String] .toUpperCase() .map(s => s.toUpperCase())
[a] -> a 'hi' 'HI' – worked
[a] -> a undefined ERROR!
[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 actual head type might be [a] -> (a | undefined), but if nine times out of ten the function returns an a, human beings are doomed to forget the other case.)

The Maybe Functor

The type of functor map function is that it "upgrades" an a -> b function to work on 0+ value(s) "in a context":

map :: Functor f => (a -> b) -> (f     a -> f     b)
map ::              (a -> b) -> (Array a -> Array b)
map ::              (a -> b) -> (Maybe a -> Maybe b)

Now, the context for Maybe is that the value we want to operate might be in a Just OR might not exist (Nothing). Our map function works regardless, and we obey the map type in that same context in -> same context out. Mapping an Array results in an array; mapping a Maybe results in a Maybe.

The Just and Nothing Functors?

In Haskell we literally define a single fmap function for Maybe which does case analysis:

instance Functor Maybe where
    fmap transform maybeVal =  -- mapping using a transformer on a maybe
        case maybeVal of       -- depends on which case our maybe val is
            Nothing -> Nothing
            Just a  -> Just (transform a)

(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 on Just values and one which lives on Nothing values.

function Just (val) {
    return { val, map }
    function map (transform) {
        return Just(transform(val))
    }
}

const Nothing = {
    map (transform) {
        return Nothing
    }
}

If instead of a single Maybe functor, we imagine a universe in which there are two separate functors Just and Nothing, the functor laws and map type still hold. Same context in, same context out; Just maps to Just and Nothing maps to Nothing.

// map :: Nothing ~> (a -> b) -> Nothing
Nothing.map(x => x)   ≡ Nothing                  // map(id) is a noop
Nothing.map(f).map(g) ≡ Nothing.map(pipe(f, g))  // funcs don't touch context

// map :: Just a ~> (a -> b) -> Just b
Just(5).map(x => x)   ≡ Just(5)                  // map(id) is a noop
Just(5).map(f).map(g) ≡ Just(5).map(pipe(f, g))  // funcs don't touch context

So, it doesn't seem like we need any Maybe type at all so far. Just a and Nothing a could be types, and Just / Nothing could be functors. The context for the Just functor is that a value is wrapped inside a Just object. The context for the Nothing functor is that there is no value at all, so map is a noop.

However… look what happens to our head function:

-- before
head :: [a] -> Maybe a

-- after
head :: [a] -> Just a | Nothing

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.

// :: [a] -> Just a | Nothing
function head (list) {
    if (!list.length) return Nothing
    return Just(list[0])
}

Works fine. But… what good is a function which returns values that might be Just vals, and might be Nothing? The answer is that such a function is really only useful if we ensure that both Just and Nothing values have the same API (e.g. they both have map), 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) the Just String | Nothing into a single String (with a default).

// :: Just String | Nothing -> String
function fold_JS_N (justStringOrNothing) {
    if ('val' in justStringOrNothing) return justStringOrNothing.val
    return 'default'
}

const string = fold(head(listOfStrings))

The above function knows specifics about the shape of Just values vs Nothing values. The more utility functions we write for the combo of Just or Nothing vals – the bigger our "Just or Nothing" toolset gets, in terms of both methods and functions – the odder it seems that we treat Just a and Nothing as two different types.

So even in vanilla JS, if we are going to deal with and document (via comments) Just and Nothing values together all the time, then Maybe 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 has map
  • Just(4) is a functor because it has map

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?

  • in the type Array Int, the Array "part" is a functor.
  • in the type Maybe Int, the Maybe "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 type Maybe.

  • The idea of the Array context is that it is an abstract template, e.g. [_, _, _]
  • The idea of the Maybe context is that it is an abstract template, e.g. Just(_).

It is only when you fill in the "type template" Array or Maybe with an actual type (like Int) that you get a collection of runtime values:

  • The type Array Int includes [1, 2, 3]
  • The type Maybe Int includes Just(4)

Now here's the kicker: these "type templates" or rather type constructors like Array and Maybe, 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 values 1/2/3 are transformed.
  • Just(4).map(inc) // Just(5): the abstract context Just(_) is the functor, the value 4 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 constructor Array 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 Applicative

Monads must also be functors and applicatives. One of the requirements of applicatives is a function of, aka pure (also return, lamentably). This function takes any single value, and puts it "into" the context.

of :: Applicative a => x -> a x

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 as of(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 call ap.

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!

function isNull (x) {
  return x === null
}

// law-breaking, assuming Maybe.of(null) returns `Nothing`
const res1 = Maybe.of(isNull).ap(Maybe.of(null)) // Nothing
const res2 = Maybe.of(isNull(null)) // Just true

// law-abiding, assuming Maybe.of(null) returns `Just null`
const res1 = Maybe.of(isNull).ap(Maybe.of(null)) // Just true
const res2 = Maybe.of(isNull(null)) // Just true

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 to Nothing.

Consider Array.prototype.find, which has a weird problem – if find returns undefined, does that mean "found undefined" or "did not find what you wanted"? There is no way to tell.

If on the other hand find returned Maybe values, then you could tell, because that's the difference between Just(undefined) and Nothing. They mean different things, in a genuinely-useful way.

A major purpose for Maybe as a concept is to take an existing type – like Bool – and add one more special value to it, which can definitely be distinguished from the existing values.

Bool = True | False -- 2 elements
Maybe Bool = Just True | Just False | Nothing -- 3 elements

Sign = Rock | Paper | Scissors  -- 3 elements
Maybe Sign = Just Rock | Just Paper | Just Scissors | Nothing  -- 4 elements

JSVals = null | undefined | 5 | ...  -- infinite values
Maybe JSVals = Just null | Just undefined | Just 5 | ... | Nothing  -- infinite + 1 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 always 0 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 like Maybe. This can even work if the value you are looking for is itself a maybe value!

function findFirstMaybe (list) {
   for (let i = 0; i < list.length; i++) {
       if (isMaybe(list[i])) return Just(list[i])
   }
   return Nothing
}

findFirstMaybe([])        // Nothing        -- did not find
findFirstMaybe([Nothing]) // Just(Nothing)  -- found this Maybe val
findFirstMaybe([Just(5)]) // Just(Just(5))  -- found this Maybe val

The Just and Nothing Applicatives?

Earlier we asserted that if we allow union types, we don't need Maybe – that we could have a mix of Just and Nothing vals as inputs and outputs, and they would still obey both the functor laws and map type.

Does that logic still hold for Applicatives? Let's look at the ap function.

ap :: Applicative a => a (x -> y) -> a x -> a y

Important point again: ap promises same two applicative contexts in, same applicative context out. We have just lost the concept of useful separate Just a and Nothing types! We cannot do Just(inc).ap(Nothing) because ap claims that we need the same applicative context on both sides. One reason is so that the ap type can tell you what applicative context we will get back, without tracing runtime implementation logic.

If we group Just a and Nothing together into a single type Maybe a, this problem goes away:

-- broken, not allowed in Haskell:
ap :: Applicative a/b => a       (x -> y) -> b       x -> (a|b) y
ap ::                    Just    (x -> y) -> Nothing x -> ???   y  -- cannot infer
ap ::                    Nothing (x -> y) -> Just    x -> ???   y  -- cannot infer
-- etc.

-- fixed, a *single* context:
ap :: Applicative a => a     (x -> y) -> a     x -> a     y
ap ::                  Maybe (x -> y) -> Maybe x -> Maybe y

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:

--                vanilla fn -> fn which works despite context
map :: Functor f => (x -> y) -> (f     x -> f     y)
map ::              (x -> y) -> (Array x -> Array y)
map ::              (x -> y) -> (Maybe x -> Maybe y)
//      (String -> Int), Maybe String -> Maybe Int
maybeMap(stringLength, Just('hi')) // Just(2)

And ap deals with what happens when you end up with a function which is itself stuck in the context:

--            fn stuck in context -> 
ap :: Applicative a => a     (x -> y) -> (a     x -> a     y)
ap ::                  Array (x -> y) -> (Array x -> Array y)
ap ::                  Maybe (x -> y) -> (Maybe x -> Maybe y)
// Maybe (String -> Int) -> Maybe String -> Maybe Int
Just(stringLength)      .ap(Just('hi'))  // Just(2)

Monads deal with what happens when you end up with nested contexts.

join :: Monad m => m     (m     a) -> m     a
join ::            Maybe (Maybe a) -> Maybe a
join ::            Array (Array a) -> Array a

The thing that makes monads special is join, aka flatten (or in JS's case, sometimes flat). 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 we map with a function that generates more context.

Array Monad

For a concrete example, consider a solution to this classic interview question:

Given a list of meeting start-end times, what is the minimum number of rooms do you need to hold all the meetings?

  • create a single timeline of labeled time points (start and stop, mixed)
  • sort by time (for ties, put end points first)
  • iterate through the timeline
    • increment a counter on start points
    • decrement the counter on end points
  • return the max the counter ever reached

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:

const meetings = [
  { start: 11, end: 13 },
  { start: 10, end: 13 },
  { start: 13, end: 14 }
]

const timeline = meetings
  .map(({start, end}) => [
    { type: 'start', time: start},
    { type: 'end', time: end }
  ])      // -> an array of 3 arrays, each with 2 elements
  .flat() // -> an array of 6 elements

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:

[1, 2, 3]    // [ 1,    2,    3  ]
.map(double) // [ 2,    4,    6  ]
.map(inc)    // [ 3,    5,    7  ]
.map(String) // ['3',  '5',  '7' ]
.map(yell)   // ['3!', '5!', '7!']

Of course, we could apply the same sequence of operations to an initial Maybe Int value.

head(possiblyEmptyList) // Maybe Int, e.g. Just(5) (or Nothing!)
.map(double) // Maybe Int, e.g. Just(10) 
.map(inc)    // Maybe Int, e.g. Just(11)
.map(String) // Maybe String, e.g. Just('10')
.map(yell)   // Maybe String, e.g. Just('10!')

What's cool about the above is that if our initial value was Nothing, then the subsequent maps were all noops and we end up with Nothing (but no thrown errors). So right away we have a nice use case for the Maybe concept which is that we know our return type for this chain: it is a Maybe String.

But what if some of our sequenced operations returned more Maybe vals?

// :: Array (Array String)
const example = [["", "Hi"], ["Yo"], [], ["Sup", "Hi"]]

head(example) // Maybe (Array String)
.map(head)    // Maybe (Maybe String)
.map(head)    // MISTAKE

Oops! When we tried to map our Maybe (Array String) to convert the Array String to its first String element, head returned a Maybe String (because of course there might not be a String in that sublist). But this was a map, so that Maybe String ends up back in the context the Array 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)", but map doesn't go "deep enough" – so our API has broken down at this point.

One thing we could do is map using map.

// :: Array (Array String)
const example = [["", "Hi"], ["Yo"], [], ["Sup", "Hi"]]

head(example) // Maybe (Array String)
.map(head)    // Maybe (Maybe String)
.map(maybeStr => maybeStr.map(head)) // Maybe (Maybe (Maybe Char)) // yuck

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 a Maybe (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.

// :: Array (Array String)
const example = [["", "Hi"], ["Yo"], [], ["Sup", "Hi"]]

head(example) // Maybe (Array String)
.map(head)    // Maybe (Maybe String)
.join()       // Maybe String
.map(head)    // Maybe (Maybe Char)
.join()       // Maybe Char

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 than join itself. We call it chain, aka bind, >>=, and flatMap.

// :: Array (Array String)
const example = [["", "Hi"], ["Yo"], [], ["Sup", "Hi"]]

head(example) // Maybe (Array String)
.chain(head)  // Maybe String
.chain(head)  // Maybe Char

head keeps producing more "maybeness" all over the place – at each step it might be Just and it might be Nothing – but chain keeps simplifying to just one level of maybeness.

map let us sequence functions like w -> x, x -> y, y -> z even though our values were wrapped in functor contexts like [w], [x], and [y].

chain lets us sequence functions like w -> [x], x -> [y], and y -> [z] - where map would start nesting unwanted layers like [[[z]]]. Or if you prefer, w -> Maybe x, x -> Maybe y, and y -> Maybe z – and we end up with a Maybe z, not a Maybe (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?

  • a single type ("namespace" if you prefer) for type signatures dealing with Just & Nothing vals - necessary for Haskell, convenient for JS
  • the mathematical context necessary to define Applicative and Monad instances, where hypothetical Just or Nothing types alone would not match the required types (because the context must be preserved, and e.g. chain can switch from Just to Nothing!)
  • a functor which lets you easily sequence vanilla computations, while "ignoring" the fact that your initial value might not exist
  • a monad which lets you easily sequence maybe-returning computations, where at each step you might have to bail out with a Nothing
  • a way of adding a "special" value to any type, even the type of all values, so that you can e.g. distinguish between "not found" and "found undefined"

Cheers, —G.

@glebec

This comment has been minimized.

Copy link

glebec commented May 5, 2019

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.

@abiodun0

This comment has been minimized.

Copy link

abiodun0 commented May 6, 2019

Thanks for this great explanation @glebec. Spot On!

@glebec

This comment has been minimized.

Copy link

glebec commented May 6, 2019

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 "found undefined" 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 of idx)
    • (already mentioned): upgrade find to return maybe values
  • certain arithmetic operations
    • (already mentioned): safeDivide(x, 0) === Nothing (instead of Infinity), safeDivide(x, 2) === Just(x/2)
    • squareRoot (-4) === Nothing (instead of NaN), squareRoot(4) === Just(2)
  • 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 seed b and a producer b -> Maybe (a, b) function, and begins constructing a data type from a single value up. It's the opposite of reduce! The Maybe part is used to indicate whether to keep producing (on Just results) or stop (on Nothing).
    • In a tic-tac-toe game, each cell can be a Maybe Mark where Nothing corresponds to no mark and Mark = 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.

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
    }
  }
}
@harmenjanssen

This comment has been minimized.

Copy link

harmenjanssen commented May 9, 2019

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!

@glebec

This comment has been minimized.

Copy link

glebec commented May 9, 2019

Happy to hear that @harmenjanssen.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.