Mercurial > dylan

annotate categorical/monad.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>Monads in CS and Math</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-11 03:07:07 EDT"/>
rlm@2 11 <meta name="author" content="Robert McIntyre"/>
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 <script type="text/javascript">
rlm@2 58 <!--/*--><![CDATA[/*><!--*/
rlm@2 59 function CodeHighlightOn(elem, id)
rlm@2 60 {
rlm@2 61 var target = document.getElementById(id);
rlm@2 62 if(null != target) {
rlm@2 63 elem.cacheClassElem = elem.className;
rlm@2 64 elem.cacheClassTarget = target.className;
rlm@2 65 target.className = "code-highlighted";
rlm@2 66 elem.className = "code-highlighted";
rlm@2 67 }
rlm@2 68 }
rlm@2 69 function CodeHighlightOff(elem, id)
rlm@2 70 {
rlm@2 71 var target = document.getElementById(id);
rlm@2 72 if(elem.cacheClassElem)
rlm@2 73 elem.className = elem.cacheClassElem;
rlm@2 74 if(elem.cacheClassTarget)
rlm@2 75 target.className = elem.cacheClassTarget;
rlm@2 76 }
rlm@2 77 /*]]>*///-->
rlm@2 78 </script>
rlm@2 79 <script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js">
rlm@2 80 <!--/*--><![CDATA[/*><!--*/
rlm@2 81 MathJax.Hub.Config({
rlm@2 82 // Only one of the two following lines, depending on user settings
rlm@2 83 // First allows browser-native MathML display, second forces HTML/CSS
rlm@2 84 // config: ["MMLorHTML.js"], jax: ["input/TeX"],
rlm@2 85 jax: ["input/TeX", "output/HTML-CSS"],
rlm@2 86 extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js",
rlm@2 87 "TeX/noUndefined.js"],
rlm@2 88 tex2jax: {
rlm@2 89 inlineMath: [ ["\\(","\\)"] ],
rlm@2 90 displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ],
rlm@2 91 skipTags: ["script","noscript","style","textarea","pre","code"],
rlm@2 92 ignoreClass: "tex2jax_ignore",
rlm@2 93 processEscapes: false,
rlm@2 94 processEnvironments: true,
rlm@2 95 preview: "TeX"
rlm@2 96 },
rlm@2 97 showProcessingMessages: true,
rlm@2 98 displayAlign: "center",
rlm@2 99 displayIndent: "2em",
rlm@2 100
rlm@2 101 "HTML-CSS": {
rlm@2 102 scale: 100,
rlm@2 103 availableFonts: ["STIX","TeX"],
rlm@2 104 preferredFont: "TeX",
rlm@2 105 webFont: "TeX",
rlm@2 106 imageFont: "TeX",
rlm@2 107 showMathMenu: true,
rlm@2 108 },
rlm@2 109 MMLorHTML: {
rlm@2 110 prefer: {
rlm@2 111 MSIE: "MML",
rlm@2 112 Firefox: "MML",
rlm@2 113 Opera: "HTML",
rlm@2 114 other: "HTML"
rlm@2 115 }
rlm@2 116 }
rlm@2 117 });
rlm@2 118 /*]]>*///-->
rlm@2 119 </script>
rlm@2 120 </head>
rlm@2 121 <body>
rlm@2 122 <div id="content">
rlm@2 123
rlm@2 124
rlm@2 125
rlm@2 126 <h1>
rlm@2 127 Monads in CS and Math
rlm@2 128 </h1>
rlm@2 129
rlm@2 130 <p>
rlm@2 131 The purpose of a <i>monad</i> is to introduce a new data type into your
rlm@2 132 language and to integrate it with existing types; a monad augments a
rlm@2 133 pre-existing data type \(A\), creating a new type \(B\).
rlm@2 134 </p>
rlm@2 135 <p>
rlm@2 136 When describing monads, I will use the following terminology:
rlm@2 137 </p><ul>
rlm@2 138 <li>Values of type \(A\) are called <b>ordinary values</b>, because they belong
rlm@2 139 to the pre-existing data type.
rlm@2 140 </li>
rlm@2 141 <li>Values of type \(B\) are called <b>monadic values</b>, because they
rlm@2 142 belong to the type introduced by the monad.
rlm@2 143 </li>
rlm@2 144 <li>A function \(A\rightarrow B\) is called a <b>monadic function</b>; such
rlm@2 145 functions accept regular values as input and return monadic values.
rlm@2 146 </li>
rlm@2 147 </ul>
rlm@2 148
rlm@2 149
rlm@2 150 <p>
rlm@2 151 A monad consists of
rlm@2 152 two components for achieving this purpose:
rlm@2 153 </p>
rlm@2 154 <dl>
rlm@2 155 <dt>A function that converts ordinary values into monadic values</dt><dd>
rlm@2 156 <p>
rlm@2 157 First, in order to create a new data type, each monad has an
rlm@2 158 <i>upgrade function</i> which systematically adds structure to values of
rlm@2 159 the existing data type, \(A\). Because the upgrade function produces
rlm@2 160 enhanced values in a systematic way, the enhanced values constitute
rlm@2 161 a sort of new data type, \(B\).
rlm@2 162 </p></dd>
rlm@2 163 </dl>
rlm@2 164
rlm@2 165
rlm@2 166 <blockquote>
rlm@2 167
rlm@2 168
rlm@2 169 \(\text{upgrade}:A\rightarrow B\)
rlm@2 170
rlm@2 171 </blockquote>
rlm@2 172
rlm@2 173
rlm@2 174 <dl>
rlm@2 175 <dt>A function that enables monadic functions to accept monadic values</dt><dd>Second, each monad has a <i>pipe function</i> which is a
rlm@2 176 protocol for combining a monadic function and a monadic value to
rlm@2 177 produce a monadic value. The pipe function facilitates composition:
rlm@2 178 notice that a collection of monadic functions \(A\rightarrow B\) is composable only if they have been modified by the
rlm@2 179 pipe function to become functions of type \(B\rightarrow B\), otherwise their input and output types do not match.
rlm@2 180 </dd>
rlm@2 181 </dl>
rlm@2 182
rlm@2 183 <blockquote>
rlm@2 184
rlm@2 185
rlm@2 186 \(\text{pipe}:B\times B^A\rightarrow B\)
rlm@2 187
rlm@2 188 </blockquote>
rlm@2 189
rlm@2 190
rlm@2 191
rlm@2 192
rlm@2 193
rlm@2 194
rlm@2 195 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.monad)
rlm@2 196
rlm@2 197 </pre>
rlm@2 198
rlm@2 199
rlm@2 200
rlm@2 201
rlm@2 202
rlm@2 203 <div id="table-of-contents">
rlm@2 204 <h2>Table of Contents</h2>
rlm@2 205 <div id="text-table-of-contents">
rlm@2 206 <ul>
rlm@2 207 <li><a href="#sec-1">1 Examples of monads </a>
rlm@2 208 <ul>
rlm@2 209 <li><a href="#sec-1-1">1.1 The nondeterministic monad </a></li>
rlm@2 210 </ul>
rlm@2 211 </li>
rlm@2 212 </ul>
rlm@2 213 </div>
rlm@2 214 </div>
rlm@2 215
rlm@2 216 <div id="outline-container-1" class="outline-2">
rlm@2 217 <h2 id="sec-1"><span class="section-number-2">1</span> Examples of monads </h2>
rlm@2 218 <div class="outline-text-2" id="text-1">
rlm@2 219
rlm@2 220
rlm@2 221 </div>
rlm@2 222
rlm@2 223 <div id="outline-container-1-1" class="outline-3">
rlm@2 224 <h3 id="sec-1-1"><span class="section-number-3">1.1</span> The nondeterministic monad </h3>
rlm@2 225 <div class="outline-text-3" id="text-1-1">
rlm@2 226
rlm@2 227
rlm@2 228 <p>
rlm@2 229 We'll implement nondeterministic programming by defining a monad <code>amb</code>
rlm@2 230 that transforms ordinary deterministic functions into functions that ``ambiguously'' return zero or more
rlm@2 231 values.
rlm@2 232 </p>
rlm@2 233
rlm@2 234
rlm@2 235
rlm@2 236 <pre class="src src-clojure"></pre>
rlm@2 237
rlm@2 238
rlm@2 239
rlm@2 240 </div>
rlm@2 241 </div>
rlm@2 242 </div>
rlm@2 243 <div id="postamble">
rlm@2 244 <p class="date">Date: 2011-07-11 03:07:07 EDT</p>
rlm@2 245 <p class="author">Author: Robert McIntyre</p>
rlm@2 246 <p class="creator">Org version 7.6 with Emacs version 23</p>
rlm@2 247 <a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a>
rlm@2 248 </div>
rlm@2 249 </div>
rlm@2 250 </body>
rlm@2 251 </html>