1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/categorical/monad.org	Fri Oct 28 00:03:05 2011 -0700
     1.3 @@ -0,0 +1,76 @@
     1.4 +#+TITLE: Monads in CS and Math
     1.5 +#+BEGIN_HTML
     1.6 +<h1>
     1.7 +{{{TITLE}}}
     1.8 +</h1>
     1.9 +#+END_HTML
    1.10 +
    1.11 +The purpose of a /monad/ is to introduce a new data type into your
    1.12 +language and to integrate it with existing types; a monad augments a
    1.13 +pre-existing data type $A$, creating a new type $B$. 
    1.14 +
    1.15 +When describing monads, I will use the following terminology:
    1.16 +- Values of type $A$ are called *ordinary values*, because they belong
    1.17 +  to the pre-existing data type.
    1.18 +- Values of type $B$ are called *monadic values*, because they
    1.19 +  belong to the type introduced by the monad.
    1.20 +- A function $A\rightarrow B$ is called a *monadic function*; such
    1.21 +  functions accept regular values as input and return monadic values.
    1.22 +
    1.23 +
    1.24 +
    1.25 +A monad consists of
    1.26 +two components for achieving this purpose: 
    1.27 +
    1.28 +- A function that converts ordinary values into monadic values ::
    1.29 +     First, in order to create a new data type, each monad has an
    1.30 +  /upgrade function/ which systematically adds structure to values of
    1.31 +  the existing data type, $A$. Because the upgrade function produces
    1.32 +  enhanced values in a systematic way, the enhanced values constitute
    1.33 +  a sort of new data type, $B$.
    1.34 +
    1.35 +#+begin_quote
    1.36 +$\text{upgrade}:A\rightarrow B$
    1.37 +#+end_quote
    1.38 +
    1.39 +- A function that enables monadic functions to accept monadic values :: Second, each monad has a /pipe function/ which is a
    1.40 +  protocol for combining a monadic function and a monadic value to
    1.41 +  produce a monadic value. The pipe function facilitates composition:
    1.42 +  notice that a collection of monadic functions $A\rightarrow B$ is composable only if they have been modified by the
    1.43 +  pipe function to become functions of type $B\rightarrow B$, otherwise their input and output types do not match.
    1.44 +#+begin_quote
    1.45 +$\text{pipe}:B\times B^A\rightarrow B$
    1.46 +#+end_quote
    1.47 +
    1.48 +#+srcname: intro
    1.49 +#+begin_src clojure :results silent
    1.50 +(ns categorical.monad)
    1.51 +(use 'clojure.contrib.monads)
    1.52 +#+end_src
    1.53 +
    1.54 +
    1.55 +* Examples of monads
    1.56 +** The nondeterministic  monad
    1.57 +
    1.58 +We'll implement nondeterministic programming by defining a monad =amb=
    1.59 +that transforms ordinary deterministic functions into functions that ``ambiguously'' return zero or more
    1.60 +values. 
    1.61 +
    1.62 +#+srcname: stuff
    1.63 +#+begin_src clojure :results silent
    1.64 +(in-ns 'categorical.monad)
    1.65 +
    1.66 +;; To implement nondeterministic programs, we'll use a lazy seq to represent a value which may be any one of the members of seq.
    1.67 +
    1.68 +(defmonad amb
    1.69 +  [
    1.70 +   m-result (fn[& vals] (cons 'amb vals))
    1.71 +   m-bind (fn[amb-seq f] (cons 'amb (map f (rest amb-seq))))
    1.72 +   ]
    1.73 +)
    1.74 +#+end_src
    1.75 +
    1.76 +#+begin_src clojure :results silent :tangle monad.clj :noweb yes
    1.77 +<<intro>>
    1.78 +<<stuff>>
    1.79 +#+end_src