1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//! ## or, an exploration of category theory for _systems programmers_
//!
//! 
//!
//! What follows in this library is derived from _Category Theory for Programmers_, a long-running blog series by
//! [Bartosz Milewki](https://twitter.com/BartoszMilewski). A nice "book" created from original blog posts can be found [here](https://github.com/hmemcpy/milewski-ctfp-pdf).
//!
//! #### Crate Health
//!
//! [](https://travis-ci.org/damienstanton/ctrs)
//!
//! ### Goals
//!
//! My intention is simply to share my learning experience with category theory by using the built-in documentation and
//! testing faculties that Rust provides. I will also conduct screen casts to explore each implementation so that I can
//! make sure that what I commit to the crate is logical. I hope that by doing this, others can apply this knowledge to
//! what they do at `$WORK` in C++, Go, Java, etc.
//!
//! ### Table of Contents
//! | CTFP Chapter | Topic | Articles | Lecture Videos | Notes |
//! | -- | --- | --- | --- | --- |
//! | 1 | Introduction | [Category: The Essence of Composition](https://bartoszmilewski.com/2014/11/04/category-the-essence-of-composition/) | [Motivation](https://youtu.be/I8LbkfSSR58), [What is a category?](https://youtu.be/p54Hd7AmVFU) |See [`id`](./fn.id.html) and [`compose`](./fn.compose.html)|
//!
//! ### Non-code challenge questions:
//!
//! Chapter 1
//!
//! _Is the world-wide web a category in any sense? Are links morphisms?_
//!
//! > I would say yes. We know that web pages have something akin to an identity morphism: its URI/URL. And links between pages
//! may be composable (a link from site A to B can, through the redirect protocol, map to a third side C).
//!
//! Update: After a conversation with a few people in the #categorytheory channel on FP Slack, care must be
//! taken to specify that we mean the morphism that defines the whole REST or HATEOAS command cycle for a link in this example; not the
//! links themselves. So the correct answer to Bartosz's question depends on what we mean by what `links` are.
//!
//! _Is Facebook a category, with people as objects and friendships as morphisms?_
//!
//! > Not really, because social relationships cannot always compose. Friend C, friend of B, is not necessarily friend of A.
//!
//! _When is a directed graph a category?_
//!
//! > A DAG would classify as a category when a graph _G_ has vertices _V_ and edges _E_ such that:
//! > - all paths in the graph can be concatenated
//! > - each V has an E that loops back to itself (so that it satisfies identity)
/// Identity is a unit under composition.
///
/// # Overview
/// We describe a function over a generic type `T` that simply returns its parameterized value, unchanged. This might
/// seem a little odd.
///
/// But as Bartosz describes, the motivation for understanding identity is to enable a higher order of composition:
/// > 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.
/// > Ancient Romans had a number system without a zero and they were
/// > able to build excellent roads and aqueducts, some of which survive to
/// > this day.
/// > 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. So the identity function becomes very handy as
/// > an argument to, or a return from, a higher-order function. Higher order
/// > functions are what make symbolic manipulation of functions possible.
/// > They are the algebra of functions.
/// >
/// > To summarize: A category consists of objects and arrows (mor phisms). Arrows can be composed, and the composition is associative.
/// >
/// > Every object has an identity arrow that serves as a unit under composition.
///
/// # Example
/// ```
/// use ctrs::id;
///
/// let x = 1;
/// assert_eq!(id(1), 1);
///
/// let y = "OK";
/// assert_eq!(id(y), "OK");
/// ```
/// Composition is the heart of categorical computation.
///
/// # Overview
/// Our definition of composition may appear confusing at first, but let's break it down. We start by defining generic
/// types for our two input functions. These are`F` and `G`, respectively. These have a `'static` lifetime because we
/// have to ensure that the borrow checker does not let these types out of scope before computation has finished. Next,
/// we have types `Fv` and `Gv`, which represent the types for the return values for each of the functions F and G.
/// Finally, we have our output type `V`, which is the result we want. We pass the functions F and G as parameters `f`
/// and `g`.
///
/// Still with me?
///
/// Next, the return value is a `Box` of the generic `Fn` type that takes an Fv to a V. We have to _box_ the return
/// value because we do not know how much size it could occupy on the stack (thus we allocate to the heap). Finally, we
/// implement trait bounds on F and G, specifying how the chain should compose: F takes an Fv to a Gv, and then G takes a
/// Gv to V.
///
/// Phew! 😅
///
/// Let's now see how this looks in practice using an example.
///
/// # Example
/// ```
/// use ctrs::{id, compose};
///
/// // Let's first define a trivial incrementer function.
/// fn inc(x: i32) -> i32 {
/// x + 1
/// }
///
/// // and cover our bases by confirming inc works as expected.
/// let x = 1;
/// assert_eq!(inc(x), 2);
///
/// // Since we are composing functions on a given value, the syntax is
/// // compose(A, B)(V). Knowing this, our passing test looks like:
/// assert_eq!(compose(id, inc)(1), 2);
/// ```
///
/// We can extend this idea! Let's take the situation where we've also defined an admittedly contrived `double`
/// function, and want to compose its behavior with our existing incrementer. Mathematicians sometimes call the
/// composition operator one might find in Haskell _after_, and understanding the way in which the function associates
/// is indeed _g after f_.
/// ```
/// # use ctrs::{id, compose};
/// # fn inc(x: i32) -> i32 {
/// # x + 1
/// # }
/// fn double(x: i32) -> i32 {
/// x * 2
/// }
///
/// let x = 1;
/// assert_eq!(compose(inc, double)(1), 4);
/// ```