Author: Bartosz Milewski

Arrows as Functions

A category consists of objects and arrows that go between them.

Properties of Composition

Composition is associative.

For every object ๐ด there is an arrow which is a unit of composition. This arrow loops from the object to itself.

Composition is the Essence of Programming

Neutral values like zero or id are extremely useful when working with symbolic variables. Thatโ€™s why Romans were not very good at algebra, whereas the Arabs and the Persians, who were familiar with the concept of zero, were.

of code to create solutions to larger problems. Decomposition wouldnโ€™t make sense if we werenโ€™t able to put the pieces back together.

Challenges

Category theory is extreme in the sense that it actively discourages us from looking inside the objects. An object in category theory is an abstract nebulous entity. All you can ever know about it is how it relates to other objects โ€” how it connects with them using arrows.

But not any two arrows can be composed.

designing the types. Later, type annotations drive the implementation and become compiler-enforced comments.

a two-element set of True and False. Type Char is a set of all Unicode characters like a or ฤ….

โ€” it just knows the answer. A Haskell function has to calculate the answer. Itโ€™s not a problem if the answer can be obtained in a finite number of steps โ€” however big that number might be.

Why Do We Need a Mathematical Model?

Functions that may return bottom are called partial, as opposed to total functions, which return valid results for every possible argument.

The problem is that itโ€™s very hard to prove things about programs using operational semantics. To show a property of a program you essentially have to โ€œrun itโ€ through the idealized interpreter.

Whatโ€™s the mathematical model for reading a character from the keyboard or sending a packet across the network? For the longest time that would have been an awkward question leading to a rather convoluted explanation. It seemed like denotational semantics wasnโ€™t the best fit for a considerable number of important tasks that were essential for writing useful programs, and which could be easily tackled by operational semantics. The breakthrough came from category theory.

Examples of Types

2.5 Pure and Dirty Functions

2.6 Examples of Types

In Haskell, however, there is a symbol for this value: an empty pair of parentheses, ().

A pure function that returns unit does nothing: it discards its argument.

Pure functions from Bool just pick two values from the target type, one corresponding to True and another to False. Functions to Bool are called predicates.

Simple Graphs

Y ou can get real appreciation for categories by studying a variety of examples. Categories come in all shapes and sizes and often pop up in unexpected places.

Monoid as Set

A set of morphisms from object ๐‘Ž to object ๐‘ in a category ๐‚ is called a hom-set and is written as ๐‚(๐‘Ž, ๐‘) (or, sometimes, Hom๐‚(๐‘Ž, ๐‘)).

a monoid is defined as a set with a binary operation. All thatโ€™s required from this operation is that itโ€™s associative, and that there is one special element that behaves like a unit with respect to it.

mempty and mappend (i.e., the fact that mempty is neutral and that mappend is associative). Itโ€™s the responsibility of the programmer to make sure they are satisfied.

The former translates into equality of morphisms in the category Hask (or ๐’๐ž๐ญ, if we ignore bottoms, which is the name for never-ending calculations)

Challenges

we can always recover a set monoid from a category monoid. For all intents and purposes they are one and the same.

Kleisli Categories

You know that this is not a pure function, because its memoized version would fail to produce a log. This function has side effects.

main purpose of the

function negate is to turn one Boolean into another. The logging is secondary.

We want to modify the functions toUpper and toWords so that they piggyback a message string on top of their regular return values.

We have accomplished our goal: The aggregation of the log is no longer the concern of the individual functions. They produce their own messages, which are then, externally, concatenated into a larger log. Now imagine a whole program written in this style. Itโ€™s a nightmare of repetitive, error-prone code.

The Writer Category

The idea of embellishing the return types of a bunch of functions in order to piggyback some additional functionality turns out to be very fruitful. Weโ€™ll see many more examples of it. The starting point is our regular category of types and functions. Weโ€™ll leave the types as objects, but redefine our morphisms to be the embellished functions.

Writer in Haskell

The result is a lambda function of one argument x. The lambda is written as a backslash โ€” think of it as the Greek letter ฮป with an amputated leg.

Challenge

For our limited purposes, a Kleisli category has, as objects, the types of the underlying programming language. Morphisms from type ๐ด to type ๐ต are functions that go from ๐ด to a type derived from ๐ต using the particular embellishment.

Products and Coproducts

Ancient Greek playwright Euripides once said: โ€œEvery man is like the company he is wont to keep.โ€ We are defined by our relationships. Nowhere is this more true than in category theory.

Initial Object

