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
FandGare 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.
