Mercurial > dylan
diff categorical/monad.org @ 2:b4de894a1e2e
initial import
author | Robert McIntyre <rlm@mit.edu> |
---|---|
date | Fri, 28 Oct 2011 00:03:05 -0700 |
parents | |
children |
line wrap: on
line diff
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