Preface

This is a collection notes on Category Theory for personal reference.

Index

Glossary

Quick Definitions

Category Theory for Programmers

• 1 | Category: The Essence of Composition

• 2 | Types and Functions

• 3 | Categories, Great and Small

• 4 | Kleisli Categories

• 5 | Products and Coproducts

• 6 | Simple Algebraic Data Types

• 7 | Functors

• 8 | Functoriality

• 9| Function Types

• 10 | Natural Transformation

• 11 | Declarative Programming

• 12 | Limits and Colimits

Glossary

Quick Definitions

• A Category $\mathbf{C}$ consists of
  • A class $ob(\mathbf{C})$ called the class of object of $\mathbf{C}$
    • A class is a collection of things which would yield a paradox if we called it a set
  • For all $A, B \in \mathbf{C}$, a class $\mathbf{C}(A,B)$ called the hom-set of morphisms (or maps, arrows) from $A$ to $B$
    • The homset is literally the collection of morphisms
  • For all $A, B, C \in ob(\mathbf{C})$, a function $\circ: \mathbf{C}(B, C) \times \mathbf{C}(A,B) \rarr \mathbf{C}(A,C)$, such that $(g,f) \mapsto g \circ f$ called composition
  • For all $A \in ob(\mathbf{C})$, a morphism $\mathbf{id}_A \in \mathbf{C}(A,A)$ called the identity on $A$
  • Where composition is subject to the following conditions for all $A, B, C,D \in ob(\mathbf{C})$:
    • For all morphisms $f \in \mathbf{C}(A,B), g \in \mathbf{C}(B,C)$, and $h \in \mathbf{C}(C,D)$, we have associativity: $\\(h \circ g) \circ f = h \circ (g \circ f)$
    • For all morphisms $f \in \mathbf{C}(A,B)$, we have $f \circ \mathbf{id}_A = f = \mathbf{id}_B \circ f$
• A Functor between categories $\mathbf{C, D}$ consists of $F : \mathbf{C} \rarr \mathbf{D}$ where
  • A function $ob(\mathbf{C}) \rarr ob(\mathbf{D}$, such that $F \mapsto F(A)$
  • For all $A, B, C \in \mathbf{C}$, a function $\mathbf{C}(A,B) \rarr \mathbf{D}(F(A), F(B))$ such that $f \mapsto F(f)$
  • The function on morphisms is subject to the following conditions $\forall A,B,C \in \mathbf{C}$:
    • If $f \in \mathbf{C}(A,B)$ and $g \in \mathbf{C}(B,C)$, then $F(g \circ f) = F(g) \circ F(f)$. That is, $F$ preserves compositions
    • Similarly, $F(\mathbf{id}_A) = \mathbf{id}_{F(A)}$, so $F$ preserves identities as well
  • Functors take objects to objects and morphisms to morphisms subject to sensible composition laws
    • Forgetful functors take objects to a superclass of themselves by dropping some properties of the initial subclass

Classes of sameness

Category Theory for Programmers

1 | Category: The Essence of Composition

• A category consists of objects and arrows that go between them
• The essence of a composition is a category, and vice versa (the essence of a category is composition)

TODO illustration

1.1 Arrows as Functions

• Arrows are morphisms, which, for the time being, can be thought of as functions (functions are a subset of morphisms).

• If we have two functions $f: A \rarr B$ and $g: B \rarr C$, then we can compose them to have a function $h: A \rarr C$ given by $h = g \circ f$ where $\circ := |$, unix pipe operator, and can be read as "$g$ of $f$" or "$g$ after $f$."

1.2 Properties of Composition

1. Composition is associative: it can be expressed without parentheses

2. For every object $A$, there exists and arrow which is a unit of composition. This arrow goes from the object back into itself. "Unit of composition" means that, when composed with any arrow that either starts or ends at $A$, it will give back the same arrow. The unit for $A$ is the identity operation on $A$ given by $\mathbf{id}_A$, which is useful for higher order functions and establishing other properties of categories. Given a function $f: A \rarr B$,

1.3 Composition is the Essence of Programming

• Programming naturally follows the technique of de-composing a large problem into smaller, digestible problems for efficient solutions.

2 | Types and Function

2.1 Who needs Types?

• Higher level languages' compilers protect from lexical and grammatical errors that might arise from arbitrary sequences of machine code
  • Type checking is one mechanism to prevent non-sense programs
  • Dynamically-typed languages resolve mismatches at runtime
  • Statically-typed languages resolve mismatches at compile time

2.2 Types Are About Composability

• Category Theory is about composing arrows, but not just any combination of arrows, typically they have to compose between arrows of similar type
  • Target object must be the same as the source of the next arrow

2.3 What are Types?

• Intuitively, we can think of types as sets of values e.g.,

• Types can be finite, like the set of allowable characters in a programming language:

• Types can be infinite:

• Set is itself a category where objects are sets, and morphisms or arrows are functions

• A conflict which arises between the mathematical and programming understandings of the term "functions"

  • A mathematical function is and answer
  • A programming function is a sequence of executable steps to compute an answer. This is fine as long as there are finite steps, but recursive functions may never terminate
    • Well-defined recursive definitions are fine, but determining whether a recursive functioning terminates is undecidable and has several neat implications.

• Programming languages circumvent this by having all types extend a special value known as the bottom: $\perp$ which means non-terminating computation

For example, take the following Haskell function:

f :: Bool -> Bool

It might return True, False, or bottom. It's convenient to treat every runtime error as a bottom:

f x = undefined

which is acceptable to the type checker since undefined evaluates to bottom which is a member of any type including Bool.

• Functions that may return bottom are called partial, as opposed to total which returns valid values for all input arguments.

Because of this definition, the category of Haskell types and functions used above are called Hask, rather than Set. There's a theoretical distinction, but pragmatically speaking, they're equivalent

2.4 Why Do We Need a Mathematical Model?

• It's hard to nail down precise semantic standards for programming languages

• Operational Semantics represent a formal tool of describing behavior, but it's complex and academic

  • Relies on / defines an idealized program interpreter
  • It's rather difficult to prove program behavior this way since you have to run a program through your idealized interpreter to document a property which is only a minor improvement over how humans do it in our heads. And we all know how great we are at writing sound programs!

• Semantics of industrial languages are usually described with informal operational reasoning in terms of an "abstract machine"

• Denotational Semantics - a formalization under which every programming construct is given a mathematical interpretation. Languages which lend themselves to denotational semantics are "good" and those that don't are "bad" (I'm heavily paraphrasing here lol):

Consider the following programs

factorial n = product[1..n]

int factorial(int n) {
  int i;
  int res = 1;
  for (i = 2; i <= n; ++i)
    res *= i;
  return res;
}

This is something of a cheap shot since we could just as easily ask for a mathematical model of reading characters from stdin, or sending a packet across the wire, or any other program which doesn't intuitively lend itself to notation like that of computing the factorial of a number. GG Haskell.

