rlm@2: #+TITLE: Monads in CS and Math
rlm@2: #+BEGIN_HTML
rlm@2: <h1>
rlm@2: {{{TITLE}}}
rlm@2: </h1>
rlm@2: #+END_HTML
rlm@2: 
rlm@2: The purpose of a /monad/ is to introduce a new data type into your
rlm@2: language and to integrate it with existing types; a monad augments a
rlm@2: pre-existing data type $A$, creating a new type $B$. 
rlm@2: 
rlm@2: When describing monads, I will use the following terminology:
rlm@2: - Values of type $A$ are called *ordinary values*, because they belong
rlm@2:   to the pre-existing data type.
rlm@2: - Values of type $B$ are called *monadic values*, because they
rlm@2:   belong to the type introduced by the monad.
rlm@2: - A function $A\rightarrow B$ is called a *monadic function*; such
rlm@2:   functions accept regular values as input and return monadic values.
rlm@2: 
rlm@2: 
rlm@2: 
rlm@2: A monad consists of
rlm@2: two components for achieving this purpose: 
rlm@2: 
rlm@2: - A function that converts ordinary values into monadic values ::
rlm@2:      First, in order to create a new data type, each monad has an
rlm@2:   /upgrade function/ which systematically adds structure to values of
rlm@2:   the existing data type, $A$. Because the upgrade function produces
rlm@2:   enhanced values in a systematic way, the enhanced values constitute
rlm@2:   a sort of new data type, $B$.
rlm@2: 
rlm@2: #+begin_quote
rlm@2: $\text{upgrade}:A\rightarrow B$
rlm@2: #+end_quote
rlm@2: 
rlm@2: - A function that enables monadic functions to accept monadic values :: Second, each monad has a /pipe function/ which is a
rlm@2:   protocol for combining a monadic function and a monadic value to
rlm@2:   produce a monadic value. The pipe function facilitates composition:
rlm@2:   notice that a collection of monadic functions $A\rightarrow B$ is composable only if they have been modified by the
rlm@2:   pipe function to become functions of type $B\rightarrow B$, otherwise their input and output types do not match.
rlm@2: #+begin_quote
rlm@2: $\text{pipe}:B\times B^A\rightarrow B$
rlm@2: #+end_quote
rlm@2: 
rlm@2: #+srcname: intro
rlm@2: #+begin_src clojure :results silent
rlm@2: (ns categorical.monad)
rlm@2: (use 'clojure.contrib.monads)
rlm@2: #+end_src
rlm@2: 
rlm@2: 
rlm@2: * Examples of monads
rlm@2: ** The nondeterministic  monad
rlm@2: 
rlm@2: We'll implement nondeterministic programming by defining a monad =amb=
rlm@2: that transforms ordinary deterministic functions into functions that ``ambiguously'' return zero or more
rlm@2: values. 
rlm@2: 
rlm@2: #+srcname: stuff
rlm@2: #+begin_src clojure :results silent
rlm@2: (in-ns 'categorical.monad)
rlm@2: 
rlm@2: ;; 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: 
rlm@2: (defmonad amb
rlm@2:   [
rlm@2:    m-result (fn[& vals] (cons 'amb vals))
rlm@2:    m-bind (fn[amb-seq f] (cons 'amb (map f (rest amb-seq))))
rlm@2:    ]
rlm@2: )
rlm@2: #+end_src
rlm@2: 
rlm@2: #+begin_src clojure :results silent :tangle monad.clj :noweb yes
rlm@2: <<intro>>
rlm@2: <<stuff>>
rlm@2: #+end_src