Natural Transformation

Polymorphic Functions Between Type Constructors

Two Sentences

A natural transformation is a function that converts every F<A> into a G<A>, for any A, without ever looking at the value inside. It changes the container, never the cargo.

F<A>  ────  Natural<F, G>  ────▶  G<A>

If we have used Higher-Kinded-J for more than a few hours, we have already called several. MaybePath::toEitherPath is one. Either::toMaybe is another. The interface in this section is just the formalisation, plus the laws that keep these transformations honest.

Everyday Examples

The pattern is the same in every row: a rule about the shape of the input that knows nothing about what the input contains.

The Interface

@FunctionalInterface
public interface Natural<F, G> {

    <A> Kind<G, A> apply(Kind<F, A> fa);

    default <H> Natural<F, H> andThen(Natural<G, H> after);

    default <E> Natural<E, G> compose(Natural<E, F> before);

    static <F> Natural<F, F> identity();
}

Three things to notice:

1. The <A> is on apply, not on the interface. A single Natural<F, G> works for every element type. That polymorphism is the entire point.
2. It is a @FunctionalInterface, so most transformations are written as a one-line lambda.
3. andThen and compose exist because we want to chain transformations, and identity() exists because chains need a sensible starting point.

Three Worked Transformations

Maybe ~> List

import static org.higherkindedj.hkt.maybe.MaybeKindHelper.MAYBE;
import static org.higherkindedj.hkt.list.ListKindHelper.LIST;

Natural<MaybeKind.Witness, ListKind.Witness> maybeToList = new Natural<>() {
    @Override
    public <A> Kind<ListKind.Witness, A> apply(Kind<MaybeKind.Witness, A> fa) {
        Maybe<A> maybe = MAYBE.narrow(fa);
        List<A> list = maybe.fold(
            () -> List.of(),
            value -> List.of(value));
        return LIST.widen(list);
    }
};

Kind<MaybeKind.Witness, String> hello   = MAYBE.widen(Maybe.just("hello"));
Kind<ListKind.Witness, String>  asList  = maybeToList.apply(hello);
// LIST.narrow(asList) -> ["hello"]

Either ~> Maybe (discarding the error)

Natural<EitherKind.Witness<String>, MaybeKind.Witness> eitherToMaybe = new Natural<>() {
    @Override
    public <A> Kind<MaybeKind.Witness, A> apply(Kind<EitherKind.Witness<String>, A> fa) {
        Either<String, A> either = EITHER.<String, A>narrow(fa);
        return MAYBE.widen(
            either.fold(left -> Maybe.nothing(), Maybe::just));
    }
};

List ~> Maybe (head)

Natural<ListKind.Witness, MaybeKind.Witness> listHead = new Natural<>() {
    @Override
    public <A> Kind<MaybeKind.Witness, A> apply(Kind<ListKind.Witness, A> fa) {
        List<A> list = LIST.narrow(fa);
        return MAYBE.widen(
            list.isEmpty() ? Maybe.nothing() : Maybe.just(list.get(0)));
    }
};

In all three cases, the body never inspects the element type. That is the discipline Natural enforces.

The Naturality Law

A transformation that calls itself "natural" must obey one rule:

For any function f: A -> B and any value fa: F<A>, nat.apply(map(f, fa)) equals map(f, nat.apply(fa)).

In a diagram:

            map(f)
   F<A>  ──────────▶  F<B>
    │                   │
   nat                 nat
    ▼                   ▼
   G<A>  ──────────▶  G<B>
            map(f)

Either route to the bottom-right corner gives the same answer. Concretely: it does not matter whether we map and then transform, or transform and then map. The container changes; the value does not.

Why This Matters

If a transformation peeks at A and behaves differently for Integer than for String, it is no longer structure-preserving and the naturality square stops commuting. The moment that happens, every reasoning we want to do about composition stops holding. We can no longer freely refactor nat.apply(map(f, x)) into map(f, nat.apply(x)), and the abstraction has cost us nothing while delivering nothing.

The discipline is not pedantic; it is what makes natural transformations useful.

Composition

Natural transformations chain like ordinary functions, with andThen and compose:

Natural<F, G> fg = ...;
Natural<G, H> gh = ...;

Natural<F, H> fh = fg.andThen(gh);     // F ~> G ~> H

Composition is associative. Identity is Natural.identity():

Natural<F, F> id = Natural.identity();   // id.apply(fa) == fa
Natural.identity().andThen(nat).equals(nat);
nat.andThen(Natural.identity()).equals(nat);

These laws are the same laws categories obey. We do not need the category-theory background to use them; we just need to know that chaining is well-behaved and we can trust it.

Where This Shows Up

Free Monad Interpreters

The most common use is interpreting Free monads. A Free program is built from an instruction set F. To run it, we provide a natural transformation F ~> M, where M is the target effect (often IO).

sealed interface ConsoleOp<A> {
    record PrintLine(String text) implements ConsoleOp<Unit> {}
    record ReadLine() implements ConsoleOp<String> {}
}

Natural<ConsoleOpKind.Witness, IOKind.Witness> interpreter = new Natural<>() {
    @Override
    public <A> Kind<IOKind.Witness, A> apply(Kind<ConsoleOpKind.Witness, A> fa) {
        ConsoleOp<A> op = CONSOLE_OP.narrow(fa);
        return switch (op) {
            case ConsoleOp.PrintLine p -> IO_OP.widen(IO.delay(() -> {
                System.out.println(p.text());
                return (A) Unit.INSTANCE;
            }));
            case ConsoleOp.ReadLine r -> IO_OP.widen(IO.delay(() -> (A) scanner.nextLine()));
        };
    }
};

Free<ConsoleOpKind.Witness, String> program = ...;
Kind<IOKind.Witness, String> executable = program.foldMap(interpreter, ioMonad);

The interpreter is the place where the program meets the world. Swapping it for a test interpreter (one that returns canned input and records prints) is how we test Free programs without mocking. The interpreter is a Natural, full stop.

Monad Transformer Lifting

Every lift on a monad transformer (IO ~> EitherT<IO, E, ?>, for example) is a natural transformation. The same shape applies; the cargo is preserved; the container deepens by one layer.

Coyoneda Lowering

Coyoneda.lower runs internally as a natural transformation. We rarely need to know that, but it explains why the lowering is law-abiding without extra hand-waving.

Back to the One-Liner

Once again the line:

repo.find(id)
    .toEitherPath()           // <-- natural transformation: MaybePath ~> EitherPath
    .focus().attributes().at(key)
    .modify(spec::validateAndCoerce)
    .flatMap(repo::save);

.toEitherPath() is the everyday face of a natural transformation. It takes whatever was inside the MaybePath (a found node, or absence) and produces the equivalent EitherPath (a Right with the node, or a typed Left carrying the not-found error). The element type A does not matter; the rule converts the shape. That is precisely what Natural is for.

The reason this composes with everything downstream is that Natural is law-abiding: anything we could have done to the value inside the MaybePath we can equally do to the value inside the EitherPath after the transformation, and the answer agrees. That is naturality, doing useful work without us thinking about it.

When to Reach for Natural

Good use cases:

1. Free monad and Free applicative interpretation. The primary reason the type exists.
2. Converting between similar containers in generic code. Hand-rolling each conversion is fine for one-offs; defining a Natural is the move when the conversion is reused across the codebase.
3. Swapping interpreters at runtime. Production interpreter, test interpreter, dry-run interpreter; same program, three different Naturals.
4. Lifting through transformer stacks. Moving a value up a stack of transformers is naturality at work.

When we do not need a Natural: if we only need to convert one specific Maybe<String> to a List<String> once, write a method. Natural earns its keep when the polymorphism does.

Things People Get Wrong

Identity, Composition, Laws

// Left identity
Natural.identity().andThen(nat).equals(nat);

// Right identity
nat.andThen(Natural.identity()).equals(nat);

// Associativity
fg.andThen(gh).andThen(hi).equals(fg.andThen(gh.andThen(hi)));

These are the same laws functions obey. Natural is, deliberately, just a function with extra discipline.

Relationship to Other Concepts

Previous: Bifunctor Next: For Comprehension