# Natural transformations by Mark Seemann

*Mappings between functors, with some examples in C#.*

This article is part of a series of articles about functor relationships. In this one you'll learn about natural transformations, which are simply mappings between two functors. It's probably the easiest relationship to understand. In fact, it may be so obvious that your reaction is: *Is that it?*

In programming, a natural transformation is just a function from one functor to another. A common example is a function that tries to extract a value from a collection. You'll see specific examples a little later in this article.

### Laws #

In this, the dreaded section on *laws*, I have a nice surprise for you: There aren't any (that we need worry about)!

In the broader context of category theory there are, in fact, rules that a natural transformation must follow.

"Haskell's parametric polymorphism has an unexpected consequence: any polymorphic function of the type:

alpha :: F a -> G a"where

`F`

and`G`

are functors, automatically satisfies the naturality condition."

While C# isn't Haskell, .NET generics are similar enough to Haskell parametric polymorphism that the result, as far as I can tell, carry over. (Again, however, we have to keep in mind that C# doesn't distinguish between pure functions and impure actions. The knowledge that I infer translates for pure functions. For impure actions, there are no guarantees.)

The C# equivalent of the above `alpha`

function would be a method like this:

G<T> Alpha<T>(F<T> f)

where both `F`

and `G`

are functors.

### Safe head #

Natural transformations easily occur in normal programming. You've probably written some yourself, without being aware of it. Here are some examples.

It's common to attempt to get the first element of a collection. Collections, however, may be empty, so this is not always possible. In Haskell, you'd model that as a function that takes a list as input and returns a `Maybe`

as output:

Prelude Data.Maybe> :t listToMaybe listToMaybe :: [a] -> Maybe a Prelude Data.Maybe> listToMaybe [] Nothing Prelude Data.Maybe> listToMaybe [7] Just 7 Prelude Data.Maybe> listToMaybe [3,9] Just 3 Prelude Data.Maybe> listToMaybe [5,9,2,4,4] Just 5

In many tutorials such a function is often called `safeHead`

, because it returns the *head* of a list (i.e. the first item) in a safe manner. It returns `Nothing`

if the list is empty. In F# this function is called tryHead.

In C# you could write a similar function like this:

public static Maybe<T> TryFirst<T>(this IEnumerable<T> source) { if (source.Any()) return new Maybe<T>(source.First()); else return Maybe.Empty<T>(); }

This extension method (which is really a pure function) is a natural transformation between two functors. The source functor is the list functor and the destination is the Maybe functor.

Here are some unit tests that demonstrate how it works:

[Fact] public void TryFirstWhenEmpty() { Maybe<Guid> actual = Enumerable.Empty<Guid>().TryFirst(); Assert.Equal(Maybe.Empty<Guid>(), actual); } [Theory] [InlineData(new[] { "foo" }, "foo")] [InlineData(new[] { "bar", "baz" }, "bar")] [InlineData(new[] { "qux", "quux", "quuz", "corge", "corge" }, "qux")] public void TryFirstWhenNotEmpty(string[] arr, string expected) { Maybe<string> actual = arr.TryFirst(); Assert.Equal(new Maybe<string>(expected), actual); }

All these tests pass.

### Safe index #

The above *safe head* natural transformation is just one example. Even for a particular combination of functors like *List to Maybe* many natural transformations may exist. For this particular combination, there are infinitely many natural transformations.

You can view the *safe head* example as a special case of a more general set of *safe indexing*. With a collection of values, you can attempt to retrieve the value at a particular index. Since a collection can contain an arbitrary number of elements, however, there's no guarantee that there's an element at the requested index.

In order to avoid exceptions, then, you can try to retrieve the value at an index, getting a Maybe value as a result.

The F# `Seq`

module defines a function called tryItem. This function takes an index and a sequence (`IEnumerable<T>`

) and returns an `option`

