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