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