-
Notifications
You must be signed in to change notification settings - Fork 1
/
Why-Category-Theory.html
199 lines (181 loc) · 18.4 KB
/
Why-Category-Theory.html
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<link rel="icon" type="image/png" href="./images/favicon-32x32.png" sizes="32x32" />
<link rel="icon" type="image/png" href="./images/favicon-16x16.png" sizes="16x16" />
<title>Why Category Theory - SPK's Rationality Essays</title>
<link rel="stylesheet" type="text/css" href="./css/default.css" />
<link rel="stylesheet" type="text/css" href="./css/highlight.css" />
<!-- <script src="http://ajax.googleapis.com/ajax/libs/jquery/1.10.2/jquery.min.js"></script> -->
<!-- <script type="text/javascript" src="/js/header-links.js"></script> -->
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<link href="atom.xml" type="application/atom+xml" rel="alternate" title="Sitewide ATOM/RSS Feed" />
<!-- Google Analytics stuff -->
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-DEWF2J5BG8"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-DEWF2J5BG8');
</script>
<script type="text/javascript" src="https://fast.fonts.net/jsapi/f7f47a40-b25b-44ee-9f9c-cfdfc8bb2741.js"></script>
</head>
<body>
<div id="header">
<div id="logo">
<a href="./">SPK's Rationality Essays</a>
</div>
<div id="navigation">
<a href="./">Home</a>
<a href="./notes.html">Notes</a>
<!-- <a href="/about.html">About</a> -->
<a href="./archive.html">Archive</a>
<a href="./atom.xml" type="application/atom+xml" rel="alternate" title="Sitewide ATOM/RSS Feed">RSS</a>
</div>
</div>
<div id="content">
<h1 id="post-title">Why Category Theory</h1>
<!-- <center><img src="https://fbcdn-sphotos-d-a.akamaihd.net/hphotos-ak-prn1/t31.0-8/p600x600/10257116_10202295769100492_2438594605053717342_o.jpg" height="400" width="300" class="sujeet-pic" alt="Sujeet pic" /></center> -->
<p><strong>Question</strong>: Given the function <code>children</code>, how will you write <code>greatGrandChildren</code>?</p>
<hr />
<h1 id="composition-is-not-just-for-simple-functions">Composition is Not Just for Simple Functions</h1>
<p>Assume <code>square</code> is of type <code>Int -> Int</code> and <code>cube</code> is of type <code>Int -> Int</code>, then you can write:</p>
<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"> power6 <span class="fu">=</span> cube <span class="fu">.</span> square</code></pre></div>
<p>Neat and simple. Couldn’t have put it better. The “.” there is the compose operator. It put square and cube together to get a new function.</p>
<p>But say you have a function <code>children</code> of type <code>Human -> [Human]</code>?</p>
<p>How will you write a function that gives a person’s grandchildren? You have to go through all kinds of trouble just to say what you would have said in three words in English - children of children.</p>
<p>Even in a good functional language like Scheme, you would have to say:</p>
<div class="sourceCode"><pre class="sourceCode scheme"><code class="sourceCode scheme"> (<span class="kw">define</span><span class="fu"> grandchildren </span>(x)
(concat (map children (children x))))</code></pre></div>
<p>That map in there is basically looping over the list of children and getting their children and the concat is putting them all together.</p>
<p>What about great-grandchildren, you ask? Children of children of children, right?</p>
<div class="sourceCode"><pre class="sourceCode scheme"><code class="sourceCode scheme"> (<span class="kw">define</span><span class="fu"> great-grandchildren </span>(x)
(concat (map children (concat (map children (children x))))))</code></pre></div>
<p>or, if you cheat and use grandchildren:</p>
<div class="sourceCode"><pre class="sourceCode scheme"><code class="sourceCode scheme"> (<span class="kw">define</span><span class="fu"> great-grandchildren </span>(x)
(concat (map children (grandchildren x))))</code></pre></div>
<p>We desperately want to say grandchildren are just children of children, but Scheme is not letting us. Can’t we compose children with children? Nope. The types don’t match. <code>children</code> takes a Human and returns a <strong>list</strong> of Humans, so you can’t pass that on to <code>children</code>.</p>
<h1 id="monads-to-the-rescue">Monads to the Rescue</h1>
<p>Here’s how you would write it in Haskell:</p>
<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"> grandChildren <span class="fu">=</span> children <span class="fu"><=<</span> children
greatGrandChildren <span class="fu">=</span> children <span class="fu"><=<</span> children <span class="fu"><=<</span> children</code></pre></div>
<p>What do you say about that!</p>
<p>You can see the similarity to function composition. Just like we used “.” to put square and cube together, we’re using “<=<” here to put children and children together.</p>
<p>The <code>.</code> operator is the way to compose functions that share the same output and input type (respectively).</p>
<p>The <code><=<</code> operator is the way to compose functions that share almost the same output and input type - just that for one, the output is wrapped in some form.</p>
<p>We call these monadic functions. For <code>children</code>, the output was wrapped in a list (<code>[Human]</code>).</p>
<p>We can pull the same trick with lots of functions with lots of different kinds of wrappings.</p>
<p>(Note: I’m being loose in my descriptions here. Just use the “wrapping” analogy as a jumping board for now.)</p>
<h1 id="call-me-maybe">Call Me Maybe</h1>
<p>For example, you have a function that usually works but may fail for some input. Like, say, <code>sqrt</code>. It takes an <code>Int</code> and returns another <code>Int</code>, but will fail on negative input.</p>
<p>So, we represent that output as a <code>Maybe Int</code>. It can either be <code>Just Int</code> (<code>sqrt 16 = Just 4</code>) or it can be <code>Nothing</code> (<code>sqrt -3924 = Nothing</code>). Nothing is basically our <code>null</code>.</p>
<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"><span class="ot"> sqrt ::</span> <span class="dt">Int</span> <span class="ot">-></span> <span class="dt">Maybe</span> <span class="dt">Int</span></code></pre></div>
<p>How can we write safe code using sqrt? For example, how would you write <code>x^(1/4)</code> using sqrt? In (pseudo) Java:</p>
<div class="sourceCode"><pre class="sourceCode java"><code class="sourceCode java"> Integer <span class="fu">fourthRoot</span>(Integer x) {
<span class="co">// sqrt assumes that its input is non-null.</span>
<span class="kw">if</span> (x == <span class="kw">null</span>)
<span class="kw">return</span> <span class="kw">null</span>;
Integer y = <span class="fu">sqrt</span>(x);
<span class="kw">if</span> (y == <span class="kw">null</span>)
<span class="kw">return</span> <span class="kw">null</span>
<span class="kw">return</span> <span class="fu">sqrt</span>(y);
}</code></pre></div>
<p>But, <code>x^(1/4)</code> is just sqrt of sqrt. We don’t want to do all that unnecessary null-checking. If anything is null along the way, the whole answer is null. Obvious! Why make me write it out by hand every time?</p>
<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"> fourthRoot <span class="fu">=</span> sqrt <span class="fu"><=<</span> sqrt</code></pre></div>
<p>Here, <code><=<</code> let us compose two functions of <code>Int -> Maybe Int</code> to get a new function of <code>Int -> Maybe Int</code>.</p>
<p>Similarly, if you wanted to find some integer in a list and then take its square root. <code>find</code> can fail too - there may not be any matching element in the list. So, simplifying a bit, it’s type is <code>[Int] -> Maybe Int</code>.</p>
<p>This means we can’t compose <code>sqrt</code> and <code>find</code>. If they could never fail then we could just do <code>sqrt . find</code>. Done. Do <code>find</code> first and then do <code>sqrt</code> on what you find. Piece of cake. But, nope. They can fail so their types aren’t compatible for function composition.</p>
<div class="sourceCode"><pre class="sourceCode java"><code class="sourceCode java"> Integer <span class="fu">findAndSqrt</span>(List<Integer> xs) {
<span class="co">// findSomeElem expects non-null input.</span>
<span class="kw">if</span> (xs == <span class="kw">null</span>)
<span class="kw">return</span> <span class="kw">null</span>;
Integer y = <span class="fu">findSomeElem</span>(xs);
<span class="kw">if</span> (y == <span class="kw">null</span>) {
<span class="kw">return</span> <span class="kw">null</span>;
}
<span class="kw">return</span> <span class="fu">sqrt</span>(y);
}</code></pre></div>
<p>Again that nasty null-checking. No more.</p>
<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"> findAndSqrt <span class="fu">=</span> sqrt <span class="fu"><=<</span> findSomeElem</code></pre></div>
<p>We can scale this up to an arbitrary number of functions.</p>
<div class="sourceCode"><pre class="sourceCode haskell"><code class="sourceCode haskell"> doComplicatedProcessing <span class="fu">=</span> getAge <span class="fu"><=<</span> getFatherDetails <span class="fu"><=<</span> lookupPersonIdInDatabase <span class="fu"><=<</span> findMatchingId</code></pre></div>
<p>Each of those functions could return null. But, at no point did we have to stop thinking about our logic and go do some stupid null-checking. <code><=<</code> let us do our job and just let us compose potentially failing functions elegantly.</p>
<p>There are tons of other applications for <code><=<</code>. Anywhere you have functions that return “wrapped” values and you want to compose them, you can <code><=<</code>.</p>
<p>Just like with normal function composition, we were able to put together a whole bunch of functions into one final function and do it with ease.</p>
<p>Ok. So we can compose normal functions, and we can compose wrapping functions (<a href>monadic</a> functions, in other words). Is that all?</p>
<h1 id="monoids">Monoids</h1>
<p>Let’s look at list concatenation. <code>l1 ++ l2</code> means appending l2 to l1.</p>
<pre><code>[1, 2] ++ [3, 4, 5] = [1, 2, 3, 4, 5]
[1, 2] ++ [3, 4, 5] ++ [6, 7] = [1, 2, 3, 4, 5, 6, 7]
= ([1, 2] ++ [3, 4, 5]) ++ [6, 7]
= [1, 2] ++ ([3, 4, 5] ++ [6, 7])</code></pre>
<p>All that to say that list concatenation is associative. The order in which you do those individual concatenations doesn’t change the result. Big deal. Right?</p>
<p>Also, the empty list concatenated to the left or right of any list just gives the same list back. Yo, that’s just another way of saying that <code>++</code> has a left and right identity.</p>
<p>Breaking news. So what?</p>
<p>The point is that even after putting together a lot of lists, you get one list in the end. You don’t have to worry about all the individual details. Put them together and now you’ve got one list to represent them all. You can even put this list together with other lists and still get a list back.</p>
<p>The complexity doesn’t rise up as you put together many lists. It says absolutely flat throughout.</p>
<p>The above properties don’t just hold for lists and strings. They hold for numbers too, under addition and multiplication.</p>
<p>They hold for functions that have the same input and output type. Gabriel gives the example of Plugins. You can think of a plugin for some application to be of type (Request -> Data). It takes some request and returns the desired data.</p>
<h1 id="functions-as-monoids">Functions as Monoids</h1>
<p>Say you’re writing a search aggregator for some company. The idea is that employees will enter a phrase and you will bring in search results from the different parts of that company - say HR, manufacturing, marketing, whatever. All of these parts have their own customized search facility - manufacturing lets you search within their orders, marketing lets you search within their records, whatever. You need to bring all of that to one interface in front of the user.</p>
<p>At first, you decide to support searching just one department - the Software Engineering department. Easier to test your aggregator with just one search backend.</p>
<p>You write a function <code>getSWEnggSearchResult</code> of type <code>Search -> SearchResult</code>. The <code>SearchResult</code> is some properly-formatted thing that you can display directly. You don’t need to know what is inside it. It has a “convertToHTML” method, so to speak, and you can just use that.</p>
<p>Cool. It works! All your hours of coding and debugging have paid off. Ok. Now, you need to add more backends.</p>
<p>You decide to add one more - HR Department. So, you write a function <code>getHRSearchResult</code> of type <code>Search -> SearchResult</code>. And, in your main function, you first call <code>getSWEnggSearchResult</code> and insert its HTML output into your page. Then, you call <code>getHRSearchResult</code> and insert its HTML output into your page.</p>
<p>That works too! Then, you go ahead and do this for every single other goddamn department in your company. The main function balloons up with all kinds of <code>getFooSearchResults</code>.</p>
<p>Then, next month, the company merges with another company. You get 10 more departments whose search backends you have to support. Then, at the end of the year, that company is sold off to some other company - so you now need to split off your application into two - one that supports your company’s backends and one that supports theirs. You hand that over to them. And, so it goes on.</p>
<h1 id="keeping-the-complexity-low">Keeping the Complexity Low</h1>
<p>What could you have done differently?</p>
<p>You say that the type of <code>Backend</code> is <code>Search -> SearchResult</code>. If <code>SearchResult</code> is a Monoid (which it seems to be), then <code>Search -> SearchResult</code> will automatically be a Monoid. We can easily compose all these Backends together.</p>
<p>I will use the <code><></code> sign to show appending of two Monoids.</p>
<p>We will call it <code>SWEnggBackend</code> instead of <code>getSWEnggSearchResult</code>.</p>
<p>So, initially:</p>
<pre><code>backend = SWEnggBackend</code></pre>
<p>Then, you added the HR backend.</p>
<pre><code>backend = SWEnggBackend <> HRBackend</code></pre>
<p>What this does is create a <strong>composite function</strong> that takes a Search and passes it to both the backends. It then takes the results and appends them together (because SearchResult is a Monoid).</p>
<p>This means that from the point of view of the program, there is only <strong>one</strong> backend. You can add as many as you want, it will all look just like one backend, a simple Monoid of type (Search -> SearchResult). This will hold up even when the company merges with another.</p>
<pre><code>ourBackend = SWEnggBackend <> HRBackend <> ...
theirBackend = FooBackend <> BarBackend <> ...
backend = ourBackend <> theirBackend</code></pre>
<p>No part of your program has to change with all the other changes. You don’t have to add the complexity of having a list of backends and then processing them manually. In fact, each of those backends could themselves encompass several other backends about which you need know nothing.</p>
<p>To your program, there is just one backend. At each point, you’re dealing with just <strong>one</strong> composite backend. The code complexity of your program stays constant no matter how many backends you add.</p>
<hr />
<p>This is just the tip of the iceberg with category theory. There’s still free monads, coyoneda (free functor), monad transformers, adjoints, and all this other neat stuff that helps you tame the complexity of your code.</p>
<h1 id="notes">Notes</h1>
<ul>
<li><p>Thanks to <a href="http://www.haskellforall.com/">Gabriel Gonsalez</a>’s brilliant blog posts for getting me fired up about Category Theory. All I know about Compositional Programming, I learnt from him.</p></li>
<li><p>The <code>greatGrandChildren</code> example is from Gabriel’s <a href="http://www.haskellforall.com/2012/08/the-category-design-pattern.html">Category Design Pattern</a> post.</p></li>
<li><p>Learn You A Haskell has a <a href="http://learnyouahaskell.com/a-fistful-of-monads">great example</a> of the common Knight-Move interview problem, where they give you <code>knightMove</code> and ask for <code>knightMoveThrice</code>. (Hint: It’s the exact problem as <code>greatGrandChildren</code>)</p></li>
</ul>
<div class="info">Created: December 20, 2014</div>
<div class="info">Last modified: November 5, 2016</div>
<div class="info">Status: finished</div>
<div class="info"><b>Tags</b>: category theory, thinking</div>
<br />
<div id="disqus_thread"></div>
<script type="text/javascript">
/* * * CONFIGURATION VARIABLES: EDIT BEFORE PASTING INTO YOUR WEBPAGE * * */
var disqus_shortname = 'spkrationalitytrainingground'; // required: replace example with your forum shortname
var disqus_identifier = '/Why-Category-Theory.html';
var disqus_title = 'Why Category Theory';
/* * * DON'T EDIT BELOW THIS LINE * * */
(function() {
var dsq = document.createElement('script'); dsq.type = 'text/javascript'; dsq.async = true;
dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
(document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
})();
</script>
<script type="text/javascript" src="https://fast.fonts.net/jsapi/f7f47a40-b25b-44ee-9f9c-cfdfc8bb2741.js"></script>
<noscript>Please enable JavaScript to view the <a href="http://disqus.com/?ref_noscript">comments powered by Disqus.</a></noscript>
<a href="http://disqus.com" class="dsq-brlink">comments powered by <span class="logo-disqus">Disqus</span></a>
</div>
<div id="footer">
Site proudly generated by
<a href="http://jaspervdj.be/hakyll">Hakyll</a>
</div>
</body>
</html>