The initial object is the object that has one and only one morphism going to any object in the category.

However, even that doesnโ€™t guarantee the uniqueness of the initial object (if one exists). But it guarantees the next best thing: uniqueness up to isomorphism.

Terminal Object

The terminal object is the object with one and only one morphism coming to it from any object in the category.

Duality

It turns out that for any category ๐‚ we can define the opposite category ๐‚ ๐‘œ๐‘ just by reversing all the arrows. The opposite category automatically satisfies all the requirements of a category, as long as we simultaneously redefine composition.

Isomorphisms

The constructions in the opposite category are often prefixed with โ€œcoโ€, so you have products and coproducts, monads and comonads, cones and cocones, limits and colimits, and so on. There are no cocomonads though, because reversing the arrows twice gets us back to the original state.

An isomorphism is an invertible morphism; or a pair of morphisms, one being the inverse of the other.

Products

The composition ๐‘” โˆ˜ ๐‘“ must be a morphism from ๐‘–1 to ๐‘–1 . But ๐‘–1 is initial so there can only be one morphism going from ๐‘–1 to ๐‘–1 . Since we are in a category, we know that there is an identity morphism from ๐‘–1 to ๐‘–1 , and since there is room for only one, that must be it. Therefore ๐‘” โˆ˜ ๐‘“ is equal to identity. Similarly, ๐‘“ โˆ˜๐‘” must be equal to identity, because there can be only one morphism from ๐‘–2 back to ๐‘–2 . This proves that ๐‘“ and ๐‘” must be the inverse of each other. Therefore any two initial objects are isomorphic.

Another way of looking at these equations is that ๐‘š factorizes ๐‘ โ€ฒ and ๐‘ž โ€ฒ . Just pretend that these equations are in natural numbers, and the dot is multiplication: ๐‘š is a common factor shared by ๐‘ โ€ฒ and ๐‘ž โ€ฒ

The second example is different: we retain enough information after running either p or q, but there is more than one way to factorize fst and snd. Because both p and q ignore the second component of the triple, our m’ can put anything in it. We can have: m’ (x, b) = (x, x, b) or m’ (x, b) = (x, 42, b) and so on.

Coproduct

A product of two objects ๐‘Ž and ๐‘ is the object ๐‘ equipped with two projections such that for any other object ๐‘ โ€ฒ equipped with two projections there is a unique morphism ๐‘š from ๐‘ โ€ฒ to ๐‘ that factorizes those projections

A coproduct of two objects ๐‘Ž and ๐‘ is the object ๐‘ equipped with two injections such that for any other object ๐‘ โ€ฒ equipped with two injections there is a unique morphism ๐‘š from ๐‘ to ๐‘ โ€ฒ that factorizes those injections.

Asymmetry

Weโ€™ll see later that product behaves like multiplication, with the terminal object playing the role of one; whereas coproduct behaves more like the sum, with the initial object playing the role of zero.

Product Types

For instance, if you know how to compare values of basic types for equality, and you know how to generalize these comparisons to product and coproduct types, you can automate the derivation of equality operators for composite types. In Haskell you can automatically derive equality, comparison, conversion to and from string, and more, for a large subset of composite types.

Pairs are not strictly commutative: a pair (Int, Bool) cannot be substituted for a pair (Bool, Int), even though they carry the same information. They are, however, commutative up to isomorphism โ€” the isomorphism being given by the swap function (which is its own inverse): swap :: (a, b) -> (b, a) swap (x, y) = (y, x) You can think of the two pairs as simply using a different format for storing the same data. Itโ€™s just like big endian vs. little endian.

You can interpret the creation of a product type as a binary operation on types. From that perspective, the above isomorphism looks very much like the associativity law weโ€™ve seen in monoids: (๐‘Ž โˆ— ๐‘) โˆ— ๐‘ = ๐‘Ž โˆ— (๐‘ โˆ— ๐‘)

data Pair a b = P a b Here, Pair a b is the name of the type parameterized by two other types, a and b; and P is the name of the data constructor. You define a pair type by passing two types to the Pair type constructor.

Sum Types

Just as the product in the category of sets gives rise to product types, the coproduct gives rise to sum types.

In terms of types, we have Either as the monoidal operator and Void, the uninhabited type, as its neutral element. You can think of Either as plus, and Void as zero. Indeed, adding Void to a sum type doesnโ€™t change its content. For instance: Either a Void is isomorphic to a. Thatโ€™s because there is no way to construct a Right version of this type โ€” there isnโ€™t a value of type Void.

