Mercurial > dylan

comparison categorical/morphisms.html @ 2:b4de894a1e2e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial import
author Robert McIntyre <rlm@mit.edu>
date Fri, 28 Oct 2011 00:03:05 -0700
parents
children
comparison
equal deleted inserted replaced
1:8d8278e09888 2:b4de894a1e2e
1 <?xml version="1.0" encoding="iso-8859-1"?>
2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
3 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
4 <html xmlns="http://www.w3.org/1999/xhtml"
5 lang="en" xml:lang="en">
6 <head>
7 <title>Categorical Programs</title>
8 <meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"/>
9 <meta name="generator" content="Org-mode"/>
10 <meta name="generated" content="2011-07-01 12:28:39 CDT"/>
11 <meta name="author" content="Dylan Holmes"/>
12 <meta name="description" content=""/>
13 <meta name="keywords" content=""/>
14 <style type="text/css">
15 <!--/*--><![CDATA[/*><!--*/
16 html { font-family: Times, serif; font-size: 12pt; }
17 .title { text-align: center; }
18 .todo { color: red; }
19 .done { color: green; }
20 .tag { background-color: #add8e6; font-weight:normal }
21 .target { }
22 .timestamp { color: #bebebe; }
23 .timestamp-kwd { color: #5f9ea0; }
24 .right {margin-left:auto; margin-right:0px; text-align:right;}
25 .left {margin-left:0px; margin-right:auto; text-align:left;}
26 .center {margin-left:auto; margin-right:auto; text-align:center;}
27 p.verse { margin-left: 3% }
28 pre {
29 border: 1pt solid #AEBDCC;
30 background-color: #F3F5F7;
31 padding: 5pt;
32 font-family: courier, monospace;
33 font-size: 90%;
34 overflow:auto;
35 }
36 table { border-collapse: collapse; }
37 td, th { vertical-align: top; }
38 th.right { text-align:center; }
39 th.left { text-align:center; }
40 th.center { text-align:center; }
41 td.right { text-align:right; }
42 td.left { text-align:left; }
43 td.center { text-align:center; }
44 dt { font-weight: bold; }
45 div.figure { padding: 0.5em; }
46 div.figure p { text-align: center; }
47 textarea { overflow-x: auto; }
48 .linenr { font-size:smaller }
49 .code-highlighted {background-color:#ffff00;}
50 .org-info-js_info-navigation { border-style:none; }
51 #org-info-js_console-label { font-size:10px; font-weight:bold;
52 white-space:nowrap; }
53 .org-info-js_search-highlight {background-color:#ffff00; color:#000000;
54 font-weight:bold; }
55 /*]]>*/-->
56 </style>
57 <link rel="stylesheet" type="text/css" href="../css/aurellem.css" />
58 <script type="text/javascript">
59 <!--/*--><![CDATA[/*><!--*/
60 function CodeHighlightOn(elem, id)
61 {
62 var target = document.getElementById(id);
63 if(null != target) {
64 elem.cacheClassElem = elem.className;
65 elem.cacheClassTarget = target.className;
66 target.className = "code-highlighted";
67 elem.className = "code-highlighted";
68 }
69 }
70 function CodeHighlightOff(elem, id)
71 {
72 var target = document.getElementById(id);
73 if(elem.cacheClassElem)
74 elem.className = elem.cacheClassElem;
75 if(elem.cacheClassTarget)
76 target.className = elem.cacheClassTarget;
77 }
78 /*]]>*///-->
79 </script>
80 <script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js">
81 <!--/*--><![CDATA[/*><!--*/
82 MathJax.Hub.Config({
83 // Only one of the two following lines, depending on user settings
84 // First allows browser-native MathML display, second forces HTML/CSS
85 // config: ["MMLorHTML.js"], jax: ["input/TeX"],
86 jax: ["input/TeX", "output/HTML-CSS"],
87 extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js",
88 "TeX/noUndefined.js"],
89 tex2jax: {
90 inlineMath: [ ["\\(","\\)"] ],
91 displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ],
92 skipTags: ["script","noscript","style","textarea","pre","code"],
93 ignoreClass: "tex2jax_ignore",
94 processEscapes: false,
95 processEnvironments: true,
96 preview: "TeX"
97 },
98 showProcessingMessages: true,
99 displayAlign: "center",
100 displayIndent: "2em",
101
102 "HTML-CSS": {
103 scale: 100,
104 availableFonts: ["STIX","TeX"],
105 preferredFont: "TeX",
106 webFont: "TeX",
107 imageFont: "TeX",
108 showMathMenu: true,
109 },
110 MMLorHTML: {
111 prefer: {
112 MSIE: "MML",
113 Firefox: "MML",
114 Opera: "HTML",
115 other: "HTML"
116 }
117 }
118 });
119 /*]]>*///-->
120 </script>
121 </head>
122 <body>
123 <div id="content">
124
125
126
127
128
129 <h1>Categorical Programs</h1>
130
131
132 <div id="table-of-contents">
133 <h2>Table of Contents</h2>
134 <div id="text-table-of-contents">
135 <ul>
136 <li><a href="#sec-1">1 The Category of Types </a>
137 <ul>
138 <li><a href="#sec-1-1">1.1 Building new data types out of existing ones </a></li>
139 </ul>
140 </li>
141 </ul>
142 </div>
143 </div>
144
145 <div id="outline-container-1" class="outline-2">
146 <h2 id="sec-1"><span class="section-number-2">1</span> The Category of Types </h2>
147 <div class="outline-text-2" id="text-1">
148
149 <p>Every computer language with data types (such as Integers,
150 Floats, or
151 Strings) corresponds with a certain category; the objects of the category are the data types
152 of the language, and there is one arrow between data types \(A\) and \(B\)
153 for every function in the language whose argument has type \(A\) and whose return value
154 has type \(B\).
155 </p>
156
157
158
159 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.morphisms)
160
161 </pre>
162
163
164
165
166
167 </div>
168
169 <div id="outline-container-1-1" class="outline-3">
170 <h3 id="sec-1-1"><span class="section-number-3">1.1</span> Building new data types out of existing ones </h3>
171 <div class="outline-text-3" id="text-1-1">
172
173
174 <p>
175 We will now discuss two processes which combine existing
176 data types to yield composite data types. These higher-order processes will be
177 <i>functorial</i>, which means that they will recombine not only the objects of
178 our category (the data types), but the arrows as well (functions with
179 typed input and output).
180 </p>
181 <p>
182 The <code>product</code> functor combines two data types, \(A\) and \(B\), producing
183 a new type, denoted \(A\times B\). Conceptually, values with the data type \(A\times
184 B\) have two components, the first of which is a value of type \(A\), the
185 second of which is a value of type \(B\). Concretely, the data type \(A\times B\)
186 can be implemented as pairs of values, the first of which is
187 of type \(A\) and the second of which is of type \(B\). With this
188 implementation in mind, you can see that the type \(A\) and type \(B\)
189 constituents of type \(A\times B\) value can be recovered; the so-called
190 projection functors <code>first</code> and <code>second</code> recover them. A third
191 functor, the <code>diagonal</code> functor, completes our toolkit; given
192 value \(a\) of type \(A\), it produces the value \((a,a)\) of type \(A\times A\).
193 </p>
194
195
196
197 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">product</span>[a b] (<span style="color: #8cd0d3;">list</span> a b))
198 (<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">projections</span> (<span style="color: #8cd0d3;">list</span> first second))
199 (<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">diagonal</span>[a] (product a a))
200
201 </pre>
202
203
204
205
206 <p>
207 The <code>coproduct</code> functor combines two data types, \(A\) and \(B\),
208 producing a new type, denoted \(A+B\). Conceptually, you construct the
209 \(A+B\) datatype by creating labelled versions of the data types \(A\) and
210 \(B\) &mdash; we'll call them black-\(A\) and white-\(B\) &mdash; and
211 then creating a data type \(A+B\) which contains all the black-\(A\)
212 values and all the white-\(B\) values. Concretely, you can implement the
213 \(A+B\) data type using label-value pairs: the first value in the pair
214 is either the label `black' or the label `white'; the second
215 value must have type \(A\) if the label is black, or type \(B\) if the
216 label is white.
217 </p>
218 <p>
219 Now, the <code>product</code> functor came with projection functors <code>first</code>
220 and <code>second</code> that take \(A\times B\) values and return (respectively) \(A\) values and
221 \(B\) values. The <code>coproduct</code> functor, conversely, comes with two
222 injection functors <code>make-black</code> and <code>make-white</code> that perform the
223 opposite function: they take (respectively) \(A\) values and \(B\) values,
224 promoting them to the \(A+B\) datatype by making the \(A\)'s into
225 black-\(A\)'s and the \(B\)'s into white-\(B\)'s.
226 </p>
227
228
229 </div>
230 </div>
231 </div>
232 <div id="postamble">
233 <p class="date">Date: 2011-07-01 12:28:39 CDT</p>
234 <p class="author">Author: Dylan Holmes</p>
235 <p class="creator">Org version 7.5 with Emacs version 23</p>
236 <a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a>
237 </div>
238 </div>
239 </body>
240 </html>