Mercurial > dylan
diff categorical/monad.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/monad.html Fri Oct 28 00:03:05 2011 -0700 1.3 @@ -0,0 +1,251 @@ 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>Monads in CS and Math</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-11 03:07:07 EDT"/> 1.14 +<meta name="author" content="Robert McIntyre"/> 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 +<script type="text/javascript"> 1.61 +<!--/*--><![CDATA[/*><!--*/ 1.62 + function CodeHighlightOn(elem, id) 1.63 + { 1.64 + var target = document.getElementById(id); 1.65 + if(null != target) { 1.66 + elem.cacheClassElem = elem.className; 1.67 + elem.cacheClassTarget = target.className; 1.68 + target.className = "code-highlighted"; 1.69 + elem.className = "code-highlighted"; 1.70 + } 1.71 + } 1.72 + function CodeHighlightOff(elem, id) 1.73 + { 1.74 + var target = document.getElementById(id); 1.75 + if(elem.cacheClassElem) 1.76 + elem.className = elem.cacheClassElem; 1.77 + if(elem.cacheClassTarget) 1.78 + target.className = elem.cacheClassTarget; 1.79 + } 1.80 +/*]]>*///--> 1.81 +</script> 1.82 +<script type="text/javascript" src="http://orgmode.org/mathjax/MathJax.js"> 1.83 +<!--/*--><![CDATA[/*><!--*/ 1.84 + MathJax.Hub.Config({ 1.85 + // Only one of the two following lines, depending on user settings 1.86 + // First allows browser-native MathML display, second forces HTML/CSS 1.87 + // config: ["MMLorHTML.js"], jax: ["input/TeX"], 1.88 + jax: ["input/TeX", "output/HTML-CSS"], 1.89 + extensions: ["tex2jax.js","TeX/AMSmath.js","TeX/AMSsymbols.js", 1.90 + "TeX/noUndefined.js"], 1.91 + tex2jax: { 1.92 + inlineMath: [ ["\\(","\\)"] ], 1.93 + displayMath: [ ['$$','$$'], ["\\[","\\]"], ["\\begin{displaymath}","\\end{displaymath}"] ], 1.94 + skipTags: ["script","noscript","style","textarea","pre","code"], 1.95 + ignoreClass: "tex2jax_ignore", 1.96 + processEscapes: false, 1.97 + processEnvironments: true, 1.98 + preview: "TeX" 1.99 + }, 1.100 + showProcessingMessages: true, 1.101 + displayAlign: "center", 1.102 + displayIndent: "2em", 1.103 + 1.104 + "HTML-CSS": { 1.105 + scale: 100, 1.106 + availableFonts: ["STIX","TeX"], 1.107 + preferredFont: "TeX", 1.108 + webFont: "TeX", 1.109 + imageFont: "TeX", 1.110 + showMathMenu: true, 1.111 + }, 1.112 + MMLorHTML: { 1.113 + prefer: { 1.114 + MSIE: "MML", 1.115 + Firefox: "MML", 1.116 + Opera: "HTML", 1.117 + other: "HTML" 1.118 + } 1.119 + } 1.120 + }); 1.121 +/*]]>*///--> 1.122 +</script> 1.123 +</head> 1.124 +<body> 1.125 +<div id="content"> 1.126 + 1.127 + 1.128 + 1.129 +<h1> 1.130 +Monads in CS and Math 1.131 +</h1> 1.132 + 1.133 +<p> 1.134 +The purpose of a <i>monad</i> is to introduce a new data type into your 1.135 +language and to integrate it with existing types; a monad augments a 1.136 +pre-existing data type \(A\), creating a new type \(B\). 1.137 +</p> 1.138 +<p> 1.139 +When describing monads, I will use the following terminology: 1.140 +</p><ul> 1.141 +<li>Values of type \(A\) are called <b>ordinary values</b>, because they belong 1.142 + to the pre-existing data type. 1.143 +</li> 1.144 +<li>Values of type \(B\) are called <b>monadic values</b>, because they 1.145 + belong to the type introduced by the monad. 1.146 +</li> 1.147 +<li>A function \(A\rightarrow B\) is called a <b>monadic function</b>; such 1.148 + functions accept regular values as input and return monadic values. 1.149 +</li> 1.150 +</ul> 1.151 + 1.152 + 1.153 +<p> 1.154 +A monad consists of 1.155 +two components for achieving this purpose: 1.156 +</p> 1.157 +<dl> 1.158 +<dt>A function that converts ordinary values into monadic values</dt><dd> 1.159 +<p> 1.160 + First, in order to create a new data type, each monad has an 1.161 + <i>upgrade function</i> which systematically adds structure to values of 1.162 + the existing data type, \(A\). Because the upgrade function produces 1.163 + enhanced values in a systematic way, the enhanced values constitute 1.164 + a sort of new data type, \(B\). 1.165 +</p></dd> 1.166 +</dl> 1.167 + 1.168 + 1.169 +<blockquote> 1.170 + 1.171 + 1.172 +\(\text{upgrade}:A\rightarrow B\) 1.173 + 1.174 +</blockquote> 1.175 + 1.176 + 1.177 +<dl> 1.178 +<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 1.179 + protocol for combining a monadic function and a monadic value to 1.180 + produce a monadic value. The pipe function facilitates composition: 1.181 + notice that a collection of monadic functions \(A\rightarrow B\) is composable only if they have been modified by the 1.182 + pipe function to become functions of type \(B\rightarrow B\), otherwise their input and output types do not match. 1.183 +</dd> 1.184 +</dl> 1.185 + 1.186 +<blockquote> 1.187 + 1.188 + 1.189 +\(\text{pipe}:B\times B^A\rightarrow B\) 1.190 + 1.191 +</blockquote> 1.192 + 1.193 + 1.194 + 1.195 + 1.196 + 1.197 + 1.198 +<pre class="src src-clojure">(<span style="color: #f0dfaf; font-weight: bold;">ns</span> categorical.monad) 1.199 + 1.200 +</pre> 1.201 + 1.202 + 1.203 + 1.204 + 1.205 + 1.206 +<div id="table-of-contents"> 1.207 +<h2>Table of Contents</h2> 1.208 +<div id="text-table-of-contents"> 1.209 +<ul> 1.210 +<li><a href="#sec-1">1 Examples of monads </a> 1.211 +<ul> 1.212 +<li><a href="#sec-1-1">1.1 The nondeterministic monad </a></li> 1.213 +</ul> 1.214 +</li> 1.215 +</ul> 1.216 +</div> 1.217 +</div> 1.218 + 1.219 +<div id="outline-container-1" class="outline-2"> 1.220 +<h2 id="sec-1"><span class="section-number-2">1</span> Examples of monads </h2> 1.221 +<div class="outline-text-2" id="text-1"> 1.222 + 1.223 + 1.224 +</div> 1.225 + 1.226 +<div id="outline-container-1-1" class="outline-3"> 1.227 +<h3 id="sec-1-1"><span class="section-number-3">1.1</span> The nondeterministic monad </h3> 1.228 +<div class="outline-text-3" id="text-1-1"> 1.229 + 1.230 + 1.231 +<p> 1.232 +We'll implement nondeterministic programming by defining a monad <code>amb</code> 1.233 +that transforms ordinary deterministic functions into functions that ``ambiguously'' return zero or more 1.234 +values. 1.235 +</p> 1.236 + 1.237 + 1.238 + 1.239 +<pre class="src src-clojure"></pre> 1.240 + 1.241 + 1.242 + 1.243 +</div> 1.244 +</div> 1.245 +</div> 1.246 +<div id="postamble"> 1.247 +<p class="date">Date: 2011-07-11 03:07:07 EDT</p> 1.248 +<p class="author">Author: Robert McIntyre</p> 1.249 +<p class="creator">Org version 7.6 with Emacs version 23</p> 1.250 +<a href="http://validator.w3.org/check?uri=referer">Validate XHTML 1.0</a> 1.251 +</div> 1.252 +</div> 1.253 +</body> 1.254 +</html>