This kind of optionality, if deliberate, is expressed in Haskell using the Maybe type: data Maybe a = Nothing | Just a The Maybe type is a sum of two types. You can see this if you separate the two constructors into individual types. The first one would look like this: data NothingType = Nothing Itโ€™s an enumeration with one value called Nothing. In other words, itโ€™s a singleton, which is equivalent to the unit type (). The second part: data JustType a = Just a is just an encapsulation of the type a.

data Maybe a = Either () a

object that was created as Just “energy” will never turn into Nothing. Similarly, an empty list will forever be empty, and a list of three elements will always have the same three elements. Itโ€™s this immutability that makes construction reversible.

Algebra of Types

Taken separately, product and sum types can be used to define a variety of useful data structures, but the real strength comes from combining the two. Once again we are invoking the power of composition.

Does it also hold for product and sum types? Yes, it does โ€” up to isomorphisms, as usual.

Mathematicians have a name for two such intertwined monoids: itโ€™s called a semiring. Itโ€™s not a full ring, because we canโ€™t define subtraction of types. Thatโ€™s why a semiring is sometimes called a rig, which is a pun on โ€œring without an nโ€ (negative). But barring that, we can get a lot of mileage from translating statements about, say, natural numbers, which form a rig, to statements about types.

The list type is quite interesting, because itโ€™s defined as a solution to an equation. The type we are defining appears on both sides of the equation: data List a = Nil | Cons a (List a) If we do our usual substitutions, and also replace List a with x, we get the equation: x = 1 + a * x We canโ€™t solve it using traditional algebraic methods because we canโ€™t subtract or divide types. But we can try a series of substitutions, where we keep replacing x on the right hand side with (1 + a*x), and use the distributive property. This leads to the following series: x = 1 + a*x x = 1 + a*(1 + a*x) = 1 + a + a*a*x x = 1 + a + a*a*(1 + a*x) = 1 + a + a*a + a*a*a*x … x = 1 + a + a*a + a*a*a + a*a*a*a… We end up with an infinite sum of products (tuples), which can be interpreted as: A list is either empty, 1; or a singleton, a; or a pair, a*a; or a triple, a*a*a; etcโ€ฆ Well, thatโ€™s exactly what a list is โ€” a string of as!

Challenges

Logical and and or also form a semiring, and it too can be mapped into type theory:

Functors

A functor is a mapping between categories.

thereโ€™s something more to the structure of a category: thereโ€™s also the composition of morphisms. If โ„Ž is a composition of ๐‘“ and ๐‘”: โ„Ž = ๐‘”.๐‘“ we want its image under ๐น to be a composition of the images of ๐‘“ and ๐‘”: ๐นโ„Ž = ๐น๐‘” . ๐น ๐‘“

It may smash objects together, it may glue multiple morphisms into one, but it may never break things apart. This no-tearing constraint is similar to the continuity condition you might know from calculus.

The Maybe Functor

We can talk about functors that map this category into itself โ€” such functors are called endofunctors. So whatโ€™s an endofunctor in the category of types? First of all, it maps types to types.

In Haskell, we implement the morphism-mapping part of a functor as a higher order function called fmap. In the case of Maybe, it has the following signature: fmap :: (a -> b) -> (Maybe a -> Maybe b)

Equational Reasoning

equational reasoning, which is a common proof technique in Haskell. It takes advantage of the fact that Haskell functions are defined as equalities: the left hand side equals the right hand side. You can always substitute one for another, possibly renaming variables to avoid name conflicts.

Optional

Letโ€™s consider the C++ analog of Maybe, the template type optional.

So how does Haskell deal with abstracting the functor? It uses the typeclass mechanism. A typeclass defines a family of types that support a common interface.

Typeclasses

Typeclasses are also Haskellโ€™s only mechanism for overloading functions (and operators)

The List Functor

We have the type constructor List, which is a mapping from any type a to the type List a. To show that List is a functor we have to define the lifting of functions: Given a function a -> b define a function List a -> List b: fmap :: (a -> b) -> (List a -> List b)

Notice that, on the right hand side, fmap f is applied to a list thatโ€™s shorter than the list for which we are defining it โ€” itโ€™s applied to its tail. We recurse towards shorter and shorter lists, so we are bound to eventually reach the empty list, or Nil.

The Reader Functor

Most C++ containers are functors by virtue of implementing iterators that can be passed to std::transform, which is the more primitive cousin of fmap. Unfortunately, the simplicity of a functor is lost under the usual clutter of iterators and temporaries