The solution: Category Theory. Eugenio Moggi found that computational effect can be mapped to Monads which helps ?

2.5 Pure and Dirty Function

• Recall that a mathematical function is just a mapping of values. Mathematical functions can easily be implemented as programming functions e.g. we can expect that a square function will produce the same output every time, regardless of outside factors

  • Squaring a number should not have the side effect of dispensing a dog treat, else it cannot be easily modeled as a mathematical function

• A Pure Function always produces the same output when given the same input

  • All functions in Haskell are pure, which contributes to why it's easier to describe the language's behavior with denotational semantics

• A Dirty Function is one which produces side effects like dog treats by creating or relying upon external, (global) state

2.6 Examples of Types

2.6.1 Empty

• Is there a type that corresponds to the empty set?
• Not the C/C++ void, but yes the Haskell Void since it's a type that is not inhabited by any values, which nicely corresponds to the mathematical notion of $\empty$.
• Thus, you can define a function which accepts Void as an argument, but you can never invoke it since, by definition, no values satisfy the argument signature!
• This function can happily return any type since it will never be called

absurd :: Void -> a

• Void represents falsity, absurd corresponds to the statement that from falsity follows anything

Ex falso sequitur quodlibet.

2.6.2 Singleton

• This is the C/C++ void construct, holding only 1 possible value
• A function from void can always be called, and if it is pure, it will always return the same result

int f42() { return 42; }

• The above example isn't quite taking "nothing" as the argument since "nothing" is Haskell's Void, but since there's only one instance of void in C/C++, it's implied in the function signature

• Haskell's singleton is () –the "unit"– which coincidentally results in a very similar signature:

f44 :: () -> Integer
f44 () = 44

• We can think of f44 is a substitute for the primitive Integer 44 which helps us express specific elements as functions or morphisms

2.6.3 void/Unit as a Return Type

• This is normally used for side-effecting functions, but these are not mathematical functions
• Formally, a function from set $A$ to Singleton set maps every element of $A$ to the single element of the Singleton. For all sets there exists one such function:

fInt :: Integer -> ()
fInt x = ()
fInt _ = ()

• Note that it doesn't even depend on the type of argument

• Functions that can be implemented with the same formula for any type like this are called parametrically polymorphic

unit :: a -> ()
unit _ = ()

2.6.4 Two-element Set

• In Haskell, the notion of Bool is defined as

data Bool = True | False

• In libc it's a primitive (or if you're willing to suspend your pedantry, that is)
• Functions to the Boolean type are called predicates:
  • isEven, isNumeric, isTerminal, etc.

3 | Categories, Great and Small

3.1 - No Objects

• The category with zero objects consequently has zero morphisms
• It's important in the same way that the empty set, empty type, and the number 0 are important

3.2 - Simple Graphs

• Consider an arbitrary directed graph; we can make it into a category by adding a few more arrows:
  • Ensure that each object has an $\mathbf{id}$ arrow
  • For any two arrows such that the end of one coincides with the beginning of another, add a new arrow to serve as their composition

• Here, we've created a category which has an object for all nodes in our graph, and all possible chains of composable graph edges as morphisms ($\mathbf{id}$ are special chains of length 0).
• This is an example of a free category generated by a graph $G$ and completed by extending it with the minimal number of items to satisfy its laws.

3.3 - Orders

• An Order is a category where a morphism is a comparative relation between objects
• We can verify that Orders are categories as follows:
  • What's the identity in an Order? Every object is less than or equal to itself
  • Can we compose objects in an Order? Yes, if $a \leq b$ and $b \leq c$, then, transitively $a \leq c$
  • Is the composition associative? Also yes
    • A set with this relation is called a Preorder which is a category
    • A stronger conditional relation where

is known as a Partial Order

• Lastly, imposing the condition that any two objects are in relation with each other yields a Linear Total Order

• A Preorder is a category where there is at most one morphism from any object $a$ to object $b$

  • This is called a "thin" category
  • A set of morphisms from objects $a$ to $b$ in a category $C$ is called a Hom-set and is denoted: $\mathbf{C}(a,b)$ or $\mathbf{Hom}_C(a,b)$
  • Every Hom-set in a preorder is either empty or a singleton
    • This includes the Hom-set $\mathbf{C}(a,a)$, the set of morphisms from $a$ to $a$ which must be the singleton containing only the identity
    • There may be cycles in a preorder, but not a partial order
    • Sorting algorithms like quicksort, mergesort, selection sort, etc. can only work on total orders
    • Partial orders can be topologically sorted

3.4 - Monoid as Set

• A monoid is a set with an associative, binary operation and one special element that behaves like a unit with respect to this operation
• E.g., the natural numbers with zero form a monoid under addition. To verify:
  • Associativity: $(a + b) + c = a + (b + c)$
  • neutral element: $0 + a = a$ and $a + 0 = a$
    • The 2nd equation appears redundant because addition is commutative, but commutativity is not a requisite property of monoids, so it's included for thoroughness
• Another example, Strings form a monoid with the binary concatenation operation where the unit is the empty string which can be joined on either side of another string without modifying it

class Monoid m where
  mempty  :: m
  mappend :: m -> m -> m

First, what does the m -> m -> m argument list mean? It can be interpreted as:

1. a function with multiple argument where the last, or rightmost, argument signifies the return type
2. or as a function with one argument (leftmost) that returns a function. This can be hinted using parentheses e.g. m -> (m -> m) but is redundant since arrows are right-associative

We can instantiate a string as an instance of Monoid and define its behavior:

instance Monoid String where
  mempty  = ""
  mappend = (++)

• Note that there are different paradigms for what equality means in programming languages:
  • functional equality: what we have here, mappend = (++), which is the equality of morphisms in the Hask category
    • Also known as point-free equality: equality without specifying arguments
  • extensional equality: mappend s1 s2 = (++) s1 s2, which is also known as point-wise equality, where the value of the function mappend at point (s1, s2) is equivalent to (++) s1 s2

3.5 - Monoid as Category

• Every monoid can be described as a single object with a set of morphisms that follow appropriate rules of composition

• We can always extract a set from a single object category. This set is the set of morphisms. I.e., we have the Hom-set $\mathbf{M}(m, m)$ of the single object $m$ in the category $\mathbf{M}$

  • We can easily define a binary operator in this set: the monoidal product of two set-elements. Given 2 elements of $\mathbf{M}(m, m)$ corresponding to $f$ and $g$, their product will be equivalent to $f \circ g$ and this composition always exists because the source and target of the morphism are the same object $m$.
  • It's associative, and the identity morphism is the neutral element of the product, so we can always recover a set monoid from a category monoid, they're effectively equivalent.

• Note that morphisms don't have to form a set; categories are broader than sets. In fact, a category in which a morphism between any two objects forms a set is called "locally small"

• Elements of a Home-set can be seen as both

  1. morphisms which follow the rules of composition
  2. points in a set

