How the Encoding Works

Write "any container F" in Java: a witness names the container, and Kind<F, A> carries the name.

"since words are only names for things, it would be more convenient for all men to carry about them such things as were necessary to express a particular business they are to discourse on."

— Jonathan Swift, Gulliver's Travels (Part III, Chapter V)

The sages of Lagado gave up words and carried the things themselves. Java cannot carry a type constructor about, so Higher-Kinded-J carries a name for one instead: the witness.

A head in profile, made of jigsaw pieces printed with gears and sketches, its top pieces lifting away

What You'll Learn

  • Read a Kind<F, A> and name the container its witness stands for
  • Move a value into the encoding with widen and back with narrow, and say what each costs
  • Declare the WitnessArity bound on a generic method
  • Predict what a core type does with null, and return Unit or a Maybe instead
  • Tell an encoding failure from a domain failure

See Example Code

The code on this page is EncodingBook.java: the page includes it, so the build compiles and runs it. EncodingBookTest.java holds each claim the page makes.


Why Java needs an encoding

Java can abstract over a type, as List<T> does over T, but not over a type constructor such as List itself. A method for "any container of integers" does not compile:

<F> F<Integer> doubleAll(F<Integer> numbers) {
    return numbers;
}

javac answers unexpected type, with found: type parameter F: a type parameter cannot take type arguments of its own. A language with higher-kinded types can name such a parameter, written F<_> in this book: "a container still waiting for its element type". It is not Java's ? wildcard, which stands for an unknown type rather than a missing one. Why Higher-Kinded Types? says what this buys. Higher-Kinded-J gets there with ordinary interfaces. Each container gets a name, and generic code passes the name about in place of the container. The technique is called defunctionalisation.

The witness and Kind<F, A>

A witness is an empty class that stands for one container. ListKind.Witness stands for List, MaybeKind.Witness for Maybe, and EitherKind.Witness<L> for Either with its left type L fixed. Its constructor is private, so nothing ever creates one: a witness appears only as a type argument.

Kind<F, A> is the interface that generic code works with. It reads "a container named by F, holding A", so Kind<ListKind.Witness, String> is the Kind view of a List<String>. A type class such as Monad<F> is written over Kind<F, A>, so one Monad interface serves every container that has a witness.

Two helpers cross between a value and its Kind view: widen takes the value into the encoding, and narrow brings it back. Here flatMap takes a Kind and gives one back, and only the Either instance behind monad looks inside:

    Monad<EitherKind.Witness<String>> monad = Instances.monad(either());

    Either<String, Integer> start = Either.right(10);
    // widen: the same Either, seen as a Kind
    Kind<EitherKind.Witness<String>, Integer> kind = EITHER.widen(start);
    // flatMap takes the function first, then the Kind, and returns a Kind
    Kind<EitherKind.Witness<String>, String> result =
        monad.flatMap(i -> EITHER.widen(Either.right("v=" + i)), kind);
    // narrow: back to an Either
    Either<String, String> finalEither = EITHER.narrow(result);
    // Right(v=10)

EITHER is the helper that EitherKindHelper provides for widen and narrow, and each type has one, such as MAYBE or LIST. Instances.monad(either()) is the value that knows how to flatMap an Either, and Obtaining Instances is the page on asking for one. Lifting the Hood traces the same round trip call by call, with what each step allocates. The type system glossary defines each of these terms in a line.

The WitnessArity bound

A witness also declares how many type arguments its container still needs: its arity. Kind asks for that declaration in its bound, Kind<F extends WitnessArity<?>, A>, so a class that is not a witness cannot stand in for F:

// ListKind.Witness: one type argument still missing, like List<_>
final class Witness implements WitnessArity<TypeArity.Unary> {
    private Witness() {}
}

// EitherKind2.Witness: two type arguments still missing, like Either<_, _>
final class Witness implements WitnessArity<TypeArity.Binary> {
    private Witness() {}
}