fmap f g = (.) f g and the arguments can be omitted to yield a direct equality of two functions:

Functors as Containers

This combination of the type constructor (->) r with the above implementation of fmap is called the reader functor.

So I like to think of the functor object (an object of the type generated by an endofunctor) as containing a value or values of the type over which it is parameterized, even if these values are not physically present there.

Despite its weirdness, the Const functor plays an important role in many constructions. In category theory, itโ€™s a special case of the ฮ”๐‘ functor I mentioned earlier โ€” the endo-functor case of a black hole.

Functor Composition

In particular, itโ€™s easy to compose endofunctors.

And there is also a trivial identity functor in every category: it maps every object to itself, and every morphism to itself. So functors have all the same properties as morphisms in some category.

functoriality means that a bifunctor has to map morphisms as well. This time, though, it must map a pair of morphisms, one from ๐‚ and one from ๐ƒ, to a morphism in ๐„.

When declaring an instance of Bifunctor, you have a choice of either implementing bimap and accepting the defaults for first and second, or implementing both first and second and accepting the default for bimap (of course, you may implement all three of them, but then itโ€™s up to you to make sure they are related to each other in this manner).

By duality, a coproduct, if itโ€™s defined for every pair of objects in a category, is also a bifunctor. In Haskell, this is exemplified by the Either type constructor being an instance of Bifunctor:

So what are the building blocks of parameterized algebraic data types? First, there are the items that have no dependency on the type parameter of the functor, like Nothing in Maybe, or Nil in List. They are equivalent to the Const functor. Remember, the Const functor ignores its type parameter (really, the second type parameter, which is the one of interest to us, the first one being kept constant).

Itโ€™s a sum of two types, and we now know that the sum is functorial. The first part, Nothing can be represented as a Const () acting on a (the first type parameter of Const is set to unit โ€” later weโ€™ll see more interesting uses of Const). The second part is just a different name for the identity functor. We could have defined Maybe, up to isomorphism, as:

Functorial Algebraic Data Types

newtype BiComp bf fu gu a b = BiComp (bf (fu a) (gu b))

So it turns out that we didnโ€™t have to prove that Maybe was a functor โ€” this fact followed from the way it was constructed as a sum of two functorial primitives.

data Maybe a = Nothing | Just a deriving Functor and the corresponding fmap will be implemented for you.

Functors in C++

Virtual functions cannot be templatized in C++. Weโ€™ll implement fmap as a generic free function, and weโ€™ll replace pattern matching with dynamic_cast.

The Writer Functor

I said that the embellishment was somehow related to endofunctors. And, indeed, the Writer type constructor is functorial in a. We donโ€™t even have to implement fmap for it, because itโ€™s just a simple product type.

Covariant and Contravariant Functors

of acting with f on the lambdaโ€™s argument.

Letโ€™s try to make it functorial in the first argument. Weโ€™ll start with a type synonym โ€” itโ€™s just like the Reader but with the arguments flipped: type Op r a = a -> r

ch a functor maps a morphism ๐‘“ ๐‘œ๐‘ โˆท ๐‘Ž โ†’ ๐‘ in ๐‚ ๐‘œ๐‘ to the morphism ๐น ๐‘“ ๐‘œ๐‘ โˆท ๐น ๐‘Ž โ†’ ๐น ๐‘ in ๐ƒ. But the morphism ๐‘“ ๐‘œ๐‘ secretly corresponds to some morphism ๐‘“ โˆท ๐‘ โ†’ ๐‘Ž in the original category ๐‚.

class Contravariant f where contramap :: (b -> a) -> (f a -> f b)

Profunctors

contramap = flip (.)

The Hom-Functor

The above examples are the reflection of a more general statement that the mapping that takes a pair of objects ๐‘Ž and ๐‘ and assigns to it the set of morphisms between them, the hom-set ๐‚(๐‘Ž, ๐‘), is a functor.

Challenges

A morphism in ๐‚ ๐‘œ๐‘ ร— ๐‚ is a pair of morphisms from ๐‚: ๐‘“ โˆท ๐‘Žโ€ฒ โ†’ ๐‘Ž ๐‘” โˆท ๐‘ โ†’ ๐‘โ€ฒ The lifting of this pair must be a morphism (a function) from the set ๐‚(๐‘Ž, ๐‘) to the set ๐‚(๐‘Ž โ€ฒ , ๐‘โ€ฒ ). Just pick any element โ„Ž of ๐‚(๐‘Ž, ๐‘) (itโ€™s a morphism from ๐‘Ž to ๐‘) and assign to it: ๐‘” โˆ˜ โ„Ž โˆ˜ ๐‘“ which is an element of ๐‚(๐‘Ž โ€ฒ , ๐‘โ€ฒ ). As you can see, the hom-functor is a special case of a profunctor.