• Composition of morphisms in $\mathbf{M}$ translates into a monoidal product in the set $\mathbf{M}(m, m)$.

4 | Kleisli Categories

• How can we model non-pure functions or side effects in Category Theory?
  • Imperatively, this is achieved by modifying global state

string logger;
bool negate(bool b) {
  logger += "Not so!";
  return !b;
}

• This function is not pure since its memoized version fails to produce a log. A more modern approach might resemble the following:

Pair<bool, string> negate(bool b, string logger) {
  return make_pair(!b, logger + "Not so!");
}

• This still sucks from a design perspective. It would be better to aggregate the log message externally between function calls:

Pair<bool, string> negate(bool b) {
  return make_pair(!b, "Not so!");
}

res = negate(true);
negated = res.first;
logger += res.second;

• But, externally aggregating all logs is gross, and we can abstract this repetition further, but then we'd be abstracting the composition of functions 👻

4.1 - Writer Category

• Embellishing return types of functions is very useful. We start with a regular category of types and functions. We leave types as our objects, but we redefine our morphisms to be the embellished functions
• E.g., We want to embellish isEven which goes from int to bool and turn it into a morphism that is represented by an embellished function
  • This morphism would still need to be considered an arrow between objects int, bool, even though the embellished function returns Pair

Pair<bool, string> isEven(int n) { return make_pair(n % 2 ==0, "isEven"); }

• By laws of categories, wee should be able to compose this with another morphism that goes from object bool to whatever:

Pair<bool, string> negate(bool b) { return make_pair(!b, "Not so!"); }

The literal composition would look like:

Pair<bool, string> isOdd(int n) {
  Pair<bool, str> p1 = isEven(n);
  Pair<bool, str> p2 = negate(p1.first);
  return make_pair(p2.first, p1.second + p2.second);
}

The formula for composition, then, is:

1. Execute the embellished function corresponding to the first morphism
2. Extract the first component of the result and pass it to the second morphism
3. Concatenate the second component of the first result with the second component of the second result.
4. Return the new pair combining the first component of the final result with the concatenated result from (3)

• If we want to abstract this composition, we just need to parameterize the three object involved in our category: two embellished functions that are composable according to our rules, and return the third embellished function.

template<class A, class B, class C>
function<Writer<C>(A)> compose(function<Writer<B>(A)> m1,
                               function<Writer<C>(B)> m2) {
  return [m1, m2](A x) {
    auto p1 = m1(x);
    auto p2 = m2(p1.first);
    return make_pair(p2.first, p1.second + p2.second);
  }
}

4.2 - Writer in Haskell

type Writer a = (a, String) -- alias/typedef, parameterized by a
a -> Writer b -- morphisms

We declare the composition of Writers using Haskell's "fish" operator which is a function of two arguments which are other functions and returns a function

(>=>) :: (a -> Writer b) -> (b -> Writer c) -> (a Writer c)

m1 >=> m2 = \x ->
  let (y, s1) = m1 x
      (z, s2) = m2 y
  in (z, s1 ++ s2)

with the identity:

return :: a -> Writer a
return x = (x, "")

Then, we can compose them:

upCase :: String -> Writer String
upCase s = (map toUpper s, "upCase")

toWords :: String -> Writer [String]
toWords s = (words s, "toWords")

process :: String -> Writer [String]
process = upCase >=> toWords

4.3 - Kleisli Categories

• Based on Monad, where:

  • Objects are the types of the underlying programming language
  • Morphisms from types $A$ to $B$ are functions that go from $A$ to a type derived from $B$ using the particular embellishment
  • Later, we'll see that "embellishment" is an imprecise description of the notion of an endofunctor is a category

• The last degree of freedom is composition itself which is precisely what makes it possible to give denotational semantics to programs that, in imperative languages, are traditionally implemented with side effects.

5 | Products and Coproducts

• In Category Theory, there exists a common construction called the "Universal construction" for defining object in terms of their relationships (morphisms)
  • Pick a pattern or shape constructed from objects and arrows and look for all its occurrences in the category
  • For large enough categories and common enough shapes/patterns, we can find many instances. We can establish a ranking over them and pick what is considered to be the best fit, like a search engine. The line to toe is
    • generality: large recall
    • specifcity: precision

5.1 - Initial Object

• This is the simplest shape. There are as many instance of this shape as there are objects in a given category
• We need to rank them, and all we have are morphisms
  • It is possible that there is an "overall net flow" of arrows from one end of the category to the other, especially in (partially) ordered categories
• We can generalize the notion of object precedence by saying that "$a$ is more initial than $b$" if there is an arrow from $a$ to $b$:

• "The" initial object is one that has arrows going to all other objects
  • There is no guarantee that such an object exists in an arbitrary category, but that's okay.
    • The bigger problem is that there might be too many objects matching this description (good recall, low precision)
  • Leveraging ordered categories which have implicit restrictions on morphisms between objects: there can be at most one arrow between objects since there is only one way of being less than or equal to another object, we get a definition of the initial object: The object that has one and only one morphism going to any object in the category
  • Even this doesn't guarantee uniqueness of the initial object though (if it exists), but it does guarantee uniqueness up to isomorphism.

Examples:

