Natural Transformation
Turn one container into another, such as a Maybe into a List, whatever value it holds.
"One morning, when Gregor Samsa woke from troubled dreams, he found himself transformed in his bed into a horrible vermin."
— Franz Kafka, Metamorphosis (trans. David Wyllie)
Gregor wakes in a new shell with the same thoughts: maybeToList gives a line item a new container, and leaves the item as it was.
- Say what a natural transformation is, and how it differs from
map - Write one as a generic method and use it as a
Naturalthrough a method reference - Chain transformations with
andThen, and start a chain fromNatural.identity() - Check a transformation against the naturality law
- Find the interpreters and conversions in the library that take a
Natural
The code on this page is NaturalBook.java: the page includes it, so the build compiles and runs it. NaturalBookTest.java holds what the page says each transformation does, and FoundationsLawsBookTest.java checks the laws.
The container changes, never the cargo
A natural transformation turns every F<A> into a G<A>, for any A, without looking at the value inside. It changes the container, never the cargo. Functor's map does the opposite: it changes the value and keeps the container.
You have called some already. optional.stream() turns an Optional into a Stream, and list.stream().findFirst() turns a List into an Optional. The library adds maybe.toOptional(), Try.toEither(mapper) and, on an Effect Path, MaybePath.toEitherPath(error). Application code stays with methods like these.
This page writes three over the Kind encoding, as an interpreter needs:
| From | To | The rule |
|---|---|---|
Maybe<A> | List<A> | Nothing becomes [], and Just(x) becomes [x] |
List<A> | Maybe<A> | Keep the first element, if there is one |
Either<E, A> | Maybe<A> | Left becomes Nothing, and Right(x) becomes Just(x) |
Each rule is about the shape of its input, and none needs to know what the input holds.
Write one as a generic method
The code on this page uses these imports, with LineItem from the order records the Optics chapter introduces:
import static org.higherkindedj.hkt.either.EitherKindHelper.EITHER;
import static org.higherkindedj.hkt.list.ListKindHelper.LIST;
import static org.higherkindedj.hkt.maybe.MaybeKindHelper.MAYBE;
import java.util.List;
import org.higherkindedj.example.book.optics.cast.LineItem;
import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.Natural;
import org.higherkindedj.hkt.either.Either;
import org.higherkindedj.hkt.either.EitherKind;
import org.higherkindedj.hkt.list.ListKind;
import org.higherkindedj.hkt.maybe.Maybe;
import org.higherkindedj.hkt.maybe.MaybeKind;
Natural<F, G> has one abstract method, <A> Kind<G, A> apply(Kind<F, A> fa). Its <A> is on the method, not the interface, so one Natural works for every element type. That also means a lambda cannot implement it, since a Java lambda cannot be generic:
Natural<MaybeKind.Witness, ListKind.Witness> toList = fa -> NaturalBook.maybeToList(fa);
javac refuses it with "invalid functional descriptor for lambda expression". Write each conversion as a generic method:
// Each works for every A, and none looks at the value it carries
public static <A> Kind<ListKind.Witness, A> maybeToList(Kind<MaybeKind.Witness, A> fa) {
Maybe<A> maybe = MAYBE.narrow(fa);
return LIST.widen(maybe.isJust() ? List.of(maybe.get()) : List.of());
}
public static <A> Kind<MaybeKind.Witness, A> eitherToMaybe(
Kind<EitherKind.Witness<String>, A> fa) {
return MAYBE.widen(EITHER.<String, A>narrow(fa).fold(error -> Maybe.nothing(), Maybe::just));
}
public static <A> Kind<MaybeKind.Witness, A> firstOf(Kind<ListKind.Witness, A> fa) {
List<A> list = LIST.narrow(fa);
return list.isEmpty() ? MAYBE.nothing() : MAYBE.just(list.getFirst());
}
A method reference makes one a Natural. LAMP is a lamp line item: Just(LAMP) becomes a one-element list, and Nothing an empty one.
Natural<MaybeKind.Witness, ListKind.Witness> toList = NaturalBook::maybeToList;
List<LineItem> found = LIST.narrow(toList.apply(MAYBE.just(LAMP)));
// [LineItem[sku=LAMP, quantity=1, price=40.00]]
List<LineItem> notFound = LIST.narrow(toList.apply(MAYBE.nothing()));
// []
Chaining
andThen runs one transformation and then another, and compose runs them the other way round. Natural.identity() returns its input unchanged, so it can start a chain built in a loop. Here a Right becomes a one-element list, and a Left an empty one, its error dropped:
Natural<EitherKind.Witness<String>, MaybeKind.Witness> toMaybe = NaturalBook::eitherToMaybe;
Natural<EitherKind.Witness<String>, ListKind.Witness> eitherToList = toMaybe.andThen(toList);
List<LineItem> priced = LIST.narrow(eitherToList.apply(EITHER.widen(Either.right(LAMP))));
// [LineItem[sku=LAMP, quantity=1, price=40.00]]
List<LineItem> unpriced =
LIST.narrow(eitherToList.apply(EITHER.widen(Either.left("no price for LAMP"))));
// []
The naturality law
One rule makes a transformation natural: for any function f, mapping f and then converting gives what converting and then mapping gives.
map(f)
F<A> ──────────▶ F<B>
│ │
nat nat
▼ ▼
G<A> ──────────▶ G<B>
map(f)
Both routes to the bottom-right corner give the same answer. That is what lets you move a conversion before or after a map without changing the result.
- Naturality: converting and mapping can swap places.
nat.apply(map(f, fa))equalsmap(f, nat.apply(fa)), for every functionfand valuefa. - Identity: the identity changes nothing, on either side.
Natural.identity().andThen(nat).apply(fa)equalsnat.apply(fa), and so doesnat.andThen(Natural.identity()).apply(fa). - Associativity: grouping a chain differently changes nothing.
f.andThen(g).andThen(h).apply(fa)equalsf.andThen(g.andThen(h)).apply(fa).
The laws compare what each side gives for the same input. Two Naturals are different objects, so equals between them says nothing. The laws assume functions that never return null, and Values, never null says what each type does with one. A transformation that looks at the value inside, such as one that treats an Integer differently from a String, breaks the naturality law, and is a function of another kind.
Checking these laws with hkj-test is not supported yet, so the test checks them by hand, for maybeToList and firstOf. It uses these imports, with JUnit's, and ORDER is any Order:
import static org.assertj.core.api.Assertions.assertThat;
import static org.higherkindedj.hkt.instances.Witnesses.list;
import static org.higherkindedj.hkt.instances.Witnesses.maybe;
import static org.higherkindedj.hkt.list.ListKindHelper.LIST;
import static org.higherkindedj.hkt.maybe.MaybeKindHelper.MAYBE;
import java.util.List;
import java.util.function.BiPredicate;
import java.util.function.Function;
import org.higherkindedj.example.book.foundations.natural.NaturalBook;
import org.higherkindedj.example.book.optics.cast.Order;
import org.higherkindedj.hkt.Functor;
import org.higherkindedj.hkt.Kind;
import org.higherkindedj.hkt.Natural;
import org.higherkindedj.hkt.TypeArity;
import org.higherkindedj.hkt.WitnessArity;
import org.higherkindedj.hkt.assertions.KindEquivalence;
import org.higherkindedj.hkt.instances.Instances;
import org.higherkindedj.hkt.list.ListKind;
import org.higherkindedj.hkt.maybe.MaybeKind;
<F extends WitnessArity<TypeArity.Unary>, G extends WitnessArity<TypeArity.Unary>, A, B>
void assertNaturality(
Natural<F, G> nat,
Functor<F> from,
Functor<G> to,
Kind<F, A> fa,
Function<A, B> f,
BiPredicate<Kind<G, ?>, Kind<G, ?>> same) {
// mapping and then converting equals converting and then mapping
assertThat(same.test(nat.apply(from.map(f, fa)), to.map(f, nat.apply(fa)))).isTrue();
}
@Test
@DisplayName("maybeToList and firstOf are natural, and andThen keeps identity and grouping")
void naturalLaws() {
Natural<MaybeKind.Witness, ListKind.Witness> toList = NaturalBook::maybeToList;
Natural<ListKind.Witness, MaybeKind.Witness> first = NaturalBook::firstOf;
BiPredicate<Kind<ListKind.Witness, ?>, Kind<ListKind.Witness, ?>> sameList =
KindEquivalence.byEqualsAfter(LIST::narrow);
BiPredicate<Kind<MaybeKind.Witness, ?>, Kind<MaybeKind.Witness, ?>> sameMaybe =
KindEquivalence.byEqualsAfter(MAYBE::narrow);
for (Kind<MaybeKind.Witness, Order> fa : List.of(MAYBE.just(ORDER), MAYBE.<Order>nothing())) {
assertNaturality(
toList,
Instances.functor(maybe()),
Instances.functor(list()),
fa,
Order::customer,
sameList);
// the identity, on either side, changes nothing
assertThat(
sameList.test(
Natural.<MaybeKind.Witness>identity().andThen(toList).apply(fa),
toList.apply(fa)))
.isTrue();
assertThat(sameList.test(toList.andThen(Natural.identity()).apply(fa), toList.apply(fa)))
.isTrue();
// grouping the conversions differently changes nothing
assertThat(
sameList.test(
toList.andThen(first).andThen(toList).apply(fa),
toList.andThen(first.andThen(toList)).apply(fa)))
.isTrue();
}
Order second =
new Order(
ORDER.id(),
ORDER.customer(),
List.of(),
ORDER.placedAt(),
ORDER.currency(),
ORDER.status());
for (List<Order> orders : List.of(List.<Order>of(), List.of(ORDER), List.of(ORDER, second))) {
assertNaturality(
first,
Instances.functor(list()),
Instances.functor(maybe()),
LIST.widen(orders),
Order::lines,
sameMaybe);
}
}
Where the library takes one
A Free program holds its steps, its instructions, as data. An interpreter runs it by turning each instruction into a real effect, and that turning is a Natural.
- A Free program's interpreter is a
Natural.program.foldMap(interpreter, monad)runs a program by converting each instruction with aNatural<F, M>, and aFreeApprogram'sfoldMapdoes the same with an applicative. A test interpreter is anotherNaturalfor the same program, andFreePath.foldMaptakes one too. Free.translate(program, nat, functor)moves a program from one instruction set to another. EitherF shows it.Interpreters.combinejoins two interpreters into one. A program over two instruction sets needs it, as EitherF shows.EffectBoundary.oftakes the interpreter toIOthat runs a program at the edge.- A transformer's
mapTtakesnat::apply.EitherT,MaybeT,OptionalT,ReaderT,StateTandWriterTeach have one. It changes the outer container, for example fromIOtoVTask, and leaves the inner value alone. GenericPath.mapK(nat, monad)moves a path to another container.VStreamTransformationsgives theNaturals betweenVStream,ListandStream, as the VStream Advanced Features page shows.
Things people get wrong
- "A
Naturalis a lambda." Itsapplyis generic, and a Java lambda cannot be. Write a generic method, and pass it as a method reference. - "I can branch on
A." Not in a natural transformation. A body that inspects the value, withinstanceoffor example, compiles, but it breaks the naturality law. - "A natural transformation keeps every value." It keeps the values it keeps unchanged, but it may drop some:
firstOfkeeps only the first element, andeitherToMaybedrops the error. Both are natural. - "Naturality is theory I can ignore." It is what lets you move a conversion past a
map. An interpreter that breaks it gives a program a meaning that depends on where its steps were mapped.
- Functor: the
mapthat the naturality law is stated in - Free Monad: programs that a
Naturalinterprets - Free Applicative: independent programs that a
Naturalinterprets
- Bartosz Milewski, Natural Transformations: an introduction with diagrams
Practise natural transformations in Tutorial 08: Natural Transformation (5 exercises).
Previous: Foldable and Traverse Next: Selective