Function Types

It just so happens that in the category ๐’๐ž๐ญ every hom-set is itself an object in the same category โ€”because it is, after all, a set.

Hom-set in Set is just a set

Universal Construction

A function type may be considered a composite type because of its relationship to the argument type and the result type.

But instead of dealing with individual pairs (๐‘“ , ๐‘ฅ), we can as well talk about the whole product of the function type ๐‘ง and the argument type ๐‘Ž. The product ๐‘ง ร— ๐‘Ž is an object, and we can pick, as our application morphism, an arrow ๐‘” from that object to ๐‘. In ๐’๐ž๐ญ, ๐‘” would be the function that maps every pair (๐‘“ , ๐‘ฅ) to ๐‘“ ๐‘ฅ.

which there is no product, or there isnโ€™t a product for all pairs of objects. The answer is no: there is no function type, if there is no product type.

What we really need, given the mapping โ„Ž from ๐‘ง โ€ฒ to ๐‘ง, is a mapping from ๐‘ง โ€ฒ ร— ๐‘Ž to ๐‘ง ร— ๐‘Ž. And now, after discussing the functoriality of the product, we know how to do it. Because the product itself is a functor (more precisely an endo-bi-functor), itโ€™s possible to lift pairs of morphisms.

Of course, there is no guarantee that such an object ๐‘Ž โ‡’ ๐‘ exists for any pair of objects ๐‘Ž and ๐‘ in a given category. But it always does in ๐’๐ž๐ญ. Moreover, in ๐’๐ž๐ญ, this object is isomorphic to the hom-set ๐’๐ž๐ญ(๐‘Ž, ๐‘).

Currying

letโ€™s think of the morphism ๐‘” as a function of two variables, ๐‘ง and ๐‘Ž. ๐‘” โˆท ๐‘ง ร— ๐‘Ž โ†’ ๐‘

a -> (b -> c)

curry :: ((a, b) -> c) -> (a -> b -> c) curry f a b = f (a, b)

Exponentials

In mathematical literature, the function object, or the internal homobject between two objects ๐‘Ž and ๐‘, is often called the exponential and denoted by ๐‘ ๐‘Ž . Notice that the argument type is in the exponent.

For instance a (pure) function from Bool is completely specified by a pair of values: one corresponding to False, and one corresponding to True. The set of all possible functions from Bool to, say, Int is the set of all pairs of Ints. This is the same as the product Int ร— Int or, being a little creative with notation, Int2 .

Cartesian Closed Categories

But Haskell is a lazy language, so the boundary between lazily evaluated (infinite) data structures and functions is fuzzy. This function vs. data duality explains the identification of Haskellโ€™s function type with the categorical exponential object โ€” which corresponds more to our idea of data.

Zeroth Power

in which product can be distributed over coproduct ๐‘Ž ร— (๐‘ + ๐‘) = ๐‘Ž ร— ๐‘ + ๐‘Ž ร— ๐‘ (๐‘ + ๐‘) ร— ๐‘Ž = ๐‘ ร— ๐‘Ž + ๐‘ ร— ๐‘Ž is called a bicartesian closed category.

First Power

In Haskell, we replace 0 with Void; 1 with the unit type (); and the exponential with function type.

Exponentials of Sums

This is a restatement of the observation that morphisms from the terminal object can be used to pick โ€œelementsโ€ of the object a. The set of such morphisms is isomorphic to the object itself. In ๐’๐ž๐ญ, and in Haskell, the isomorphism is between elements of the set a and functions that pick those elements, () -> a.

Curry-Howard Isomorphism

Exponentials of Exponentials

๐‘’๐‘ฃ๐‘Ž๐‘™ โˆท (๐‘Ž โ‡’ ๐‘) ร— ๐‘Ž โ†’ ๐‘ which defines the function type ๐‘Ž โ‡’ ๐‘ (or the exponential object ๐‘ ๐‘Ž ). Letโ€™s translate this signature to a logical predicate using the CurryHoward isomorphism: ((๐‘Ž โ‡’ ๐‘) โˆง ๐‘Ž) โ‡’ ๐‘ Hereโ€™s how you can read this statement: If itโ€™s true that ๐‘ follows from ๐‘Ž, and ๐‘Ž is true, then ๐‘ must be true. This makes perfect intuitive sense and has been known since antiquity as modus ponens.

