Mercurial > dylan

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