Mercurial > dylan

     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>
author	Robert McIntyre <rlm@mit.edu>
date	Fri, 28 Oct 2011 00:06:37 -0700
parents	b4de894a1e2e
children