Mercurial > dylan

comparison categorical/monad.org @ 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 #+TITLE: Monads in CS and Math
2 #+BEGIN_HTML
3 <h1>
4 {{{TITLE}}}
5 </h1>
6 #+END_HTML
7
8 The purpose of a /monad/ is to introduce a new data type into your
9 language and to integrate it with existing types; a monad augments a
10 pre-existing data type $A$, creating a new type $B$.
11
12 When describing monads, I will use the following terminology:
13 - Values of type $A$ are called *ordinary values*, because they belong
14 to the pre-existing data type.
15 - Values of type $B$ are called *monadic values*, because they
16 belong to the type introduced by the monad.
17 - A function $A\rightarrow B$ is called a *monadic function*; such
18 functions accept regular values as input and return monadic values.
19
20
21
22 A monad consists of
23 two components for achieving this purpose:
24
25 - A function that converts ordinary values into monadic values ::
26 First, in order to create a new data type, each monad has an
27 /upgrade function/ which systematically adds structure to values of
28 the existing data type, $A$. Because the upgrade function produces
29 enhanced values in a systematic way, the enhanced values constitute
30 a sort of new data type, $B$.
31
32 #+begin_quote
33 $\text{upgrade}:A\rightarrow B$
34 #+end_quote
35
36 - A function that enables monadic functions to accept monadic values :: Second, each monad has a /pipe function/ which is a
37 protocol for combining a monadic function and a monadic value to
38 produce a monadic value. The pipe function facilitates composition:
39 notice that a collection of monadic functions $A\rightarrow B$ is composable only if they have been modified by the
40 pipe function to become functions of type $B\rightarrow B$, otherwise their input and output types do not match.
41 #+begin_quote
42 $\text{pipe}:B\times B^A\rightarrow B$
43 #+end_quote
44
45 #+srcname: intro
46 #+begin_src clojure :results silent
47 (ns categorical.monad)
48 (use 'clojure.contrib.monads)
49 #+end_src
50
51
52 * Examples of monads
53 ** The nondeterministic monad
54
55 We'll implement nondeterministic programming by defining a monad =amb=
56 that transforms ordinary deterministic functions into functions that ``ambiguously'' return zero or more
57 values.
58
59 #+srcname: stuff
60 #+begin_src clojure :results silent
61 (in-ns 'categorical.monad)
62
63 ;; To implement nondeterministic programs, we'll use a lazy seq to represent a value which may be any one of the members of seq.
64
65 (defmonad amb
66 [
67 m-result (fn[& vals] (cons 'amb vals))
68 m-bind (fn[amb-seq f] (cons 'amb (map f (rest amb-seq))))
69 ]
70 )
71 #+end_src
72
73 #+begin_src clojure :results silent :tangle monad.clj :noweb yes
74 <<intro>>
75 <<stuff>>
76 #+end_src