• Within a partially ordered set (poset): initial object is the the least object
• Category of sets and function: empty set (Haskell's Void) and the unique polymorphic function:

absurd :: Void -> a

5.2 - Terminal Object

• Similarly, we can identify an object $a$ which is "more terminal" than $b$

• The Terminal Object is the object with exactly one incoming morphism from any other object in the category

  • The terminal object is also unique up to the point of isomorphism
  • In a poset, the terminal object is the "biggest" object
  • In the category of sets and functions, it's a singleton
  • In Haskell, it's the unit (), and in C/C++ it's void

• Earlier, we established that there is only one pure function from any type to the unit type:

unit :: a -> ()
unit _ = ()

Here, uniqueness is critical, because there are other sets (all of them, actually, except for the Empty category) that have incoming morphisms from every set.

• There exists a boolean function (predicate) defined for every type:

yes :: a -> bool
yes _ = True

But this isn't the/a terminal object, because there's at least one more:

no :: a -> bool
no _ = False

• Insisting on uniqueness gives us just the right amount of precision to narrow down the definition of the terminal object to just one type

5.3 - Duality

• Observing the symmetry between definitions of initial and terminal objects, we can reason that: for any category, we can define the opposite category: $\mathbf{C}^{op}$, just by reversing all the arrows
  • This automatically satisfies all the requirements of a category as long as we simultaneously redefine composition. If the original morphisms

f :: a -> b
g :: b ->
-- composed to
h :: a -> c

with $h = g \circ f$, then the reversed morphisms must be $f^{op} : b \rarr a$ and $g^{op} : c \rarr b$ and will compose to $h^{op} : c \rarr a$, $h^{op} : f^{op} \circ g^{op}$.

Reversing the identity morphisms is a no op: $\circlearrowleft, \circlearrowright$

• Duality doubles the "productivity" as, for all categories once concocts, there exists the dual category you get for free!

5.4 - Isomorphisms

• Intuitively it means, "they look the same." That is, every part of $a$ corresponds to $b$

• Formally, it means that there exists a mapping from $a \rarr b$ and back, $b \rarr a$, and they (the mappings) are the inverse of one another

• Inverse here is defined in terms of composability and identity:

  • a morphism $g$ is the inverse of $f$ if their composition is the identity: $f \circ g = \mathbf{id}$ and $g \circ f = \mathbf{id}$

• Recall that the initial and terminal objects are unique up to isomorphism. This is because any two initial or terminal objects are isomorphic.

For example, take two initial object $i_1, i_2$. Since $i_1$ is initial, there exists a unique morphism $f$ from $i_1 \rarr i_2$. By the same reasoning, we have $g: i_2 \rarr i_1$.

• Note that all morphisms here are unique.
• The composition of $g \circ f$ must be a morphism from $i_1 \rarr i_2$, but $i_1$ is initial, so there can only be one morphism from $i_1 \rarr i_1$.
  • Since we are in a category, we know there is an identity morphism from $i_1 \rarr i_1$, and since there can only be one, that must be it (the identity).
  • Therefore, $g \circ f = \mathbf{id}$, similarly $f \circ g = \mathbf{id}$ since there exists only one morphism from $i_s \rarr i_2$.
  • Therefore $f$ and $g$ must be inverses of one another, so two initial objects are isomorphic
• Not that $f$ and $g$ must be unique in this proof because not only is the initial object unique up to isomorphism, but it is unique up to unique isomorphism.
  • There could be multiple isomorphisms between two objects

5.5 - Products

• Recall that the Cartesian product of two sets is the set of all pairwise combinations therein:

• How can we generalize this pattern that connects the product set with its constituent sets?
  • In Haskell, we have two functions, the projections, from the product to each constituent:

fst :: (a, b) -> a
fst (x, _) = x

snd :: (a, b) -> b
snd (_, y) = y

• With even this limited vocabulary, we can construct the product of two sets $a,b$ which consists of an object $c$ and two morphisms $p,q$ connecting it to $a$ and $b$ respectively:

p :: c -> a
q :: c -> b

• All $c$'s which fit the pattern can be considered candidates for the product, there might be multiple:

For example, we can define two Haskell types as our constituents, Int, Bool:

p :: Int -> Int
p x = x

q :: Int -> Bool
q _ = True

Which, as it stands, is pretty lam, but matches our criteria. Consider a denser, but also satisfactory pair of constituent types:

p :: (Int, Int, Bool) -> Int
p (x, _, _) = x

q :: (Int, Int, Bool) -> Bool
q p (_, _, b) = b

Whereas the first set of projections was too small, only covering the Int dimension of the product, these candidates are too broad, with the unnecessary duplicate Int dimension.

Returning to the universal ranking, how do we compare two instances of our pattern? That is, how do we evaluate

• We would like to say that $c$ is "better" than $c'$ if there is a morphism $m$ from $c' \rarr c$, but that constraint alone is insufficient. We also want its projections to be "better" or "more universal" than those of $c'$.
  • We want to be able to reconstruct $p', q'$ from $m$ and $c'$'s projections:

• This can be interpreted as "$m$ factorizes $p'$ and $q'$."
• Using the pair (Int, Bool), with the two canonical projections / "vocabulary" introduced earlier: fst, snd are "better" than the other two candidates:

-- mapping for first, simple candidate
m :: Int -> (Int, Bool)
m x = (x, True)

-- reconstructions of projections
p x = fst (m x) = x
q x = snd (m x) = True

And in our second, more complex example, $m$ has a similar uniquely determined $m$:

m (x, _, b) = (x,b)

Therefore, (Int, Bool) is better than either of the other two candidates. Why isn't the opposite true? That is, can we find some $m'$ that would help reconstruct fst, snd from $p, q$?

fst = p . m'
snd = q . m'

• In our first example, $q$ always returns True, and we know that there exist pairs with second components that are False, which we can't reconstruct from $q$ as defined.

• In the second example, we return enough information after $p$ or $q$, but there's multiple factorization of fst and snd since both $p$ and $q$ ignore the second component of the triple. Our m' can put anything there:

m' (x, b) = (x, x, b)

-- or

m' (x, b) = (x, 42, b)

Thus, given any type $c$ with two projections $p, q$, there is a unique $m$ from $c$ to the Cartesian product $(a, b)$ that factorizes them:

m :: c -> (a, b)
m x = (p x, q x)

which makes the Cartesian product $(a, b)$ our best match, which implies that this universal construction works in the category of Sets.

Now, let's generalize that same universal construction to define the product of two objects in any category.

• Note that the product doesn't necessarily always exist, but when it does, it is unique up to unique isomorphism

• A product of two objects $a$ and $b$ is the unique object $c$ equipped with two projections such that, for any other object $c'$ equipped with two projects, there is a unique morphism $m$ from $c'$ to $c$ that factorizes those projections

• A higher order function which produces that factorizing function $m$ from two candidates is sometimes called the factorizer:

factorizer :: (c -> a) -> (c -> b) -> (c -> (a, b))
factorizer p q = \x -> (p x, q x)
-- \x is a lambda expression or anonymous function

• to summarize, products are ranked according to their ability to factorize the morphism of their competing product-candidate's projections

5.6 - Coproducts

• Like every construction in Category Theory, the product has a dual: the coproduct
• Reversing the arrows in the product pattern yields an object $c$ with two injections $i,j$ which are morphisms from $a,b \rarr c$ respectively:

• The ranking of possible coproducts is also inverted such that $c$ is "better than" $c'$ (also equipped with two injections $i', j'$) if there is a morphisms $m$ from $c$ to $c'$ which factorizes the injections:

• A coproduct of two objects $a,b$ is the object $c$ equipped with two injections such that for any other object $c'$ equipped with two injections, there is a unique morphism $m$ from $c$ to $c'$ that factorizes those injections.
  • In the category of Sets, it is the disjoint union of two sets: an element of the disjoint union of $a, b$ is either an element of $a$ or an element of $b$. If $a$ and $b$ overlap, then the disjoint union contains two copies of the common part (somehow skirting the definition of a set??)
    • The skirting part happens by "tagging" the elements with an identifier that specifies the origin

In programming terms, it's represented as a union with the added field of a tag enum:

struct Contact {
  enum { isPhone, isEmail} tag;
  union {int phoneNum; char const* emailAddr; };
}
// with injections as "constructors" or functions:

Contact PhoneNum(int n) {
  /** this example is straight from the book,
      but this should be dynamically allocated 💅 **/
  Contact c;
  c.tag = isPhone;
  c.phoneNum = n;
  return c;
}

• Tagger unions are sometimes called variants

In Haskell:

data Contact = PhoneNum Int | EmailAddr String
helpdesk :: Contact
helpdesk = PhoneNum 9118675309

• Unlike the canonical implementation of product which is the primitive Pair, Haskell's coproduct is a data type Either:

data Either a b = Left a | Right b

• Just as we defined a factorizer for a product, we can define one for coproduct. Given a candidate type $c$ and two candidate injections $i,j$, the factorizer for Either produces the factorizing function:

factorizer :: (a -> c) -> (b -> c) -> Either a b -> c
factorizer i j (Left a) = i a
factorizer i j (Right b) = j b

5.7 - Asymmetry

• Despite the similarities between categories and their duals obtained by reversing morphisms, and similarity with initial / terminal objects in the category of sets, there are important qualities of these elements which are not symmetric:

  • Product behaves like multiplication, with the terminal object playing the role of the multiplicative identity of one
  • Coproduct behaves more like a sum, with the initial object playing the role of zero.

• For finite sets:

  • The size of the product is the product of the sizes of individual sets
  • The size of the coproduct is the sum of the sizes

• Therefore, the category of sets is not symmetric with respect to just inversion of arrows.

• Other asymmetries include:

  • Empty set: has a unique morphism to any set (the absurd function), but has no incoming morphisms
  • Singleton set: has a unique morphism to it from every set, but it also has outgoing morphisms to every set (excluding the empty set)
    • It is inherently tied to the product which is what sets it apart from the coproduct

Consider using this set, represented by the unit (), as yet another, vastly inferior candidate for the product pattern, equipped with two projections $p, q$ from the singleton to each constituent set. Because the product is universal, there is also a unique morphism $m$ from our unit candidate to the product.

Recall that $m$ select an element from the product set and factorizes the two projections:

p = fst . m
q = snd . m

When acting on the singleton value, the only element is (), so these become:

p () = fst (m ())
q () = snd (m ())

Conversely, there is not an intuitive interpretation of how this behaves for the coproduct, since the unit () tells us nothing about the source of the injections.

This is a property of functions, not sets. Functions in general aree asymmetric.

• A function must be defined for every element in its domain.
  • In programming language, it's a total function.
  • But, it doesn't have to cover the whole codomain or range
• When the size of the domain is substantially less than that of the codomain, we think of such functions as embedding the domain in the codomain.
  • I.e. $f$ from a singleton is embedded in the codomain
  • Formally, these are referred to as surjective/onto: functions that tightly fill their codomains
  • A function $f$ that maps an element $x$ to every element $y$ that is, for every $y$, there is an $x$ such that $f(x) = y$
• Another source of asymmetry is that functions are allowed to map many elements of the domain set into one element of the codomain
  • I.e. the unit collapses a whole set into a singleton. Collapsing in this way is composable, and the results of composing collapsing operations are compounded
  • These functions are called injective or one-to-one
• Bijections are the middle child of classes of functions in that they are symmetric because they are invertible. Isomorphisms in category theory are equivalent to bijections

6 | Simple Algebraic Data Types

• Many common data structures can be built using the two Algebraic Data Types covered so far: product, coproduct
  • For composite types (types construct from primitives), equality, comparison, conversion, and more can be derived from the properties of products and coproducts

6.1 - Product Types in Programming

• Canonically a a product in Haskell is a primitive Pair, in C++, it's a template from the stdlib
  • Pair's aren't strictly commutative, meaning that (Int, Bool) is not necessarily equivalent to (Bool, Int), but they are commutative up to the isomorphism given by a swap function:

swap :: (a, b) -> (b, a)
swap (x, y) = (y, x)

• We can generalize the swap function for nested types since the different ways of nesting Pairs are isomorphic to one another. E.g., nesting a product triple of a, b, c can be achieved two ways:
  • (a, (b, c)) and ((a, b), c)
  • These are different types, but their elements are in 1:1 correspondence and we can map between them:

alpha :: ((a, b), c) -> (a, (b, c))
alpha ((x, y), z) = (x, (y, z))

which, like swap, is also trivially invertible

The creation of a product type can be interpreted as a binary operation on types. Thus, the alpha isomorphism looks very similar to the associativity law for monoids:

Except that in the monoid case, these two compositions were equal, whereas here they're only equal up to isomorphism

• If we're content with equality up to isomorphism (which we are), and don't need strict equality (which we don't), we can go even further and show that the unit type () is the unit of the product in the same way that $1$ is the unit of multiplication.
  • Pairing a value type with a unit doesn't add any information, e.g., (a, ()) is isomorphic to a via:

rho :: (a, ()) -> a
rho (x, ()) = x

-- inverted by

rho :: a -> (a, ())
rho x = (x, ())

• Formally, the category of sets is a monoidal category because we can multiply objects by taking their Cartesian product

6.2 - Record

Example: We want to design a representation for a chemical element, and be able to verify that a chemical's symbol corresponds to the prefix of its name:

startwithsymbol :: (String, String, Int) -> Bool
startwithsymbol (name, symbol, _) = isPrefixOf symbol name

But this is bad, error prone, and reliant on contextual clues. A better model might resemble:

data Element = Element {
                         name :: String,
                         symbol :: String,
                         atomicNo :: Int
                        }

These two representations are isomorphic as evidenced by some conversion functions:

tupleToElem :: (String, String, Int) - Element
tupleToElem (n, s, a) = Element { name = n, symbol = s, atomicNo = a }

elemToTuple :: Element -> (String, String, Int)
elemToTuple e = (name e, symbol e, atomicNo e)
-- names of data fields serve as getters to access those fields

We can clean up our initial attempt at modeling a chemical as follows

startwithsymbol :: Element -> Bool
startwithsymbol e = isPrefixOf (symbol e) (name e)

6.3 - Sum Types

• Just as the product in the category of sets gives way to product types, coproducts correspond to sum types, canonically expressed as Either types
  • They are also commutative up to the point of isomorphism and
  • nestable up to the point of isomorphism (e.g., we can have a triple as a sum)

data oneOfThree a b c = Sinistral a | Medial b | Dextral`

• Set is also a symmetric monoidal category with respect to coproduct where

  • the binary operation is disjoint sum: Either $\approx +$
  • the unit element is the initial object: Void $\approx 0$
  • Accordingly, Either a Void is equivalent to a since it's not possible to construct a value of type Void: $a + 0 = a$
  • Sums are common in Haskell / FP
    • Less so in imperative languages, though they can be represented as variant unions (tagged unions)
    • Enums usually suffice, or primitives like stdbool.h

• Sum types which communicate the presence or absence of value or represented in Haskell as

data Maybe a = Nothing | Just a
--             ()        encapsulates a

• Immutability in FP allows repeated use of constructors for pattern matching in the reverse language

6.4 - Algebra of Types

• While powerful alone, combining the product and sum types via composition yields even richer types
• We have two commutative monoidal structures underlying our small type system so far:
  • Sum with Void as the neutral element representing $0, +$
  • Product with () as the neutral element representing $1, \times$
• Do these follow the expected rules of arithmetic like $0 * n = 0$?
  • Is a product with one component being Void isomorphic to Void? Can we create a Pair of (Int, Void)?
  • We need two values; we can take any Int for the first component of the Pair, but there are no values of type Void, so the type (Int, Void) is also uninhabited, which is equivalent to Void
  • $a \times 0 = 0$ ✅
  • Furthermore, the distributive property also follows from this:

    a * (b + c) = a * b + a * c
(a, Either b c) = Either (a ,b) (a, c)

given by

prodToSum :: (a Either b c) -> Either (a, b) (a, c)
prodToSum = (x, e) = case e of
                      Left y  -> Left (x, y)
                      Right z -> Right (x, z)

sumToProd :: Either (a, b) (a, c) -> (a, Either b c)
sumToProd e = case e of
                Left (x, y)  -> (x, Left y)
                Right (x, z) -> (x, Right z)

• Two such intertwined monoids are called semi-rings (semi because we can't/haven't defined subtraction or division on types)
• Interpreting semi-ring types as natural numbers yields the following correspondences

| Expression | Type | | ------------ | --------------------------------- | -------- | | $0$ | Void | | $1$ | () | | $a + b$ | Either a b = Left a | Right b | | $a \times b$ | (a, b) or Pair a b = Pair a b | | $2 = 1 + 1$ | data Bool = True | False | | $1 + a$ | data Maybe = Nothing | Just a |

• List is defined as a recursive solution to an equation:

data List a = Nil | Cons a (List a)
-- `Cons` is a historical holdover name from Lisp for Constructor

If we do some algebraic substitutions using the table above and replace List a with $x$, and we get:

But, because we're working with a semiring, we can't solve this equation with division or subtraction. Instead, we'll keep replacing $x$ with $1 + a * x$:

An infinite sum of product tuples which can be:

• an empty list,

• a singleton

• a pair of $(a * a)$

• a triple of (a _ a _ a), etc.

• The product of two types $a, b$ must contain both a value of type $a$ and a value of type $b$; they both must be inhabited

• Sums can contain either a value for type $a$ or type $b$, but both are not required

• Logical and and or also form a semiring and can be mapped to Type Theory:

| Expression | Type | | ---------- | -------------------- | -------- | | $false$ | Void | | $true$ | () | | $a \| b$ | Either a b = Left a | Right b | | $a \&\& b$ | (a, b) |

• Logical types and natural numbers are isomorphic via types

7 | Functors

• A Functor is a mapping between categories
• Given two categories $\mathbf{C, D}$, a functor $F$ maps objects in $\mathbf{C}$ to objects in $\mathbf{D}$
• If $a$ is an object in $\mathbf{C}$, we write its image in $\mathbf{D}$ as $Fa$
• A functor also maps morphisms –it's function on morphisms, but it doesn't just map morphisms willy nilly– it preserves connections
  • If A morphism $f$ in $\mathbf{C}$ connects $a \rarr b$, ($f :: a \rarr c$) then the image of $f$ in $\mathbf{D}, Ff$ will connect the image of $a$ to the image of $b$: $Ff :: Fa \rarr Fb$

• Functors preserve the structure of a category: what's connected in one category is connected in another
  • We also need to preserve the composition of these morphisms. E.g., if we have $h = g \circ f$, we want its image under $F$ to be a composition of the images of $f, g$

• Finally, we want all identity morphisms in $\mathbf{C}$ to be mapped to the identity morphisms in $\mathbf{D}$:

where $\mathbf{id}_a$ is the identity at object $a$ and $\mathbf{id}_{Fa}$ is the identity at $Fa$.

• Not that functors are more restrictive than regular functions in that they must preserve the structure of the program. They can't introduce and "tears," but they can "combine" morphisms.
  • This restriction is roughly analogous to the occasional requirement of continuity of functions in calculus
• Functors can also collapse and embed, just like functions as described earlier, where embedding is more prominent when the source category is smaller than the target category; I.e., the source being the Singleton, and the target is any other arbitrary Category (excluding the empty category, of course)
• A functor from a singleton to any other category will just select an object from the target, just like a morphisms from a singleton set
• The maximally collapsing functor is called the constant $\Delta_\mathbf{C}$, which maps every object in the source category to one object in $\mathbf{C}$, the target, and also maps every morphism in the source to the identity $\mathbf{id_C}$
  • It's like a black hole

7.1 - Functors in Programming

• We have the category of types and functions
• An endofunctor of this category maps to the category itself

7.1.1 - The Maybe Functor

Recall the Maybe doohicky:

data Maybe a = Nothing | Just a

Here, Maybe is not a type, but a type constructor. It needs a type argument to be a type, otherwise it's just a function on types

For example, for any function from a to b:

f :: a -> b

we want to produce a function

Maybe a -> Maybe b

• In the case of having Nothing in the Maybe, we just return Nothing
• In the case of Just, we apply f to its contents such that the image of f under Maybe is

f' :: Maybe a -> Maybe b
f' Nothing = Nothing
f' (Just x) = Just (f x)

• In Haskell, we can implement the morphism-mapping part of a functor as a higher order function call fmap, which would resemble the previous case:

fmap :: (a -> b) -> (Maybe a -> Maybe b)

• We say that a fmap lifts a function
• To show that the type constructor Maybe along with the fmap function forms a functor, we have to show that fmap preserves both identity and composition: the Functor Laws

7.1.2 - Equational Reasoning

• Equational reasoning is a means of proof which relies on substitution. I.e., base on the definition of fmap given above, if we saw an expression like fmap f Nothing, we could replace it with just Nothing
• Using this to show that fmap preserves identity we get:

fmap id = id -- which has two cases

-- case Nothing
fmap id Nothing = Nothing      -- the definition of fmap
                = id Nothing   -- definition of id

-- case Something
fmap id (Just x) = Just (id x) -- definition of fmap
                 = Just x      -- definition of id
                 = id (Just x) -- definition of id

• Then, to show preservation of composition:

fmap (g . f) = fmap g . fmap f

-- case Nothing
fmap (g .f) Nothing = Nothing        -- definition of fmap
                    = fmap g Nothing -- definition of fmap
                    = fmap g (fmap f Nothing)
                                     -- definition of fmap

-- case Something
fmap (g .f) (Just x) = Just ((g . f) x)    -- definition of fmap
                     = Just (g (f x))      -- definition of composition
                     = fmap g (Just (f x)) -- definition of fmap
                     = fmap g (fmap f (Just x))
                                           -- definition of fmap
                     = (fmap g . fmap f) (Just x)
                                           -- definition of composition

7.1.3 - Optional

• Ugly sketch of an implementation in c++

7.1.4 - Typeclasses

• How do we abstract the functor
  • This is an utterly psycho question. Where do you draw the line bruh
• Typeclasses define a family of types that support a common interface

For example, the class of objects which support equality:

class Eq a where
  (==) :: a -> a -> bool

data Point = Pt Float Float
instance Eq Point where
  (Pt x y) == (Pt x' y') = x == x' && y == y'

• Problem: a functor is not defined as a type, but as a mapping of types... But Haskell typeclasses work with type constructors as well as types:

class Functor f where
  fmap :: (a -> b) -> fa -> fb

Here, f is a functor, and if there exists an fmap w that type signature, then the Haskell compiled can deduce that f is a type constructor, not a type

instance Functor Maybe where
  fmap _ Nothing = Nothing
  fmap f (Just x) = Just (f x)

7.1.5 - Functor in c++

• I sleep

7.1.6 - The List Functor

• Any type that is parameterized by another type is a good candidate for to be a functor, I.e., most generic collections

data List a = Nil | Cons a (List a)

• To show that List is a functor, we have to define the lifting functions: given a function a -> b, define a function List a -> List b

fmap :: (a -> b) -> (List a -> List b)

which also has two cases:

• Nil: easy, since there's not much to do with an empty list
• Cons List a: a bit tricky with recursion:
  • We have a list of a, a function f that turns a -> b, and we want a list of b
  • The constructor Cons joins the head of a list with the tail
  • We apply f to the head and apply the lifted f to the tail

fmap f (Cons x t) = Cons (f x) (fmap f t)
-- this is recursively bound by the necessarily shrinking
-- portion of the list until we reach Nil and we have
-- previously defined: fmap f Nil = Nil, which will terminate

All together then:

instance Functor List where
  fmap _ Nil = Nil
  fmap f (Cons x t) = Cons (f x) (fmap f t)

7.1.7 - Reader Functor

• Consider a mapping of type a to the type of a function returning a

  • Mappings of function types are coming down the road, but we have some programming intuition about function types

• (a ->b) takes a and returns b and is equivalent to (->) a b

• Just like with regular functions, type functions of more than one argument can be partially applied such that when we provide just one type argument, it still expects another on, meaning that (->) a is a type constructor, awaiting a type b to produce a complete type signature

• This defines a whole family of type constructors parameterized by a.

  • Are they functors, though? Lets rename the argument type to be r and the result type to be a so the type Cons takes any type a and maps it to type r -> a.
  • To show that it's a functor, we need to lift a function a -> b to a function (->) a which returns (r -> b) (the types formed using the type constructor (-> r) acting on a, b respectively)

fmap :: (a -> b) -> (r -> a) -> (r -> b)

Given a function

f :: a -> b

and

g :: r -> a

we want to create r -> b, and there is only one way to compose f, g and the result is r -> b

instance Functor ((->) r) where
  fmap f g = f . g -- equiv. to just fmap = (.)

7.2 - Functors as Containers

• The reader functor treats functions as data which should feel a bit abnormal, but recall that functions can be memoized and execution can be tabularizeed
• In may functional programming languages, traditional collections may be implemented as functions

naturals :: [Integer] -- built in type constructor
naturals :: [1..]     -- list literal, can't be stored in memory
                      -- but the compiler implements as a function that
                      -- generates ints on demand

Thus, we can blur the lines and move freely between code <--> data

• Think of the functor object (generated by an endofunctor) as containing a value or values of the type over which it is parameterized, even if those values are not physically present
  • It may contain the value, or the recipe for generating those values
  • Future may have the value, maybe not
  • From a functor level, we don't care if we can access the values at any given time, just that they can be manipulated and composed properly

To illustrate that, let's define a type which completely ignores its argument

Data Const c a = Const c
fmap :: (a -> b) -> Const c -- I don't care, I don't
-- because functor ignores the argument,
-- the impl of fmap is free to ignore its function args

instance Functor (Const c) where
  fmap _ (Const v) = Cons v

Observe that the Constant functor is a special case of $\Delta_\mathbf{C}$: the endofunctor case of the black hole

7.3 - Functor Composition

• Jsut as functions compose between sets, functors compose between categories
• Recall the maybeTail example:

maybeTail :: [a] -> Maybe [a]
maybeTail [] = Nothing
maybeTail (x:xs) = Just xs

• What if we want to apply some f to the contents of the composite Maybe List?
  • We have to break through two layers of functors. fmap breaks through the outer, Maybe later, but we can't just send f inside Maybe because it doesn't work on Lists. We have to send (fmap f) to operate on the inner list:

For example, if we want to swuare the elements of a Maybe List:

square x = x * x

ms :: Maybe [Int]
ms = Just [1, 2, 3]

ms2 = fmap (fmap square) ms

The compiler will recognize that he first, outer fmap pertains to the Maybe component, and the inner fmap to the List, which is also equivalent to

ms2 = (fmap . fmap) square ms
-- since a functor can be considered a function with one arg:
fmap :: (a -> b) -> (f a -> f b)
-- and in our case, the 2nd fmap in (fmap . fmap) takes as its argument
square :: Int -> Int
-- and returns
[Int -> Int]
-- first fmap then takes that function and returns a function
Maybe [Int] -> Maybe [Int]
-- finally, that function is applied to ms

• It's obvious that functor composition is associative and that there exists a trivial identity functor in every category which maps every object to itself, and every morphism to itself
  • So, functors have all the same properties as morphisms in some category
  • But what category? It would have to be a category in which objects themselves are categories, and morphisms are functors; a category of categories!
  • But, a category of all categories would have to include itself, and we get into the same kind of Set Theoretical paradoxes that make the Set of all Sets impossible
  • There exists a category which contains all Small Categories called Cat (which itself is Big, so it can contain itself)
    • All objects in a small category form a set, as opposed to something larger than a set

8 | Functoriality

• Building larger funcors from smaller functors (which correspond to mappings between objects in a category) can be extended to functors (which include mappings between morphisms)

8.1 - Bifunctor

• Since functors are morphisms in Cat, a lot of intuititons about morphisms can apply to functors as well
• A Bifunctor is a functor of two arguments on objects. It maps every pair of objects $(a, b) | a \in \mathbf{C}, b \in \mathbf{D}$ to an object in $\mathbf{E}$.
  • In other words, it's a mapping from a Cartesian product of categories. This alone is straightforward, but functoriality means that a bifunctor also has to map morphisms

• A pair of morphisms is just a single morphism in the product category of $\mathbf{C} \times \mathbf{D} = \mathbf{E}$, and these can be interpreted in the obvious way:

which is associative, has an identity $\mathbf{id} = (\mathbf{id}, \mathbf{id})$ and thus is a category

• We could consider a bifunctor as two separate functors, checking each constituent argument. However, general, separate functoriality does not prove joint functoriality

  • Categories in which joint functoriality fails are called pre-monoidal

• In Haskell, we can define a bifunctor between three identical categories: namely, the category of Haskell types

class Bifunctor f where
  bimap :: (a -> c) -> (b -> d) -> f a b -> f c d
  bimap g h = first g . second h
  first :: (a -> c) -> f a b -> f c b
  first g = bimap g id
  second :: (b -> d) -> f a b -> f a d
  second = bimap id

• The type variable f represents the bifunctor. It's evident from all the type signature, it's always applied to two type arguments, and the result is a lifted function (f a b -> f c d), operating on types generated by the bifunctor's type constructor
• There's a default implementation of bimap in terms of first and second, but this might not always be an available pattern because two maps may not commute (more on what the hell this means later, but for the time being):

The two other signatures of first and second are the two fmaps witnessing the functoriality of f in the first and second arguments of the bifunctor

First

Second

• When declaring an instance of bifunctor, you either have to define bimap and accept the defaults for first, second or implement first, second yourself and accept the defaults for bimap

8.2 - Product and Coproduct Bifunctors

• A categorical product is a bifunctor. The simplest example is the bifunctor instance for a Pair constructor:

instance Bifunctor (,) where
  bimap f g (x ,y ) = (f x, g y)

which is preetty straightforward, bimap applies first to x and second to y

bimap :: (a -> c) -> (b -> d) -> (a, b) -> (c, d)

and the action of the bifunctor here is to make pairs of types:

(,) a b = (a, b)

and, by duality, a coproduct if its defined for every pair in the category, is also a bifunctor.

• We can now add to our definition of a Monoidal Category that the binary operator must be a bifunctor

8.3 - Functorial Algebraic Data Types

• We can specify the construction of complex types from simpler types relying on the sum and product types (which we've just shown are functorial) as ADTs

• What are the building blocks of parameterized ADTs?

  • First, there are items with no dependency on the type parameter(s) of the function. For example, $Nothing \in Maybe$, $Nil \in List$, or any other form of our Const functor
  • Then, there are also elements which Just encapsulate the type parameter itself, like $Just \in Maybe$
    • These are equivalent to the identity functor:

data Identity a = Identity a
instance Functor Identity where
  fmap f (Identity x) = Identity (f x)

We can no redefine Maybe in terms of these ADTs:

data Maybe a = Nothing | Just a

-- vs

type Maybe a Either (Const () a) (Identity a)

Thus, Maybeis the composition of the bifunctor Either with two functors: Const () and Identity

• We can express this composition with a Haskell datatype, paramterized by a bifunctor (a type variable that is a type constructor that takes two types as arguments), two functors fu, gu (which take one type variable each), and two regular types

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

• This type is a bifunctor in a, b but only if bf is a bifunctor and fu, gu are functors. The compiler must know that there will be a definition of bimap available for bf and have fmap definitions for fu, gu
  • In Haskell, this is expressed as a precondition in the instance declaration:

instance (Bifunctor bf, Functor fu, Functor gu) =>
  Bifunctor (BiComp bf fu gu) where
    bimap f1 f2 (BiComp x) = BiComp ((bimap (fmap f1) (fmap f2)) x)

• The implementation of bimap for BiComp is given in terms of bimap for bf and the two fmaps for fu, gu. the compiler auto-infers all the types and picks the correct overloaded functions whenever BiComp is invoked
• The x in the above definition has the type bf (fu a) (gu b)
• The outher bimapbreaks through the outer bf layer, and the two fmaps "dig" under fu and gu, respectively. If the types of f1, f2 are:

f1 :: a -> a'
f2 :: b -> b'

then the final result of bf (fu a') (gu b') is

bimap :: (fu a -> fu a') -> (gu b -> gu b') -> (bf (fu a) (gu b) -> bf (fu a') (gu b'))

• The Haskell compiler can and will derive all this for you if the appropriate flags are set, and will do the same for other ADTs due to their mechanical regularities

8.4 - Functors in C++

you thought

8.5 - The Writer Functor

• Returning to the Kleisli category, recall that morphisms were represented as embellished functions returning a Writer data structure:

type Writer a (a, String)

• Now, we can recognize that the Writer type constructor is a functorial in a, which doesn't even need an fmap since it's just a simple product
• What, then, is the relationship between a Kleisli category and a functor
  • Recall that composition within this category was defined by the fish operator:

(>=>) ::(a -> Writer b) -> (b -> c) -> (a -> Writer c)
m1 >=> m2 = \x ->
  Let (y, s1) = m1 x
      (z, s2) = m2 y
  in (z s1 ++ s2)

-- and the identity morphisms is given by:

return :: a -> Writer a
return x = (x, "")

• We can combine the types of these functions to produce a function with the right signature to serve as fmap:

fmap f = id >=> (\x -> return (f x))

the fish operator combines two functions:

• id
• a lambda expression that applies return to the result of f and the lambda argument \x

How it works:

1. The identity will take Writer a and "turn it into" Writer a
2. The fish will extract the value of a and pass it as x to the lambda where f will turn it into a b and return will embellish it to become a Writer b
3. All together, it takes a Writer a and yields a Writer b which is what fmap is s'posed to do

As long as the type constructor (in this case Writer) supports the fish operator (composition) and return (identity), this constructor can define fmap for anything, thus Embellishment in the Kleisli category is always a functor (but not vice versa)

8.6 - Covariant and Contravariant Functors

• Let's return once more to the Reader functor that we based on the partially-applied arrow type constructor

(->) r

-- which is synonymous with

type Reader r a = r -> a

-- for which we have the familiar functor instance

instance Functor (Reader r) where
  fmap f g = f . g
``

- Is `Reader` functorial in the first argument?  Let's start with a type synonym like reader with its argumeents flipped

```haskell
type Op r a = a -> r

• Can we construct an fmap :: (a -> b) -> (a -> r) -> (b -> r) ?
  • With just tow functions taking a and return b, r respectively, no!
  • We can't inveert an arbitrary function, but we can go to the opposite category
    • Recall that, for all categories $\mathbf{C}$, there exists an opposite category $\mathbf{C}^{op}$, its dual with all the same objects, but with inverted morphisms
    • Q: Why can't we just invert arbitrary functions then

Consider a functor that goes between $\mathbf{C}^{op}$ and $\mathbf{D}$

which maps a morphism $f^{op} :: a \rarr b$ in $\mathbf{C}^{op}$ to the morphisms $Ff :: Fa \rarr Fb$ in $\mathbf{D}$. But $f^{op}$ secretly corresponds to some morphism $f :: b \rarr a$ in the original category $\mathbf{C}$

• $F$ is a regular functor, but we can define another mapping based on $F$, which will not be a functor, call it $G$, which maps from $\mathbf{C}$ to $\mathbf{D}$. It maps objects the same way that $F$ does, but when mapping morphisms, it reverses them such that a morphism $f :: b \rarr a$ in $\mathbf{C}$ is first mapped to the opposite morphism: $f^{op} :: a \rarr b$, then uses $F$ on it to get $\\ Ff^{op} :: Fa \rarr Fb$
• Since $Fa, Fb$ is the same as $Ga, Gb$, the whole composition can be described as