Mercurial > dylan

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