absurd :: Void -> a Considering that Void translates into false, we get: ๐‘“ ๐‘Ž๐‘™๐‘ ๐‘’ โ‡’ ๐‘Ž Anything follows from falsehood (ex falso quodlibet)

Bibliography

Computers are not only helping mathematicians do their work โ€” they are revolutionizing the very foundations of mathematics. The latest hot research topic in that area is called Homotopy Type Theory, and is an outgrowth of type theory.

Natural Transformations

A functor โ€œembedsโ€ one category in another. It may collapse multiple things into one, but it never breaks connections. One way of thinking about it is that with a functor we are modeling one category inside another. The source category serves as a model, a blueprint, for some structure thatโ€™s part of the target category.

Natural transformations help us compare these realizations. They are mappings of functors โ€” special mappings that preserve their functorial nature.

We donโ€™t want to make artificial connections between objects. So itโ€™s natural to use existing connections, namely morphisms. A natural transformation is a selection of morphisms: for every object ๐‘Ž, it picks one morphism from ๐น ๐‘Ž to ๐บ๐‘Ž. If we call the natural transformation ๐›ผ, this morphism is called the component of ๐›ผ at ๐‘Ž, or ๐›ผ๐‘Ž . ๐›ผ๐‘Ž โˆท ๐น ๐‘Ž โ†’ ๐บ๐‘Ž Keep in mind that ๐‘Ž is an object in ๐‚ while ๐›ผ๐‘Ž is a morphism in ๐ƒ.

Now we have two ways of getting from ๐น ๐‘Ž to ๐บ๐‘. To make sure that they are equal, we must impose the naturality condition that holds for any ๐‘“ : ๐บ๐‘“ โˆ˜ ๐›ผ๐‘Ž = ๐›ผ๐‘ โˆ˜ ๐น ๐‘“

Polymorphic Functions

Looking at a natural transformation component-wise, one may say that it maps objects to morphisms. Because of the naturality condition, one may also say that it maps morphisms to commuting squares โ€” there is one commuting naturality square in ๐ƒ for every morphism in ๐‚.

A natural transformation is a polymorphic function that is defined for all types a: alpha :: forall a . F a -> G a The forall a is optional in Haskell (and in fact requires turning on the language extension ExplicitForAll)

In Haskell, a polymorphic function must be defined uniformly for all types. One formula must work across all types. This is called parametric polymorphism.

fmapG f . alphaa = alphab . fmapF f Because of type inference, these annotations are not necessary, and the following equation holds: fmap f . alpha = alpha . fmap f

the new container, with its own implementation of fmap. These two actions, repackaging and fmapping, are orthogonal. โ€œOne moves the eggs, the other boils them.โ€

instance Functor (Reader e) where fmap f (Reader g) = Reader (\x -> f (g x)) For every type e, you can define a family of natural transformations from Reader e to any other functor f. Weโ€™ll see later that the members of this family are always in one to one correspondence with the elements of f e (the Yoneda lemma)

Beyond Naturality

Since all standard algebraic data types are functors, any polymorphic function between such types is a natural transformation.

Polymorphic functions between two contravariant functors are still natural transformations in the categorical sense, except that they work on functors from the opposite category to Haskell types.

Functor Category

Therefore a function of the signature: (a -> a) -> f a where f is an arbitrary functor, cannot be a natural transformation.

ne (long) look at a diagram convinces us that the result of this composition is indeed a natural transformation from F to H: ๐ป ๐‘“ โˆ˜ (๐›ฝ โ‹… ๐›ผ)๐‘Ž = (๐›ฝ โ‹… ๐›ผ)๐‘ โˆ˜ ๐น ๐‘“

word about notation. Following Saunders Mac Lane I use the dot for the kind of natural transformation composition I have just described. The problem is that there are two ways of composing natural transformations. This one is called the vertical composition, because the functors are usually stacked up vertically in the diagrams that describe it. Vertical composition is important in defining the functor category.

The functor category between categories ๐‚ and ๐ƒ is written as ๐…๐ฎ๐ง(๐‚, ๐ƒ), or [๐‚, ๐ƒ], or sometimes as ๐ƒ ๐‚.

2-Categories