Most type classes, Functor and Monad among them, ask for a unary witness. Either has two type arguments, so its Monad fixes the left one, and EitherKind.Witness<L> is unary. Bifunctor and Profunctor take a binary witness, over Kind2. A generic method puts the same bound on its own F, as totals does in the Foundations introduction: <F extends WitnessArity<TypeArity.Unary>>. Type Arity covers the rest.

The pieces each type provides

Every container that joins the encoding brings the same pieces. They differ in one respect: whether the container is its own Kind, or is held in a small record that is.

PieceA type that is its own Kind: MaybeA type held in a record: Optional
WitnessMaybeKind.WitnessOptionalKind.Witness
Kind interfaceMaybeKind<A>, which Maybe itself extendsOptionalKind<A>, which a holder record implements
HelperMAYBE, on MaybeKindHelperOPTIONAL, on OptionalKindHelper
widenReturns the same object: a Maybe already is its KindWraps the Optional in the holder, one allocation
narrowChecks the type, then castsChecks for the holder, then returns the Optional it holds
Type class instancesMaybeMonad, MaybeTraverse and othersOptionalMonad, OptionalTraverse and others

The JDK's types cannot implement Kind, so they are held, and so are two of the library's own: Lazy and Tuple2. A type that is its own Kind crosses into the encoding without an allocation, and a debugger shows the Maybe itself, not a holder. Adding Your Own Type shows how to give a type of your own these pieces.

Values, never null

Higher-Kinded-J's own types hold a value, never null. They refuse it at the factory, and a map function that returns null fails them, so an absent value shows in the type. Maybe and Id treat null differently:

TypeA null valueA map function that returns null
Either, Try, Validated, EitherOrBoth, NonEmptyList, IO, VTask, Lazy, Reader, Context, State, Writer, Free and TrampolineRefused: Either.right(null) and Instances.monad(either()).of(null) throw NullPointerExceptionFails: Either throws at once, Try gives a Failure, and IO fails when it runs
MaybeRead as Nothing by Maybe.fromNullable and by the instance's of, though Maybe.just(null) throwsRead as Nothing
IdHeldHeld

When a step has nothing to return, return Unit. When a value may be absent, hold it in a Maybe. A fold is the way out, and holds nothing, so it can return null to code that takes it, such as a nullable query parameter. A nullness checker needs the result type named: parsed.<@Nullable Integer>fold(_ -> null, n -> n). The JDK containers, the transformers and the tuples have rules of their own, in Where null is read or held. A null also takes a value outside the type class laws, as Laws and Where HKJ Bends Them says.

What a nullness checker sees says which of these refusals a checker reports at compile time.

Unit: a value for "nothing to return"

void is not a type, so it cannot fill the A in Kind<F, A>. Java's own stand-in, Void, has only null as a value, which the types on this page refuse. org.higherkindedj.hkt.Unit has exactly one value, Unit.INSTANCE. An action run for its effect gives Unit, and a type whose failure carries no detail takes Unit as its error type, as Maybe's MonadError does:

    // run for its effect, with nothing to return, so it gives Unit
    Kind<IOKind.Witness, Unit> confirm =
        IO_OP.delay(
            () -> {
              System.out.println("Order confirmed");
              return Unit.INSTANCE;
            });
    IO_OP.unsafeRunSync(confirm);

    // Maybe's error type is Unit, so raising it gives Nothing
    MonadError<MaybeKind.Witness, Unit> maybeErrors = Instances.monadError(maybe());
    Maybe<String> absent = MAYBE.narrow(maybeErrors.raiseError(Unit.INSTANCE));
    // Nothing

The source is Unit.java.

You can ship now

You can now run any type class over a value you hold: widen it, call the instance, and narrow the result, returning Unit or a Maybe where you might have returned null. The rest of this page is for when a null turns up or narrow throws.

Checkpoint: a unary witness where a binary one goes

EitherKind.Witness<String> names Either with its left type fixed. Can it stand in for F in Bifunctor<F>, which maps both sides of a two-sided type?

Bifunctor<EitherKind.Witness<String>> bifunctor;

Answer and why

