source: project/wiki/eggref/4/monad @ 26480

Last change on this file since 26480 was 26480, checked in by svnwiki, 9 years ago

Anonymous wiki edit for IP [209.82.122.162]: Fixed parameter ordering

File size: 7.2 KB
Line 
1== Monads
2
3Monads for Scheme
4
5By Daniel J. Leslie
6
7dan@ironoxide.ca
8
9[[toc:]]
10
11== Description
12
13=== What is a Monad?
14
15Monads are like a burrito.
16
17Ok, well not.
18
19Monads are types that have:
20
211. A binding function of the form: a -> (a -> b) -> M b
22
232. A unit function: a -> M a
24
25That's it.
26
27For instance, the identity monad is:
28
291. Bind: (lambda (a f) (f a))
30
312. Unit: (lambda (a) a)
32
33Not too bad, eh?
34
35Most of what we write that can be described as a "recipe list" or a "do to" list is a Monad. And, as you may have noticed, we write a lot of boiler plate code to handle the interim wrapping/unwrapping/error checking functionality that occurs between each step.
36
37The Monad egg allows you to write that code once and remain focused on the task at hand.
38
39=== Why not use [[miscmacros]]:doto instead?
40
41Because you may want intermediary control and multiple usage of a unit function.
42
43Monads aren't simply about iterating over a value or set of values and passing them to various functions; they're about removing recurring boilerplate related to constructing the desired values, and any intermediary steps that may be required between processing the values.
44
45Yes, sometimes this isn't strictly a necessary set of functionality. But for when it is, save yourself some time and write a monad.
46
47=== Why not use [[F-operator]] instead?
48
49If you can understand what that is or how it works and it suits your needs better than this egg, then please, go right ahead.
50
51=== What's this about lazy evaluation?
52
53Yes, this monad implementation is lazily evaluated.
54
55When (run) is called with a given Monad the bind and unit functions are evaluated and their actions are undertaken. This happens once, and once only. Further executions of (run) will simply return the computed value of the first execution.
56
57Furthermore, when running in a REPL or printing to a string a monad will automatically be run!
58If you don't want this to happen, then capture the value before the REPL would print it.
59
60For example:
61<enscript highlight="scheme">
62#;1> (use monad)
63; loading /usr/local/lib/chicken/6/monad.so ...
64; loading /usr/local/lib/chicken/6/monad.import.so ...
65#;2> (define m (doto-using <id> 1 (lambda (x) (display "Hi!\n") (+ x 1))))
66#;3> m
67Hi!
68#<id> 2
69#;4> m
70#<id> 2
71#;5> (define (m2 y) (doto-using <id> y (lambda (x) (display "Hi!\n") (+ x 1))))
72#;6> (m2 1)
73Hi!
74#<id> 2
75#;7> (m2 1)
76Hi!
77#<id> 2
78</enscript>
79
80== Functions
81
82<procedure>(define-monad name unit-function bind-function)</procedure>
83
84Defines a new monad of the given name. Also defines the following procedures:
85
86; name-unit : Constructs a new monad from a value using the given unit function
87; name-bind : Constructs a new monad from an existing monad and a function using the given bind function
88; name? : Predicate for the new monad
89
90<procedure>(run monad)</procedure>
91
92Runs a monad and returns the outcome.
93
94<procedure>(run-chain init [monadic-functions ...])</procedure>
95
96Runs a chain of monadic functions.
97
98Expects that each monad-returning function accepts a single parameter which can be represented by the init value.
99
100Ie,
101<enscript highlight="scheme">
102 #;1> (define (f1 a) (using <id> (return a)))
103 #;2> (define (f2 a) (doto-using <id> a (lambda (b) (+ x b))))
104 #;3> (run-chain 1 f1 f2)
105 2
106</enscript>
107
108<procedure>(using monad [body ...])</procedure>
109
110Within the body the following procedures will be defined:
111
112; >>= : Maps to bind
113; return : Maps to unit
114
115Ie:
116<enscript highlight="scheme">
117(using <id>
118  (>>= (return 1) (lambda (x) (+ x 1))))
119
120;Is the same as:
121
122(<id>-bind (<id>-unit 1) (lambda  (x) (+ x 1)))
123</enscript>
124
125<procedure>(doto-using monad init [body ...])</procedure>
126
127Similar to the (using) procedure, but allows for even more terseness.
128
129The init value is turned into a monad using the monad's unit-function, and is then passed to a chain of monads constructed via a cascading chain of bind-function operations performed upon the body.
130
131Ie,
132<enscript highlight="scheme">
133(doto-using <id> (+ 0 1)
134  (lambda (x) (+ x 1))
135  (lambda (y) (+ y 2)))
136
137;Is the same as:
138
139(using <id>
140  (>>= (>>= (return (+ 0 1))
141            (lambda (x) (+ x 1)))
142       (lambda (y) (+ y 2))))
143</enscript>
144
145== Basic Monads
146
147These monads are all pre-defined by this egg.
148
149=== Identity
150
151<enscript highlight="scheme">
152 (define-monad
153   <id>
154   (lambda (a) a)
155   (lambda (a f) (f a)))
156</enscript>
157
158=== Maybe
159
160<enscript highlight="scheme">
161 (define-monad
162   <maybe>
163   (lambda (a) a)
164   (lambda (a f) (if a (f a) #f)))
165</enscript>
166
167=== List
168
169<enscript highlight="scheme">
170 (define-monad
171   <list>
172   (lambda (a) (list a))
173   (lambda (a f) (concatenate! (map! f a))))
174</enscript>
175
176== Example
177
178Everyone expects a prototypical logger example, so here goes:
179
180<enscript highlight="scheme">
181 ; Wrap the output port in the intermediary value, so that:
182 ; (return a) gives as a value ( output-port . a )
183
184 (define-monad <logger>
185   (lambda (a)
186     (let ((output-port (car a))
187           (value (cdr a)))
188       (fprintf output-port "Starting with: ~S\n" value)
189       a))
190   (lambda (a f)
191     (let* ((output-port (car a))
192            (value  (cdr a))
193            (returned (f v)))
194       (fprintf output-port "Calling (~S ~S) returned ~S\n" f value returned)
195       (cons output-port returned))))
196 
197 (define (f1 x) (+ x 1))
198 (define (f2 x) (- x 1))
199 
200 (define m
201   (doto-using <logger>
202               (cons (current-output-port) 0)
203               f1
204               f2))
205 
206 (assert (eq? 0 (cdr (run m)))
207         "Did the logger test work?")
208</enscript>
209
210Outputs:
211
212<enscript highlight="scheme">
213 Starting with: 0
214 Calling (#<procedure (f1 x)> 0) returned 1
215 Calling (#<procedure (f2 x)> 1) returned 0
216</enscript>
217
218== Contribution
219
220Contributions are welcome provided you accept the license I have chosen for this egg for the contributions themselves.
221
222The repository is at [[https://github.com/dleslie/monad-egg|GitHub]].
223
224== License
225
226Copyright 2012 Daniel J. Leslie. All rights reserved.
227
228Redistribution and use in source and binary forms, with or without modification, are
229permitted provided that the following conditions are met:
230
231   1. Redistributions of source code must retain the above copyright notice, this list of
232      conditions and the following disclaimer.
233
234   2. Redistributions in binary form must reproduce the above copyright notice, this list
235      of conditions and the following disclaimer in the documentation and/or other materials
236      provided with the distribution.
237
238THIS SOFTWARE IS PROVIDED BY DANIEL J. LESLIE ''AS IS'' AND ANY EXPRESS OR IMPLIED
239WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
240FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DANIEL J. LESLIE OR
241CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
242CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
243SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
244ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
245NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
246ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
247
248The views and conclusions contained in the software and documentation are those of the
249authors and should not be interpreted as representing official policies, either expressed
250or implied, of Daniel J. Leslie.
Note: See TracBrowser for help on using the repository browser.