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.

What You'll Learn

  • Recognise Optional.flatMap, thenCompose, Stream.flatMap and a Path's via as one shape: Monad's flatMap
  • Write a chain once for any container, through its Monad
  • Predict what each instance's flatMap does when a step has no value to work on
  • Use flatMapIfOrElse, as, asUnit, peek and flatMap2 to flatMap5 in place of hand-written lambdas
  • Check an instance against the three monad laws with hkj-test's MonadLaws

See Example Code

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.

Plain Java wins here

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:

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:

InstanceWhat flatMap does with its input and the step
Either, ValidatedRuns the step on a Right or a Valid. A Left or an Invalid passes on unchanged, and the step never runs
TryThe same with a Success and a Failure, and an exception the step throws becomes a Failure
Maybe, OptionalRuns the step on a value. An empty input stays empty, and the step never runs
List, NonEmptyListRuns the step on every element and joins the results in order: two inputs that each give two results give four
StreamThe same, lazily: the step runs on each element as the result is consumed
IO, VTaskBuilds 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
CompletableFutureStarts 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:

MethodWhat it doesBuilt as
flatMapIfOrElse(predicate, ifTrue, ifFalse, ma)Chooses the next step by testing the valueflatMap(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 nullmap(_ -> b, ma)
asUnit(ma)Keeps the outcome, and replaces the value with Unitmap(_ -> Unit.INSTANCE, ma)
peek(action, ma)Runs action on the value, and keeps the valuemap(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.

Laws

  • Left identity: running a step on a lifted value is the step. flatMap(f, of(a)) equals f.apply(a).
  • Right identity: running of as the step changes nothing. flatMap(a -> of(a), ma) equals ma.
  • Associativity: grouping the steps differently changes nothing. flatMap(g, flatMap(f, ma)) equals flatMap(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

Common Misunderstandings

  • "flatMap runs the step at once." Either's does. IO's and VTask'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, IO and CompletableFuture among them. List's flatMap runs the step on every element. The behaviour comes from the instance, not from the word "Monad".
  • "flatMap is Stream.flatMap." Stream.flatMap is one instance of the shape: it flattens a stream of streams. Monad's flatMap names the shape for any container.
  • "Nested flatMap calls are the cleanest you can do." They are the most explicit, as flatMap2's body shows. For more than two steps, a For comprehension reads better and avoids the indentation.
  • "You can call .flatMap on a Kind." Kind has no methods. Go through the Monad<F> instance, which knows how to flatten inside F.

You can ship now

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.

Checkpoint: markPaid over a list

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

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.

Checkpoint: flatMapIfOrElse on a Left

On a Left, which branch of flatMapIfOrElse runs: ifTrue or ifFalse?

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

TypesTheir Monad comes from
Every token in WitnessesInstances.monad(token), which always succeeds
Validated, Writer, EitherOrBoth and the transformersInstances with its argument, such as Instances.writer(monoid)
Freenew FreeMonad<>()
Const, FreeAp and FetchNowhere: they have an Applicative and no Monad
EitherF and CoyonedaNowhere: they have a Functor only

What builds on Monad

  • MonadError extends Monad. MonadError, the next page, adds raising an error and recovering from one.
  • MonadZero extends Monad and Alternative. MonadZero adds an empty value, so a chain can filter.
  • For takes a Monad. For.from(monad, source) writes a chain of flatMap calls as a list of steps, as For comprehensions shows.
  • GenericPath takes a Monad. GenericPath.of(kind, monad) turns any Kind that has a Monad into a Path, with via, as GenericPath shows.

See Also

Further Reading

Hands-On Learning

Practise Monad chaining in Tutorial 04: Monad Chaining (8 exercises).


Previous: Applicative Next: MonadError