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.