Mercurial > dylan
diff categorical/morphisms.html @ 2:b4de894a1e2e
initial import
| author | Robert McIntyre <rlm@mit.edu> |
|---|---|
| date | Fri, 28 Oct 2011 00:03:05 -0700 |
| parents | |
| children |
line wrap: on
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/categorical/morphisms.html Fri Oct 28 00:03:05 2011 -0700 1.3 @@ -0,0 +1,240 @@ 1.4 +<?xml version="1.0" encoding="iso-8859-1"?> 1.5 +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 1.6 + "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> 1.7 +<html xmlns="http://www.w3.org/1999/xhtml" 1.8 +lang="en" xml:lang="en"> 1.9 +<head> 1.10 +<title>Categorical Programs</title> 1.11 +<meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1"/> 1.12 +<meta name="generator" content="Org-mode"/> 1.13 +<meta name="generated" content="2011-07-01 12:28:39 CDT"/> 1.14 +<meta name="author" content="Dylan Holmes"/> 1.15 +<meta name="description" content=""/> 1.16 +<meta name="keywords" content=""/> 1.17 +<style type="text/css"> 1.18 + <!--/*--><![CDATA[/*><!--*/ 1.19 + html { font-family: Times, serif; font-size: 12pt; } 1.20 + .title { text-align: center; } 1.21 + .todo { color: red; } 1.22 + .done { color: green; } 1.23 + .tag { background-color: #add8e6; font-weight:normal } 1.24 + .target { } 1.25 + .timestamp { color: #bebebe; } 1.26 + .timestamp-kwd { color: #5f9ea0; } 1.27 + .right {margin-left:auto; margin-right:0px; text-align:right;} 1.28 + .left {margin-left:0px; margin-right:auto; text-align:left;} 1.29 + .center {margin-left:auto; margin-right:auto; text-align:center;} 1.30 + p.verse { margin-left: 3% } 1.31 + pre { 1.32 + border: 1pt solid #AEBDCC; 1.33 + background-color: #F3F5F7; 1.34 + padding: 5pt; 1.35 + font-family: courier, monospace; 1.36 + font-size: 90%; 1.37 + overflow:auto; 1.38 + } 1.39 + table { border-collapse: collapse; } 1.40 + td, th { vertical-align: top; } 1.41 + th.right { text-align:center; } 1.42 + th.left { text-align:center; } 1.43 + th.center { text-align:center; } 1.44 + td.right { text-align:right; } 1.45 + td.left { text-align:left; } 1.46 + td.center { text-align:center; } 1.47 + dt { font-weight: bold; } 1.48 + div.figure { padding: 0.5em; } 1.49 + div.figure p { text-align: center; } 1.50 + textarea { overflow-x: auto; } 1.51 + .linenr { font-size:smaller } 1.52 + .code-highlighted {background-color:#ffff00;} 1.53 + .org-info-js_info-navigation { border-style:none; } 1.54 + #org-info-js_console-label { font-size:10px; font-weight:bold; 1.55 + white-space:nowrap; } 1.56 + .org-info-js_search-highlight {background-color:#ffff00; color:#000000; 1.57 + font-weight:bold; } 1.58 + /*]]>*/--> 1.59 +</style> 1.60 +<link rel="stylesheet" type="text/css" href="../css/aurellem.css" /> 1.61 +<script type="text/javascript"> 1.62 +<!--/*--><![CDATA[/*><!--*/ 1.63 + function CodeHighlightOn(elem, id) 1.64 + { 1.65 + var target = document.getElementById(id); 1.66 + if(null != target) { 1.67 + elem.cacheClassElem = elem.className; 1.68 + elem.cacheClassTarget = target.className; 1.69 + target.className = "code-highlighted"; 1.70 + elem.className = "code-highlighted"; 1.71 + } 1.72 + } 1.73 + function CodeHighlightOff(elem, id) 1.74 + { 1.75 + var target = document.getElementById(id); 1.76 + if(elem.cacheClassElem) 1.77 + elem.className = elem.cacheClassElem; 1.78 + if(elem.cacheClassTarget) 1.79 + target.className = elem.cacheClassTarget; 1.80 + } 1.81 +/*]]>*///--> 1.82 +</script> 1.83 +<script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js"> 1.84 +<!--/*--><![CDATA[/*><!--*/ 1.85 + MathJax.Hub.Config({ 1.86 + // Only one of the two following lines, depending on user settings 1.87 + // First allows browser-native MathML display, second forces HTML/CSS 1.88 + // config: ["MMLorHTML.js"], jax: ["input/TeX"], 1.89 + jax: ["input/TeX", "output/HTML-CSS"], 1.90 + extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js", 1.91 + "TeX/noUndefined.js"], 1.92 + tex2jax: { 1.93 + inlineMath: [ ["\\(","\\)"] ], 1.94 + displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ], 1.95 + skipTags: ["script","noscript","style","textarea","pre","code"], 1.96 + ignoreClass: "tex2jax_ignore", 1.97 + processEscapes: false, 1.98 + processEnvironments: true, 1.99 + preview: "TeX" 1.100 + }, 1.101 + showProcessingMessages: true, 1.102 + displayAlign: "center", 1.103 + displayIndent: "2em", 1.104 + 1.105 + "HTML-CSS": { 1.106 + scale: 100, 1.107 + availableFonts: ["STIX","TeX"], 1.108 + preferredFont: "TeX", 1.109 + webFont: "TeX", 1.110 + imageFont: "TeX", 1.111 + showMathMenu: true, 1.112 + }, 1.113 + MMLorHTML: { 1.114 + prefer: { 1.115 + MSIE: "MML", 1.116 + Firefox: "MML", 1.117 + Opera: "HTML", 1.118 + other: "HTML" 1.119 + } 1.120 + } 1.121 + }); 1.122 +/*]]>*///--> 1.123 +</script> 1.124 +</head> 1.125 +<body> 1.126 +<div id="content"> 1.127 + 1.128 + 1.129 + 1.130 + 1.131 + 1.132 +<h1>Categorical Programs</h1> 1.133 + 1.134 + 1.135 +<div id="table-of-contents"> 1.136 +<h2>Table of Contents</h2> 1.137 +<div id="text-table-of-contents"> 1.138 +<ul> 1.139 +<li><a href="#sec-1">1 The Category of Types </a> 1.140 +<ul> 1.141 +<li><a href="#sec-1-1">1.1 Building new data types out of existing ones </a></li> 1.142 +</ul> 1.143 +</li> 1.144 +</ul> 1.145 +</div> 1.146 +</div> 1.147 + 1.148 +<div id="outline-container-1" class="outline-2"> 1.149 +<h2 id="sec-1"><span class="section-number-2">1</span> The Category of Types </h2> 1.150 +<div class="outline-text-2" id="text-1"> 1.151 + 1.152 +<p>Every computer language with data types (such as Integers, 1.153 +Floats, or 1.154 +Strings) corresponds with a certain category; the objects of the category are the data types 1.155 +of the language, and there is one arrow between data types \(A\) and \(B\) 1.156 +for every function in the language whose argument has type \(A\) and whose return value 1.157 +has type \(B\). 1.158 +</p> 1.159 + 1.160 + 1.161 + 1.162 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.morphisms) 1.163 + 1.164 +</pre> 1.165 + 1.166 + 1.167 + 1.168 + 1.169 + 1.170 +</div> 1.171 + 1.172 +<div id="outline-container-1-1" class="outline-3"> 1.173 +<h3 id="sec-1-1"><span class="section-number-3">1.1</span> Building new data types out of existing ones </h3> 1.174 +<div class="outline-text-3" id="text-1-1"> 1.175 + 1.176 + 1.177 +<p> 1.178 +We will now discuss two processes which combine existing 1.179 +data types to yield composite data types. These higher-order processes will be 1.180 +<i>functorial</i>, which means that they will recombine not only the objects of 1.181 +our category (the data types), but the arrows as well (functions with 1.182 +typed input and output). 1.183 +</p> 1.184 +<p> 1.185 +The <code>product</code> functor combines two data types, \(A\) and \(B\), producing 1.186 +a new type, denoted \(A\times B\). Conceptually, values with the data type \(A\times 1.187 +B\) have two components, the first of which is a value of type \(A\), the 1.188 +second of which is a value of type \(B\). Concretely, the data type \(A\times B\) 1.189 +can be implemented as pairs of values, the first of which is 1.190 +of type \(A\) and the second of which is of type \(B\). With this 1.191 +implementation in mind, you can see that the type \(A\) and type \(B\) 1.192 +constituents of type \(A\times B\) value can be recovered; the so-called 1.193 +projection functors <code>first</code> and <code>second</code> recover them. A third 1.194 +functor, the <code>diagonal</code> functor, completes our toolkit; given 1.195 +value \(a\) of type \(A\), it produces the value \((a,a)\) of type \(A\times A\). 1.196 +</p> 1.197 + 1.198 + 1.199 + 1.200 +<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)) 1.201 +(<span style="color: #f0dfaf; font-weight: bold;">def</span> <span style="color: #f0dfaf;">projections</span> (<span style="color: #8cd0d3;">list</span> first second)) 1.202 +(<span style="color: #f0dfaf; font-weight: bold;">defn</span> <span style="color: #f0dfaf;">diagonal</span>[a] (product a a)) 1.203 + 1.204 +</pre> 1.205 + 1.206 + 1.207 + 1.208 + 1.209 +<p> 1.210 +The <code>coproduct</code> functor combines two data types, \(A\) and \(B\), 1.211 +producing a new type, denoted \(A+B\). Conceptually, you construct the 1.212 +\(A+B\) datatype by creating labelled versions of the data types \(A\) and 1.213 +\(B\) — we'll call them black-\(A\) and white-\(B\) — and 1.214 +then creating a data type \(A+B\) which contains all the black-\(A\) 1.215 +values and all the white-\(B\) values. Concretely, you can implement the 1.216 +\(A+B\) data type using label-value pairs: the first value in the pair 1.217 +is either the label `black' or the label `white'; the second 1.218 +value must have type \(A\) if the label is black, or type \(B\) if the 1.219 +label is white. 1.220 +</p> 1.221 +<p> 1.222 +Now, the <code>product</code> functor came with projection functors <code>first</code> 1.223 +and <code>second</code> that take \(A\times B\) values and return (respectively) \(A\) values and 1.224 +\(B\) values. The <code>coproduct</code> functor, conversely, comes with two 1.225 +injection functors <code>make-black</code> and <code>make-white</code> that perform the 1.226 +opposite function: they take (respectively) \(A\) values and \(B\) values, 1.227 +promoting them to the \(A+B\) datatype by making the \(A\)'s into 1.228 +black-\(A\)'s and the \(B\)'s into white-\(B\)'s. 1.229 +</p> 1.230 + 1.231 + 1.232 +</div> 1.233 +</div> 1.234 +</div> 1.235 +<div id="postamble"> 1.236 +<p class="date">Date: 2011-07-01 12:28:39 CDT</p> 1.237 +<p class="author">Author: Dylan Holmes</p> 1.238 +<p class="creator">Org version 7.5 with Emacs version 23</p> 1.239 +<a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a> 1.240 +</div> 1.241 +</div> 1.242 +</body> 1.243 +</html>