#+TITLE: Monads in CS and Math

 #+BEGIN_HTML

 <h1>

 {{{TITLE}}}

 </h1>

 #+END_HTML

 

 The purpose of a /monad/ is to introduce a new data type into your

 language and to integrate it with existing types; a monad augments a

 pre-existing data type $A$, creating a new type $B$. 

 

 When describing monads, I will use the following terminology:

 - Values of type $A$ are called *ordinary values*, because they belong

   to the pre-existing data type.

 - Values of type $B$ are called *monadic values*, because they

   belong to the type introduced by the monad.

 - A function $A\rightarrow B$ is called a *monadic function*; such

   functions accept regular values as input and return monadic values.

 

 

 

 A monad consists of

 two components for achieving this purpose: 

 

 - A function that converts ordinary values into monadic values ::

      First, in order to create a new data type, each monad has an

   /upgrade function/ which systematically adds structure to values of

   the existing data type, $A$. Because the upgrade function produces

   enhanced values in a systematic way, the enhanced values constitute

   a sort of new data type, $B$.

 

 #+begin_quote

 $\text{upgrade}:A\rightarrow B$

 #+end_quote

 

 - A function that enables monadic functions to accept monadic values :: Second, each monad has a /pipe function/ which is a

   protocol for combining a monadic function and a monadic value to

   produce a monadic value. The pipe function facilitates composition:

   notice that a collection of monadic functions $A\rightarrow B$ is composable only if they have been modified by the

   pipe function to become functions of type $B\rightarrow B$, otherwise their input and output types do not match.

 #+begin_quote

 $\text{pipe}:B\times B^A\rightarrow B$

 #+end_quote

 

 #+srcname: intro

 #+begin_src clojure :results silent

 (ns categorical.monad)

 (use 'clojure.contrib.monads)

 #+end_src

 

 

 * Examples of monads

 ** The nondeterministic  monad

 

 We'll implement nondeterministic programming by defining a monad =amb=

 that transforms ordinary deterministic functions into functions that ``ambiguously'' return zero or more

 values. 

 

 #+srcname: stuff

 #+begin_src clojure :results silent

 (in-ns 'categorical.monad)

 

 ;; To implement nondeterministic programs, we'll use a lazy seq to represent a value which may be any one of the members of seq.

 

 (defmonad amb

   [

    m-result (fn[& vals] (cons 'amb vals))

    m-bind (fn[amb-seq f] (cons 'amb (map f (rest amb-seq))))

    ]

 )

 #+end_src

 

 #+begin_src clojure :results silent :tangle monad.clj :noweb yes

 <<intro>>

 <<stuff>>

 #+end_src