view categorical/monad.html @ 8:4dfeaf1a70c0

typos, gender reassignment
author Dylan Holmes <ocsenave@gmail.com>
date Thu, 27 Oct 2011 23:02:59 -0500
parents b4de894a1e2e
children
line wrap: on
line source
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",
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">
126 <h1>
127 Monads in CS and Math
128 </h1>
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>
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>
166 <blockquote>
169 \(\text{upgrade}:A\rightarrow B\)
171 </blockquote>
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>
183 <blockquote>
186 \(\text{pipe}:B\times B^A\rightarrow B\)
188 </blockquote>
195 <pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.monad)
197 </pre>
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>
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">
221 </div>
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">
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>
236 <pre class="src src-clojure"></pre>
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>