Monad: Sequencing Dependent Computations
Chain steps that each need the last result, and let each container's instance decide what a failure does.
"There is a concatenation of events in this best of all possible worlds: for if you had not been kicked out of a magnificent castle for love of Miss Cunegonde: if you had not been put into the Inquisition: … you would not be here eating preserved citrons and pistachio-nuts."
— Voltaire, Candide (Chapter XXX)
Voltaire's Pangloss tells a chain of flatMap calls along its happy path: each event needs the one before it. What a chain does when a link fails is left to the instance.
- Recognise
Optional.flatMap,thenCompose,Stream.flatMapand a Path'sviaas one shape:Monad'sflatMap - Write a chain once for any container, through its
Monad - Predict what each instance's
flatMapdoes when a step has no value to work on - Use
flatMapIfOrElse,as,asUnit,peekandflatMap2toflatMap5in place of hand-written lambdas - Check an instance against the three monad laws with
hkj-test'sMonadLaws
The code on this page is MonadBook.java: the page includes it, so the build compiles and runs it. MonadBookTest.java holds what the page says each instance does, and FoundationsLawsBookTest.java checks the laws.
When the next step needs the last result
You have written this code:
optional.flatMap(order -> findPayment(order)); // an Optional<Payment>
future.thenCompose(order -> fetchPayment(order)); // a CompletableFuture<Payment>
orders.stream().flatMap(order -> order.lines().stream()); // a Stream<LineItem>
maybePath.via(order -> paymentOf(order)); // a MaybePath<Payment>
Each line runs a step that needs the order, and the step gives back a container of the same kind, which the call flattens into one. Java spells that shape two ways, and a Path a third. Monad is its name: a container's flatMap, keeping the three laws on this page.
For one container, an Effect Path chains with via, as maybePath.via does, and application code stays on the Paths. This page is for a method written once for any container.
A chain over one Optional, one CompletableFuture or one Stream needs nothing from this page: flatMap and thenCompose already chain them. Monad earns its place only when one method must serve any container.
The code on this page uses these imports, with Order from the order records the Optics chapter introduces:
import static org.higherkindedj.hkt.either.EitherKindHelper.EITHER;
import static org.higherkindedj.hkt.instances.Witnesses.either;
import static org.higherkindedj.hkt.instances.Witnesses.io;
import static org.higherkindedj.hkt.io.IOKindHelper.IO_OP;
import static org.higherkindedj.hkt.validated.ValidatedKindHelper.VALIDATED;
import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import org.higherkindedj.example.book.optics.cast.Order;
import org.higherkindedj.example.book.optics.cast.OrderLenses;
import org.higherkindedj.example.book.optics.cast.OrderStatus;
import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.Monad;
import org.higherkindedj.hkt.Semigroups;
import org.higherkindedj.hkt.TypeArity;
import org.higherkindedj.hkt.WitnessArity;
import org.higherkindedj.hkt.either.Either;
import org.higherkindedj.hkt.either.EitherKind;
import org.higherkindedj.hkt.instances.Instances;
import org.higherkindedj.hkt.io.IO;
import org.higherkindedj.hkt.io.IOKind;
import org.higherkindedj.hkt.validated.Validated;
import org.higherkindedj.hkt.validated.ValidatedKind;
What a Monad adds
Monad<M> extends Applicative<M> with one method, and builds flatMap2 to flatMap5 from it. Its source names the container M, where this page's own code says F:
public interface Monad<M extends WitnessArity<TypeArity.Unary>> extends Applicative<M> {
<A, B> Kind<M, B> flatMap(Function<? super A, ? extends Kind<M, B>> f, Kind<M, A> ma);
// abridged: the null checks and the other default methods are left out,
// and flatMap3, flatMap4 and flatMap5 each build on the one before
default <A, B, R> Kind<M, R> flatMap2(
Kind<M, A> ma, Kind<M, B> mb, BiFunction<? super A, ? super B, ? extends Kind<M, R>> f) {
return flatMap(a -> flatMap(b -> f.apply(a, b), mb), ma);
}
}
map takes an A -> B. flatMap takes an A -> Kind<M, B>: a step that gives back a container of its own. With map, that step would leave a container inside a container, a Kind<M, Kind<M, B>>. flatMap flattens the step's result into one Kind<M, B>.
When no step needs another's result, map2 to map5 are enough, and the less powerful tool is the one to pick. Should you use map3 or flatMap? says what they can do that flatMap cannot, and Applicative, Selective or Monad? walks through the choice.
One chain for any container
markPaid is written over Monad. It takes the Monad for F and calls flatMap: the step marks the order paid and saves it, so it needs the order found holds:
// One chain for any container F: save needs the order that was found
public static <F extends WitnessArity<TypeArity.Unary>> Kind<F, Order> markPaid(
Monad<F> monad, Kind<F, Order> found, Function<Order, Kind<F, Order>> save) {
return monad.flatMap(
order -> save.apply(OrderLenses.status().set(OrderStatus.PAID, order)), found);
}
Run it with Either's Monad, on an order that was found and on one that was not, then with IO's. ORDER is any Order that has not been paid for, and store adds an order to the list stored and hands it back:
Monad<EitherKind.Witness<String>> eitherMonad = Instances.monad(either());
Function<Order, Kind<EitherKind.Witness<String>, Order>> save =
paid -> EITHER.widen(Either.right(paid));
Either<String, Order> saved =
EITHER.narrow(markPaid(eitherMonad, EITHER.widen(Either.right(ORDER)), save));
// Right(Order[id=00000000-0000-0000-0000-000000000001, ..., status=PAID])
Either<String, Order> notFound =
EITHER.narrow(markPaid(eitherMonad, EITHER.widen(Either.left("order not found")), save));
// Left(order not found)
List<Order> stored = new ArrayList<>();
Kind<IOKind.Witness, Order> program =
markPaid(
Instances.monad(io()),
IO_OP.widen(IO.delay(() -> ORDER)),
paid -> IO_OP.widen(IO.delay(() -> store(stored, paid))));
int savedBeforeRunning = stored.size();
// 0
IO_OP.narrow(program).unsafeRunSync();
int savedAfterRunning = stored.size();
// 1
Either's instance runs save on a Right, and passes a Left on without running it. IO's runs nothing: markPaid gives back an IO that has not run, and the order is saved only when it runs.
What each instance does
Monad promises that flatMap hands the step the value when there is one. What it does otherwise, and when the step runs, is each instance's own. Either's keeps a success track and a failure track:
found mark paid, save
Right ════●═════════════●══════▶ Right(saved order)
╲ save gives a Left
Left ────●───────────────●────▶ Left(error)
a Left from found:
save never runs
The diagram shows two ways to end on the Left track: a Left from the lookup, which save never sees, and a Left from save itself. With one step, the instances you will meet most behave like this:
| Instance | What flatMap does with its input and the step |
|---|---|
Either, Validated | Runs the step on a Right or a Valid. A Left or an Invalid passes on unchanged, and the step never runs |
Try | The same with a Success and a Failure, and an exception the step throws becomes a Failure |
Maybe, Optional | Runs the step on a value. An empty input stays empty, and the step never runs |
List, NonEmptyList | Runs the step on every element and joins the results in order: two inputs that each give two results give four |
Stream | The same, lazily: the step runs on each element as the result is consumed |
IO, VTask | Builds a new deferred value and runs nothing. When it runs, it runs the input, then the step. If the input fails, the step never runs |
CompletableFuture | Starts the step when the input completes. If the input fails, the result fails and the step never runs |
Writer, from Instances.writer(monoid) | Runs the step, and joins the input's log and the step's, in that order, with the monoid |
So stopping at a failure, known as short-circuiting, comes from the instance, not from Monad: Either's stops at a Left, and List's runs the step on every element.
Helpers built on flatMap and map
Monad adds default methods for chains you would otherwise write as lambdas:
| Method | What it does | Built as |
|---|---|---|
flatMapIfOrElse(predicate, ifTrue, ifFalse, ma) | Chooses the next step by testing the value | flatMap(a -> predicate.test(a) ? ifTrue.apply(a) : ifFalse.apply(a), ma) |
as(b, ma) | Keeps the outcome, and replaces the value with b, which must not be null | map(_ -> b, ma) |
asUnit(ma) | Keeps the outcome, and replaces the value with Unit | map(_ -> Unit.INSTANCE, ma) |
peek(action, ma) | Runs action on the value, and keeps the value | map(a -> { action.accept(a); return a; }, ma) |
as, asUnit and peek are built from map, so they run where map runs: peek's action runs on a Right and on each element of a list, and never on a Left. On the order that was found, flatMapIfOrElse keeps an order that has not shipped, and as replaces it with a message:
Kind<EitherKind.Witness<String>, Order> found = EITHER.widen(Either.right(ORDER));
Either<String, Order> unshipped =
EITHER.narrow(
eitherMonad.flatMapIfOrElse(
order -> order.status() == OrderStatus.SHIPPED,
order -> EITHER.widen(Either.left("order has shipped")),
order -> EITHER.widen(Either.right(order)),
found));
// Right(Order[id=00000000-0000-0000-0000-000000000001, ..., status=NEW])
Either<String, String> receipt = EITHER.narrow(eitherMonad.as("receipt sent", found));
// Right(receipt sent)
flatMap2 to flatMap5
flatMap2 to flatMap5 combine two to five values with a step that gives back a container, for a combination that can itself fail. map2 to map5 take a plain function instead. Because they are built from flatMap, they take their inputs in order, so on Validated they stop at the first error, where its map2 reports both:
Monad<ValidatedKind.Witness<List<String>>> validatedMonad =
Instances.validated(Semigroups.list());
Kind<ValidatedKind.Witness<List<String>>, String> blankSku =
VALIDATED.widen(Validated.invalid(List.of("SKU is blank")));
Kind<ValidatedKind.Witness<List<String>>, Integer> noQuantity =
VALIDATED.widen(Validated.invalid(List.of("quantity must be positive")));
Validated<List<String>, String> mapped =
VALIDATED.narrow(
validatedMonad.map2(blankSku, noQuantity, (sku, quantity) -> quantity + " x " + sku));
// Invalid([SKU is blank, quantity must be positive])
Validated<List<String>, String> flatMapped =
VALIDATED.narrow(
validatedMonad.flatMap2(
blankSku,
noQuantity,
(sku, quantity) -> VALIDATED.widen(Validated.valid(quantity + " x " + sku))));
// Invalid([SKU is blank])
The step always succeeds, so it is not why flatMap2 stops at one error: flatMap2 is a chain of flatMap calls, and Validated's flatMap stops at the first Invalid. Where Validated bends a rule says why its map2 differs.
Three laws
A Monad keeps three laws. Together they say that of adds nothing of its own before or after a step, and that a chain gives the same result however you group its steps.
- Left identity: running a step on a lifted value is the step.
flatMap(f, of(a))equalsf.apply(a). - Right identity: running
ofas the step changes nothing.flatMap(a -> of(a), ma)equalsma. - Associativity: grouping the steps differently changes nothing.
flatMap(g, flatMap(f, ma))equalsflatMap(a -> flatMap(g, f.apply(a)), ma).
Two containers are equal when they hold equal values, or equal errors, in the same shape. For a deferred container such as IO, they are equal when running both gives equal results. The laws assume values that are never null and functions that never return one, and Values, never null says what each type does with one.
MonadLaws, beside ApplicativeLaws in hkj-test's org.higherkindedj.hkt.laws package, checks the three laws on any instance. It takes an equality from KindEquivalence.byEqualsAfter, as on the Applicative page, which here unwraps both sides with EITHER::narrow and compares them with equals. The test checks Either's instance on a Right and on a Left. verifyEmail always gives a Left, so the laws are checked when a step fails too. ORDER is any Order, and the test uses these imports, with JUnit's:
import static org.higherkindedj.hkt.either.EitherKindHelper.EITHER;
import static org.higherkindedj.hkt.instances.Witnesses.either;
import java.util.function.Function;
import java.util.stream.Stream;
import org.higherkindedj.example.book.optics.cast.Customer;
import org.higherkindedj.example.book.optics.cast.EmailAddress;
import org.higherkindedj.example.book.optics.cast.Order;
import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.Monad;
import org.higherkindedj.hkt.assertions.KindEquivalence;
import org.higherkindedj.hkt.either.Either;
import org.higherkindedj.hkt.either.EitherKind;
import org.higherkindedj.hkt.instances.Instances;
import org.higherkindedj.hkt.laws.MonadLaws;
static Stream<Kind<EitherKind.Witness<String>, Order>> eitherOrders() {
return Stream.of(
EITHER.widen(Either.right(ORDER)), EITHER.widen(Either.left("order not found")));
}
@ParameterizedTest
@MethodSource("eitherOrders")
@DisplayName("Either's Monad keeps all three laws, on a Right and on a Left")
void eitherMonadLaws(Kind<EitherKind.Witness<String>, Order> fa) {
Monad<EitherKind.Witness<String>> monad = Instances.monad(either());
var same = KindEquivalence.<EitherKind.Witness<String>>byEqualsAfter(EITHER::narrow);
Function<Order, Kind<EitherKind.Witness<String>, Customer>> findCustomer =
order -> EITHER.widen(Either.right(order.customer()));
Function<Customer, Kind<EitherKind.Witness<String>, EmailAddress>> verifyEmail =
customer -> EITHER.widen(Either.left("email not verified"));
MonadLaws.assertLeftIdentity(monad, ORDER, findCustomer, same);
MonadLaws.assertLeftIdentity(monad, ORDER.customer(), verifyEmail, same);
MonadLaws.assertRightIdentity(monad, fa, same);
MonadLaws.assertAssociativity(monad, fa, findCustomer, verifyEmail, same);
}
Back to the one-liner
static EitherPath<OrderError, Order> changeEmail(
OrderRepository orders, UUID id, String newEmail) {
return orders
.find(id)
.toEitherPath(OrderError.notFound(id))
.map(order -> OrderFocus.customer().email().value().set(newEmail, order))
.via(orders::save);
}
.via(orders::save) is the line's Monad layer: save needs the order the line holds so far, and on a Left it never runs. via is EitherPath's own method, with no Monad instance involved. Two encodings, one algebra matches it to Monad's flatMap over Kind.
Things people get wrong
- "
flatMapruns the step at once."Either's does.IO's andVTask's build a deferred value, and nothing runs until you run it.Stream's runs the step only as the stream is consumed. The order of the steps is fixed, and the timing is the container's. - "Monads always short-circuit." Instances whose input holds at most one value stop when it is missing or failed:
Either,Validated,Maybe,IOandCompletableFutureamong them.List'sflatMapruns the step on every element. The behaviour comes from the instance, not from the word "Monad". - "
flatMapisStream.flatMap."Stream.flatMapis one instance of the shape: it flattens a stream of streams.Monad'sflatMapnames the shape for any container. - "Nested
flatMapcalls are the cleanest you can do." They are the most explicit, asflatMap2's body shows. For more than two steps, a For comprehension reads better and avoids the indentation. - "You can call
.flatMapon aKind."Kindhas no methods. Go through theMonad<F>instance, which knows how to flatten insideF.
You can now write a chain once for any container, as markPaid is, and say what each instance does when a step has no value to work on. You can use the helpers in place of hand-written lambdas, and check an instance against left identity, right identity and associativity. The rest of this page is for which types have a Monad, and what builds on it.
markPaid runs with List's instance on two found orders. save gives back an empty list for the first, and one order for the second. How many orders come back?
Answer and why
Answer and why
One. List's flatMap runs the step on every element and joins the results, so the empty list adds nothing.
Where this lives: What each instance does.
On a Left, which branch of flatMapIfOrElse runs: ifTrue or ifFalse?
Answer and why
Answer and why
Neither. flatMapIfOrElse is built from flatMap, which passes a Left on without running its step, so the test and both branches never run. ifFalse handles a value that fails the test, not a failure.
Where this lives: Helpers built on flatMap and map.
The fine print
Which types have a Monad
| Types | Their Monad comes from |
|---|---|
Every token in Witnesses | Instances.monad(token), which always succeeds |
Validated, Writer, EitherOrBoth and the transformers | Instances with its argument, such as Instances.writer(monoid) |
Free | new FreeMonad<>() |
Const, FreeAp and Fetch | Nowhere: they have an Applicative and no Monad |
EitherF and Coyoneda | Nowhere: they have a Functor only |
What builds on Monad
MonadErrorextendsMonad. MonadError, the next page, adds raising an error and recovering from one.MonadZeroextendsMonadandAlternative. MonadZero adds an empty value, so a chain can filter.Fortakes aMonad.For.from(monad, source)writes a chain offlatMapcalls as a list of steps, as For comprehensions shows.GenericPathtakes aMonad.GenericPath.of(kind, monad)turns anyKindthat has aMonadinto a Path, withvia, as GenericPath shows.
- Applicative: combining values that do not depend on one another
- MonadError: raising an error and recovering from one
- For Comprehension: a chain of
flatMapcalls written as steps - Applicative, Selective or Monad?: choosing by whether a step needs an earlier result
- One Line, Six Layers: where
viasits in the chapter's one-liner
- Magnus Smith, Functors and Monads with Java and Scala: the same two type classes, side by side in both languages
- Bartosz Milewski, Monads: Programmer's Definition: monads as the composition of functions that return a container
- Mark Seemann, Monads: "a functor you can flatten", the start of a series with examples in C#, F# and Haskell
Practise Monad chaining in Tutorial 04: Monad Chaining (8 exercises).
Previous: Applicative Next: MonadError