๐‚๐š๐ญ is a full-blown Cartesian closed category in which there is an exponential object ๐ƒ ๐‚ for any pair of categories. And by โ€œobjectโ€ in ๐‚๐š๐ญ I mean a category, so ๐ƒ ๐‚ is a category, which we can identify with the functor category between ๐‚ and ๐ƒ

Our goal is to find a morphism that goes from ๐บ(๐น ๐‘Ž) to ๐บ โ€ฒ (๐น โ€ฒ ๐‘Ž), a candidate for the component of a natural transformation connecting the two functors ๐บ โˆ˜ ๐น and ๐บ โ€ฒ โˆ˜ ๐น โ€ฒ . In fact thereโ€™s not one but two paths we can take from ๐บ(๐น ๐‘Ž) to ๐บ โ€ฒ (๐น โ€ฒ ๐‘Ž): ๐บ โ€ฒ ๐›ผ๐‘Ž โˆ˜ ๐›ฝ๐น ๐‘Ž ๐›ฝ๐น โ€ฒ๐‘Ž โˆ˜ ๐บ๐›ผ๐‘Ž Luckily for us, they are equal, because the square we have formed turns out to be the naturality square for ๐›ฝ

Hereโ€™s a categorical rule of thumb: Every time you have composition, you should look for a category. We have vertical composition of natural transformations, and itโ€™s part of the functor category. But what about the horizontal composition? What category does that live in?

Conclusion

In this new sideways interpretation of ๐‚๐š๐ญ there are two ways of getting from object to object: using a functor or using a natural transformation.

Challenges

A functor maps objects to objects, so we can use it as a type constructor, or a parametric type. A functor also maps morphisms, so it is a higher order function โ€” fmap. There are some simple functors, like Const, product, and coproduct, that can be used to generate a large variety of algebraic data types. Function types are also functorial, both covariant and contravariant, and can be used to extend algebraic data types.

Declarative Programming

There are, roughly speaking, two ways of doing it: by telling the computer what to do, or by telling it how to do it. One is called declarative and the other imperative.

h x = let y = f x in g y

Notice how this approach resembles imperative thinking: we reach the final solution by following a sequence of small steps, each depending on the result of the previous one. In fact, computer simulations of physical systems are routinely implemented by turning differential equations into difference equations and iterating them.

The other approach is global. We look at the initial and the final state of the system, and calculate a trajectory that connects them by minimizing a certain functional.

Feynmanโ€™s greatest contribution was to realize that the principle of least action can be generalized to quantum mechanics. There, again, the problem is formulated in terms of initial state and final state. The Feynman path integral between those states is used to calculate the probability of transition.

global picture, where we declare the initial and final conditions, and everything in between just follows. The global approach can be also used in programming, for instance when implementing ray tracing.

If you can get from ๐ด to ๐ต through a series of steps, you can also get there in one leap. Moreover, the major tool of category theory is the universal construction, which is the epitome of a global approach. Weโ€™

I would go as far as to argue that category theory is the kind of math that is particularly well suited for the minds of programmers. Thatโ€™s because category theory โ€” rather than dealing with particulars โ€” deals with structure. It deals with the kind of structure that makes programs composable.

Functional programming is not only about composing functions and algebraic data structures โ€” it makes concurrency composable โ€” something thatโ€™s virtually impossible with other programming paradigms.

Mathematicians laughed at the Dirac delta function, which was made up on the spot by the great physicist P. A. M. Dirac to solve some differential equations. They stopped laughing when they discovered a completely new branch of calculus called distribution theory that formalized Diracโ€™s insights.

One of the forces that are driving the big change is the multicore revolution. The prevailing programming paradigm, object oriented programming, doesnโ€™t buy you anything in the realm of concurrency and parallelism, and instead encourages dangerous and buggy design.

Data hiding, the basic premise of object orientation, when combined with sharing and mutation, becomes a recipe for data races.

The idea of combining a mutex with the data it protects is nice but, unfortunately, locks donโ€™t compose, and lock hiding makes deadlocks more likely and harder to debug.

But even in the absence of concurrency, the growing complexity of software systems is testing the limits of scalability of the imperative paradigm.

To put it simply, side effects are getting out of hand.

Itโ€™s only when we start composing functions that have side effects on top of other functions that have side effects, and so on, that things start getting hairy. Itโ€™s not that side effects are inherently bad โ€” itโ€™s the fact that they are hidden from view that makes them impossible to manage at larger scales. Side effects donโ€™t scale, and imperative programming is all about side effects.