(F#'s name for Maybe):

> Seq.tryItem 2 [2;5;3;5];; val it : int option = Some 3

The `tryItem`

function itself is *not* a natural transformation, but because of currying, it's a function that *returns* a natural transformation. When you partially apply it with an index, it becomes a natural transformation: `Seq.tryItem 3`

is a natural transformation `seq<'a> -> 'a option`

, as is `Seq.tryItem 4`

, `Seq.tryItem 5`

, and so on ad infinitum. Thus, there are infinitely many natural transformations from the List functor to the Maybe functor, and *safe head* is simply `Seq.tryItem 0`

.

In C# you can use the various `Func`

delegates to implement currying, but if you want something that looks a little more object-oriented, you could write code like this:

public sealed class Index { private readonly int index; public Index(int index) { this.index = index; } public Maybe<T> TryItem<T>(IEnumerable<T> values) { var candidate = values.Skip(index).Take(1); if (candidate.Any()) return new Maybe<T>(candidate.First()); else return Maybe.Empty<T>(); } }

This `Index`

class captures an index value for potential use against any `IEnumerable<T>`

. Thus, the `TryItem`

method is a natural transformation from the List functor to the Maybe functor. Here are some examples:

[Theory] [InlineData(0, new string[0])] [InlineData(1, new[] { "bee" })] [InlineData(2, new[] { "nig", "fev" })] [InlineData(4, new[] { "sta", "ali" })] public void MissItem(int i, string[] xs) { var idx = new Index(i); Maybe<string> actual = idx.TryItem(xs); Assert.Equal(Maybe.Empty<string>(), actual); } [Theory] [InlineData(0, new[] { "foo" }, "foo")] [InlineData(1, new[] { "bar", "baz" }, "baz")] [InlineData(1, new[] { "qux", "quux", "quuz" }, "quux")] [InlineData(2, new[] { "corge", "grault", "fred", "garply" }, "fred")] public void FindItem(int i, string[] xs, string expected) { var idx = new Index(i); Maybe<string> actual = idx.TryItem(xs); Assert.Equal(new Maybe<string>(expected), actual); }

Since there are infinitely many integers, there are infinitely many such natural transformations. (This is strictly not true for the above code, since there's a finite number of 32-bit integers. Exercise: Is it possible to rewrite the above `Index`

class to instead work with BigInteger?)

The Haskell natural-transformation package offers an even more explicit way to present the same example:

import Control.Natural tryItem :: (Eq a, Num a, Enum a) => a -> [] :~> Maybe tryItem i = NT $ lookup i . zip [0..]

You can view this `tryItem`

function as a function that takes a number and returns a particular natural transformation. For example you can define a value called `tryThird`

, which is a natural transformation from `[]`

to `Maybe`

:

λ tryThird = tryItem 2 λ :t tryThird tryThird :: [] :~> Maybe

Here are some usage examples:

λ tryThird # [] Nothing λ tryThird # [1] Nothing λ tryThird # [2,3] Nothing λ tryThird # [4,5,6] Just 6 λ tryThird # [7,8,9,10] Just 9

In all three languages (F#, C#, Haskell), *safe head* is really just a special case of *safe index*: `Seq.tryItem 0`

in F#, `new Index(0)`

in C#, and `tryItem 0`

in Haskell.

### Maybe to List #

You can also move in the opposite direction: From Maybe to List. In F#, I can't find a function that translates from `option 'a`

to `seq 'a`

(`IEnumerable<T>`

), but there are both Option.toArray and Option.toList. I'll use `Option.toList`

for a few examples:

> Option.toList (None : string option);; val it : string list = [] > Option.toList (Some "foo");; val it : string list = ["foo"]

Contrary to translating from List to Maybe, going the other way there aren't a lot of options: `None`

translates to an empty list, and `Some`

translates to a singleton list.

Using a Visitor-based Maybe in C#, you can implement the natural transformation like this:

public static IEnumerable<T> ToList<T>(this IMaybe<T> source) { return source.Accept(new ToListVisitor<T>()); } private class ToListVisitor<T> : IMaybeVisitor<T, IEnumerable<T>> { public IEnumerable<T> VisitNothing { get { return Enumerable.Empty<T>(); } } public IEnumerable<T> VisitJust(T just) { return new[] { just }; } }

Here are some examples:

[Fact] public void NothingToList() { IMaybe<double> maybe = new Nothing<double>(); IEnumerable<double> actual = maybe.ToList(); Assert.Empty(actual); } [Theory] [InlineData(-1)] [InlineData( 0)] [InlineData(15)] public void JustToList(double d) { IMaybe<double> maybe = new Just<double>(d); IEnumerable<double> actual = maybe.ToList(); Assert.Single(actual, d); }

In Haskell this natural transformation is called maybeToList - just when you think that Haskell names are always abstruse, you learn that some are very explicit and self-explanatory.

If we wanted, we could use the *natural-transformation* package to demonstrate that this is, indeed, a natural transformation:

λ :t NT maybeToList NT maybeToList :: Maybe :~> []

There would be little point in doing so, since we'd need to unwrap it again to use it. Using the function directly, on the other hand, looks like this:

λ maybeToList Nothing [] λ maybeToList $ Just 2 [2] λ maybeToList $ Just "fon" ["fon"]

A `Nothing`

value is always translated to the empty list, and a `Just`

value to a singleton list, exactly as in the other languages.

Exercise: Is this the only possible natural transformation from Maybe to List?

### Maybe-Either relationships #

The Maybe functor is isomorphic to Either where the *left* (or *error*) dimension is unit. Here are the two natural transformations in F#:

module Option = // 'a option -> Result<'a,unit> let toResult = function | Some x -> Ok x | None -> Error () // Result<'a,unit> -> 'a option let ofResult = function | Ok x -> Some x | Error () -> None

In F#, Maybe is called `option`

and Either is called `Result`

. Be aware that the F# `Result`

discriminated union puts the `Error`

dimension to the right of the `Ok`

, which is opposite of Either, where *left* is usually used for errors, and *right* for successes (because what is correct is right).

Here are some examples:

> Some "epi" |> Option.toResult;; val it : Result<string,unit> = Ok "epi" > Ok "epi" |> Option.ofResult;; val it : string option = Some "epi"

Notice that the natural transformation from `Result`

to `Option`

is only defined for `Result`

values where the `Error`

type is `unit`

. You could also define a natural transformation from *any* `Result`

to `option`

:

// Result<'a,'b> -> 'a option let ignoreErrorValue = function | Ok x -> Some x | Error _ -> None

That's still a natural transformation, but no longer part of an isomorphism due to the loss of information:

> (Error "Catastrophic failure" |> ignoreErrorValue : int option);; val it : int option = None

Just like above, when examining the infinitely many natural transformations from List to Maybe, we can use the Haskell *natural-transformation* package to make this more explicit:

ignoreLeft :: Either b :~> Maybe ignoreLeft = NT $ either (const Nothing) Just

`ignoreLeft`

is a natural transformation from the `Either b`

functor to the `Maybe`

functor.

Using a Visitor-based Either implementation (refactored from Church-encoded Either), you can implement an equivalent `IgnoreLeft`

natural transformation in C#:

public static IMaybe<R> IgnoreLeft<L, R>(this IEither<L, R> source) { return source.Accept(new IgnoreLeftVisitor<L, R>()); } private class IgnoreLeftVisitor<L, R> : IEitherVisitor<L, R, IMaybe<R>> { public IMaybe<R> VisitLeft(L left) { return new Nothing<R>(); } public IMaybe<R> VisitRight(R right) { return new Just<R>(right); } }

Here are some examples:

[Theory] [InlineData("OMG!")] [InlineData("Catastrophic failure")] [InlineData("Important information!")] public void IgnoreLeftOfLeft(string msg) { IEither<string, int> e = new Left<string, int>(msg); IMaybe<int> actual = e.IgnoreLeft(); Assert.Equal(new Nothing<int>(), actual); } [Theory] [InlineData(0)] [InlineData(1)] [InlineData(2)] public void IgnoreLeftOfRight(int i) { IEither<string, int> e = new Right<string, int>(i); IMaybe<int> actual = e.IgnoreLeft(); Assert.Equal(new Just<int>(i), actual); }

I'm not insisting that this natural transformation is always useful, but I've occasionally found myself in situations were it came in handy.

### Natural transformations to or from Identity #

Some natural transformations are a little less obvious. If you have a `NotEmptyCollection<T>`

class as shown in my article Semigroups accumulate, you could consider the `Head`

property a natural transformation. It translates a `NotEmptyCollection<T>`

object to a `T`

object.

This function also exists in Haskell, where it's simply called head.

The input type (`NotEmptyCollection<T>`

in C#, `NonEmpty a`

in Haskell) is a functor, but the return type is a 'naked' value. That doesn't look like a functor.

True, a naked value isn't a functor, but it's isomorphic to the Identity functor. In Haskell, you can make that relationship quite explicit:

headNT :: NonEmpty :~> Identity headNT = NT $ Identity . NonEmpty.head

While not particularly useful in itself, this demonstrates that it's possible to think of the `head`

function as a natural transformation from `NonEmpty`

to `Identity`

.

Can you go the other way, too?

Yes, indeed. Consider monadic return. This is a function that takes a 'naked' value and wraps it in a particular monad (which is also, always, a functor). Again, you may consider the 'naked' value as isomorphic with the Identity functor, and thus *return* as a natural transformation:

returnNT :: Monad m => Identity :~> m returnNT = NT $ return . runIdentity

We might even consider if a function `a -> a`

(in Haskell syntax) or `Func<T, T>`

(in C# syntax) might actually be a natural transformation from Identity to Identity... (It is, but only one such function exists.)

### Not all natural transformations are useful #

Are are all functor combinations possible as natural transformations? Can you take any two functors and define one or more natural transformations? I'm not sure, but it seems clear that even if it is so, not all natural transformations are useful.

Famously, for example, you can't get the value out of the IO functor. Thus, at first glance it seems impossible to define a natural transformation *from* `IO`

to some other functor. After all, how would you implement a natural transformation from `IO`

to, say, the Identity functor. That seems impossible.

On the other hand, *this* is possible:

public static IEnumerable<T> Collapse<T>(this IO<T> source) { yield break; }

That's a natural transformation from `IO<T>`

to `IEnumerable<T>`

. It's possible to ignore the input value and *always* return an empty sequence. This natural transformation collapses all values to a single return value.

You can repeat this exercise with the Haskell *natural-transformation* package:

collapse :: f :~> [] collapse = NT $ const []

This one collapses *any* container `f`

to a List (`[]`

), including `IO`

:

λ collapse # (return 10 :: IO Integer) [] λ collapse # putStrLn "ploeh" []

Notice that in the second example, the `IO`

action is `putStrLn "ploeh"`

, which ought to produce the side effect of writing to the console. This is effectively prevented - instead the `collapse`

natural transformation simply produces the empty list as output.

You can define a similar natural transformation from any functor (including `IO`

) to Maybe. Try it as an exercise, in either C#, Haskell, or another language. If you want a Haskell-specific exercise, also define a natural transformation of this type: `Alternative g => f :~> g`

.

These natural transformations are possible, but hardly useful.

### Conclusion #

A natural transformation is a function that translates one functor into another. Useful examples are safe or total collection indexing, including retrieving the first element from a collection. These natural transformations return a populated Maybe value if the element exists, and an empty Maybe value otherwise.

Other examples include translating Maybe values into Either values or Lists.

A natural transformation can easily involve loss of information. Even if you're able to retrieve the first element in a collection, the return value includes only that value, and not the rest of the collection.

A few natural transformations may be true isomorphisms, but in general, being able to go in both directions isn't required. In degenerate cases, a natural transformation may throw away all information and map to a general empty value like the empty List or an empty Maybe value.

**Next:** Traversals.