No: javac refuses it, saying the witness "is not within bounds of type-variable" F. Bifunctor takes a binary witness, over Kind2, and EitherKind.Witness<L> is unary, because fixing the left type leaves one argument missing. EitherKind2.Witness, with both missing, is the one Bifunctor takes.

Where this lives: The WitnessArity bound.

Checkpoint: of(null) in two containers

What does Instances.monad(maybe()).of(null) give back, and what does Instances.monad(try_()).of(null) do?

Answer and why

Nothing, and it throws NullPointerException. Maybe's instance reads a null value as Nothing, and Try refuses one, as every library type in the table does except Maybe and Id. So code written for any F never hands null to of: what comes back depends on F.

Where this lives: Values, never null.


The fine print

Where null is read or held

Some types read null as empty, or hold it, by design:

  • The JDK containers' instances read null as empty. of(null) gives an empty Optional, List or Stream, and a CompletableFuture completed with null.
  • MaybeT and OptionalT read null as Maybe and Optional do. Their of(null) gives an empty inner value.
  • The tuples hold whatever they are given. Tuple.of(null, null) builds a Tuple2 of two nulls.
  • Const ignores the value. It never holds one, so of(null) gives the monoid's empty value.

So generic code never hands null to of: what comes back depends on F. A flatMap function must return a Kind in every type, so one that returns null throws KindUnwrapException.

What a nullness checker sees

Every hkj-core package is @NullMarked, so a JSpecify nullness checker such as NullAway checks each call against the types the library declares. It flags a nullable value passed to Either.right or VTask.succeed, and a map function or a VTask written as a lambda that returns one.

In JSpecify mode alone, NullAway checks what a lambda returns against Function and the interfaces that extend it, such as UnaryOperator, and against no other functional interface from the JDK. So it never checks a lambda or method reference passed as a Supplier, a Callable or a BiFunction. A lambda that returns a @Nullable field compiles when passed to VTask.of, and the task fails only when it runs, with callable must not return null. Try.of gives a Failure holding a NullPointerException, supplier must not return null, and an IO built by IO.delay fails when it runs with thunk must not return null.

NullAway checks a lambda or method reference given to Try.attempt or Lazy.defer in JSpecify mode alone, since they take the library's own interfaces. For the rest, two NullAway options close most of the gap:

A null returned throughIn JSpecify mode aloneWith both options
A lambda or method reference passed as a Supplier, Callable or BiFunction, as to Try.of, VTask.of, IO.delay, Path.tryOf, Path.io, Path.vtask or VStream.zipWithMissedFlagged
A Supplier<@Nullable T> or Callable<@Nullable T> variable, where the parameter is Supplier<A> or Callable<A>, as VTask.of and IO.delay takeFlaggedFlagged
The same variable, where the parameter is Supplier<? extends A>, as Try.of and Path.lazyDefer takeMissedFlagged
A method reference to such a variable, as in Try.of(s::get)MissedMissed

So pass a supplier variable itself, never as s::get.

Set -XepOpt:NullAway:JSpecifyJDKModels=true and -XepOpt:NullAway:HandleWildcardGenerics=true beside your build's other NullAway options. Both need JSpecify mode, -XepOpt:NullAway:JSpecifyMode=true. JSpecifyJDKModels arrived in NullAway 0.14.0, and the library checks both options with 0.14.2 today. The net.ltgt.errorprone Gradle plugin takes each as an option, as in option("NullAway:JSpecifyJDKModels", "true"). The models annotate much of the JDK, so your own code is held to them too: a dereferenced System.getProperty result is flagged.

When narrow throws

Two kinds of failure meet in this encoding, and they are handled differently:

  • A domain failure is a value. A Left, a Nothing, a Try.Failure or a failed CompletableFuture travels inside its container, and the type's own methods or MonadError's handleErrorWith recover from it.
  • An encoding failure is a bug. narrow throws KindUnwrapException, an unchecked IllegalArgumentException, for null or another container's Kind, as does a flatMap function that returns null. Fix the mismatch rather than catch it.

Hands-On Learning

Practise widening and narrowing in Tutorial 01: Kind Basics (5 exercises).


Previous: One Line, Six Layers Next: Working with Kind