I hope future generations will be as admiring of the programming skills weโ€™ve been displaying in building complex operating systems, web servers, and the internet infrastructure. And, frankly, they should, because weโ€™ve done all this based on very flimsy theoretical foundations. We have to fix those foundations if we want to move forward.

This process of hierarchical decomposition and recomposition is not imposed on us by computers. It reflects the limitations of the human mind.

So what are the right chunks for the composition of programs? Their surface area has to increase slower than their volume. (I like this analogy because of the intuition that the surface area of a geometric object grows with the square of its size โ€” slower than the volume, which grows with the cube of its size.) The surface area is the information we need in order to compose chunks. The volume is the information we need in order to implement them.

The idea is that, once a chunk is implemented, we can forget about the details of its implementation and concentrate on how it interacts with other chunks. In object-oriented programming, the surface is the class declaration of the object, or its abstract interface. In functional programming, itโ€™s the declaration of a function.

The moment you have to dig into the implementation of the object in order to understand how to compose it with other objects, youโ€™ve lost the advantages of your programming paradigm.

the essence of a category is composition. Or, if you prefer, the essence of composition is a category. Arrows compose, so if you have an arrow from object A to object B, and another arrow from object B to object C, then there must be an arrow โ€” their composition โ€” that goes from A to C.

Arrows as Functions

Think of arrows, which are also called morphisms, as functions.

You have a function f that takes an argument of type A and returns a B. You have another function g that takes a B and returns a C. You can compose them by passing the result of f to g.

You have just defined a new function that takes an A and returns a C.

In math, such composition is denoted by a small circle between functions: gโˆ˜f. Notice the right to left order of composition. For some people this is confusing. You may be familiar with the pipe notation in Unix, as in: lsof | grep Chrome

But in mathematics and in Haskell functions compose right to left. It helps if you read gโˆ˜f as โ€œg after f.โ€

you see right-to-left composition: g(f(a)); this time in C.

So letโ€™s try some Haskell for a change. Hereโ€™s the declaration of a function from A to B: f :: A -> B Similarly: g :: B -> C Their composition is: g . f Once you see how simple things are in Haskell, the inability to express straightforward functional concepts in C++ is a little embarrassing. In fact, Haskell will let you use Unicode characters so you can write composition as: g โˆ˜ f You can even use Unicode double colons and arrows: f โˆท A โ†’ B

So hereโ€™s the first Haskell lesson: Double colon means โ€œhas the type ofโ€ฆโ€ A function type is created by inserting an arrow between two types. You compose two functions by inserting a period between them (or a Unicode circle).

Properties of Composition

two extremely important properties that the composition in any category must satisfy

Composition is associative. If you have three morphisms, f, g, and h, that can be composed (that is, their objects match end-to-end), you donโ€™t need parentheses to compose them. In math notation this is expressed as: hโˆ˜(gโˆ˜f) = (hโˆ˜g)โˆ˜f = hโˆ˜gโˆ˜f In (pseudo) Haskell: f :: A -> B g :: B -> C h :: C -> D h . (g . f) = (h . g) . f = h . g . f (I said โ€œpseudo,โ€ because equality is not defined for functions.) Associativity is pretty obvious when dealing with functions, but it may be not as obvious in other categories.

For every object A there is an arrow which is a unit of composition. This arrow loops from the object to itself. Being a unit of composition means that, when composed with any arrow that either starts at A or ends at A, respectively, it gives back the same arrow. The unit arrow for object A is called idA (identity on A). In math notation, if f goes from A to B then fโˆ˜idA = f and idBโˆ˜f = f

When dealing with functions, the identity arrow is implemented as the identity function that just returns back its argument.

In Haskell, the identity function is part of the standard library (called Prelude). Hereโ€™s its declaration and definition: id :: a -> a id x = x As you can see, polymorphic functions in Haskell are a piece of cake.

Hereโ€™s the trick: names of concrete types always start with a capital letter, names of type variables start with a lowercase letter. So here a stands for all types.

Function definition and function call are the bread and butter of functional programming so their syntax is reduced to the bare minimum. Not only are there no parentheses around the argument list but there are no commas between arguments (youโ€™ll see that later, when we define functions of multiple arguments

The body of a function is always an expression โ€” there are no statements in functions. The result of a function is this expression โ€” here, just x.

You might be asking yourself the question: Why would anyone bother with the identity function โ€” a function that does nothing? Then again, why do we bother with the number zero? Zero is a symbol for nothing

To summarize: A category consists of objects and arrows (morphisms). Arrows can be composed, and the composition is associative. Every object has an identity arrow that serves as a unit under composition.