We are about to discuss natural transformations in the context of practical utility in every day code. It just so happens they are a pillar of category theory and absolutely indispensable when applying mathematics to reason about and refactor our code. As such, I believe it is my duty to inform you about the lamentable injustice you are about to witness undoubtedly due to my limited scope. Let's begin.
I'd like to address the issue of nesting. Not the instinctive urge felt by soon to be mothers wherein they tidy and rearrange with obsessive compulsion, but the...well actually, come to think of it, that isn't far from the mark as we'll see in the coming chapters... In any case, what I mean by nesting is to have two or more different types all huddled together around a value, cradling it like a newborn, as it were.
Until now, we've managed to evade this common scenario with carefully crafted examples, but in practice, as one codes, types tend to tangle themselves up like earbuds in an exorcism. If we don't meticulously keep our types organized as we go along, our code will read hairier than a beatnik in a cat café.
# get_value :: IO -> Task Error (Maybe str)# post_comment :: str -> Task Error Comment# validate :: str -> Either ValidationError str# save_comment :: () -> Task Error (Maybe (Either ValidationError (Task Error Comment)))save_comment = compose(map(map(map(post_comment))),map(map(validate)),get_value('comment'),)
The gang is all here, much to our type signature's dismay. Allow me to briefly explain the code. We start by getting the user input with
get_value('#comment') which is an action which retrieves text from the command line. Now, value string may not exist so it returns
Task Error (Maybe str). After that, we must
map over both the
Task and the
Maybe to pass our text to
validate, which in turn, gives us back
ValidationError or our
str. Then onto mapping for days to send the
str in our current
Task Error (Maybe (Either ValidationError String)) into
post_comment which returns our resulting
What a frightful mess. A collage of abstract types, amateur type expressionism, polymorphic Pollock, monolithic Mondrian. There are many solutions to this common issue. We can compose the types into one monstrous container, sort and
join a few, homogenize them, deconstruct them, and so on. In this chapter, we'll focus on homogenizing them via natural transformations.
A Natural Transformation is a "morphism between functors", that is, a function which operates on the containers themselves. Typewise, it is a function
(Functor f, Functor g) => f a -> g a. What makes it special is that we cannot, for any reason, peek at the contents of our functor. Think of it as an exchange of highly classified information - the two parties oblivious to what's in the sealed manila envelope stamped "top secret". This is a structural operation. A functorial costume change. Formally, a natural transformation is any function for which the following holds:
or in code:
# nt :: (Functor f, Functor g) => f a -> g acompose(map(f), nt) == compose(nt, map(f))
Both the diagram and the code say the same thing: We can run our natural transformation then
map then run our natural transformation and get the same result. Incidentally, that follows from a free theorem though natural transformations (and functors) are not limited to functions on types.
As programmers we are familiar with type conversions. We transform types like
Floats. The difference here is simply that we're working with algebraic containers and we have some theory at our disposal.
Let's look at some of these as examples:
# id_to_maybe :: Identity a -> Maybe aid_to_maybe = lambda x: Maybe(x.value)# id_to_io :: Identity a -> IO aid_to_io = lambda x: IO(x.value)# either_to_task :: Either a b -> Task a beither_to_task = either(Task.rejected, Task)# io_to_task :: IO a -> Task () aio_to_task = lambda x: Task(lambda reject, resolve: resolve(x.unsafe_perform_IO())# maybe_to_task :: Maybe a -> Task () amaybe_to_task = lambda x: Task.rejected() if x.is_nothing else Task(x.value)# array_to_maybe :: [a] -> Maybe aarray_to_maybe = lambda x: Maybe(x)
See the idea? We're just changing one functor to another. We are permitted to lose information along the way so long as the value we'll
map doesn't get lost in the shape shift shuffle. That is the whole point:
map must carry on, according to our definition, even after the transformation.
One way to look at it is that we are transforming our effects. In that light, we can view
io_to_task as converting synchronous to asynchronous or
array_to_maybe from nondeterminism to possible failure.
Suppose we'd like to use some features from another type like
sortBy on a
List. Natural transformations provide a nice way to convert to the target type knowing our
map will be sound.
#arrayToList :: [a] -> List aarray_to_list = Listdo_listy_things = compose(sortBy(h), filter(g), array_to_list, map(f))do_listy_things_ = compose(sortBy(h), filter(g), map(f), array_to_list) # law applied
A wiggle of our nose, three taps of our wand, drop in
array_to_list, and voilà! Our
[a] is a
List a and we can
sortBy if we please.
Also, it becomes easier to optimize / fuse operations by moving
map(f) to the left of natural transformation as shown in
When we can completely go back and forth without losing any information, that is considered an isomorphism. That's just a fancy word for "holds the same data". We say that two types are isomorphic if we can provide the "to" and "from" natural transformations as proof:
# maybe_to_task :: Maybe a b -> Task a bmaybe_to_task = lambda x: Task.rejected() if x.is_nothing else Task(x.value)# task_to_maybe:: Task a b -> Maybe a bmaybe_to_task = lambda x: Task.rejected() if x.is_nothing else Task(x.value)task_to_maybe = lambda x: Maybe(Nothing()) if Task.rejected() else Maybe(x.value)x = Maybe('carrot')task_to_maybe(myabe_to_task(x)) == xy = Task('rabbit')maybe_to_task(task_to_maybe(y)) == y
Task are isomorphic. We can also write a
list_to_array to complement our
array_to_list and show that they are too. As a counter example,
array_to_maybe is not an isomorphism since it loses information:
# maybe_to_array :: Maybe a -> [a]maybe_to_array = lambda x:  if x.is_nothing() else [x.value]# array_to_maybe :: [a] -> Maybe aarray_to_maybe = x => Maybe(x)x = ['elvis costello', 'the attractions']# not isomorphicmaybe_to_array(array_to_maybe(x)) // ['elvis costello']# but is a natural transformationcompose(array_to_maybe, map(replace('elvis', 'lou')))(x) # Maybe('lou costello')# ==compose(map(replace('elvis', 'lou'), array_to_maybe))(x) # Maybe('lou costello')
They are indeed natural transformations, however, since
map on either side yields the same result. I mention isomorphisms here, mid-chapter while we're on the subject, but don't let that fool you, they are an enormously powerful and pervasive concept. Anyways, let's move on.
These structural functions aren't limited to type conversions by any means.
Here are a few different ones:
reverse :: [a] -> [a]join :: (Monad m) => m (m a) -> m ahead :: [a] -> a
The natural transformation laws hold for these functions too. One thing that might trip you up is that
head :: [a] -> a can be viewed as
head :: [a] -> Identity a. We are free to insert
Identity wherever we please whilst proving laws since we can, in turn, prove that
a is isomorphic to
Identity a (see, I told you isomorphisms were pervasive).
Back to our comedic type signature. We can sprinkle in some natural transformations throughout the calling code to coerce each varying type so they are uniform and, therefore,
# get_value :: IO -> Task Error (Maybe str)# post_comment :: str -> Task Error Comment# validate :: str -> Either ValidationError str# save_comment :: () -> Task Error (Maybe (Either ValidationError (Task Error Comment)))save_comment = compose(chain(post_comment),chain(either_to_task),map(validate),chain(io_to_task),get_value('comment'),)
So what do we have here? We've simply added
chain(either_to_task). Both have the same effect; they naturally transform the functor our
Task is holding into another
join the two. Like pigeon spikes on a window ledge, we avoid nesting right at the source. As they say in the city of light, "Mieux vaut prévenir que guérir" - an ounce of prevention is worth a pound of cure.
Natural transformations are functions on our functors themselves. They are an extremely important concept in category theory and will start to appear everywhere once more abstractions are adopted, but for now, we've scoped them to a few concrete applications. As we saw, we can achieve different effects by converting types with the guarantee that our composition will hold. They can also help us with nested types, although they have the general effect of homogenizing our functors to the lowest common denominator, which in practice, is the functor with the most volatile effects (
Task in most cases).
This continual and tedious sorting of types is the price we pay for having materialized them - summoned them from the ether. Of course, implicit effects are much more insidious and so here we are fighting the good fight. We'll need a few more tools in our tackle before we can reel in the larger type amalgamations. Next up, we'll look at reordering our types with Traversable.