Changeset 32837 in project
 Timestamp:
 10/24/15 20:35:27 (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

wiki/eggref/4/monad
r32836 r32837 1 1 == Monads 2 3 2 Monads for Scheme 4 3 5 [[toc:]] 4 ```[[https://github.com/dleslie/monadegg/issuesPlease file Issues]] if you find a bug or need help; I will attempt to address them!''' 6 5 7 == Description 6 Full documentation, with examples, [[https://github.com/dleslie/monadegg/blob/master/readme.orgCan be found on GitHub]]. 8 7 9 '''[[https://github.com/dleslie/monadegg/issuesPlease file Issues]] if you find a bug or need help; I will attempt to address them!'''10 11 === What is a Monad?12 13 Monads are like a burrito.14 15 Ok, well not.16 17 Monads are types that have:18 19 1. A binding function of the form: M a > (a > M b) > M b20 21 2. A unit function: a > M a22 23 That's it.24 25 For instance, the identity monad is:26 27 1. Bind: (lambda (a f) (f a))28 29 2. Unit: (lambda (a) a)30 31 Not too bad, eh?32 33 Most 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.34 35 The Monad egg allows you to write that code once and remain focused on the task at hand.36 37 === Why not use miscmacros:doto instead?38 39 Because you may want intermediary control and multiple usage of a unit function.40 41 Monads 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.42 43 Yes, sometimes this isn't strictly a necessary set of functionality. But for when it is, save yourself some time and write a monad.44 45 === Functions46 47 ==== (definemonad name unitfunction bindfunction [failfunction])48 8 49 9 <macro>(definemonad name unitfunction bindfunction [failfunction])</macro> 50 51 Providing âfailfunctionâ is optional.52 53 Defines a new monad of the given name. Also defines the following procedures:54 55 <table>56 <tr><th>Function</th><th>Usage</th></tr>57 <tr><td>nameunit</td><td>Constructs a new monad from a value using the given unit function</td></tr>58 <tr><td>namebind</td><td>Constructs a new monad from an existing monad and a function using the given bind function</td></tr>59 <tr><td>namefail</td><td>Constructs a âfailureâ case monad for the given monadic type. Defaults to throwing an assert</td></tr>60 </table>61 62 ==== (using monad [body ...])63 64 10 <macro>(using monad [body ...])</macro> 65 66 Within the body the following procedures will be defined:67 68 <table>69 <tr><th>Function</th><th>Usage</th></tr>70 <tr><td>>>=</td><td>Maps to bind</td></tr>71 <tr><td>return</td><td>Maps to unit</td></tr>72 <tr><td>fail</td><td>Maps to fail</td></tr>73 </table>74 75 Ie:76 77 <enscript highlight="scheme">78 (using <id>79 (>>= (return 1) (lambda (x) (+ x 1))))80 </enscript>81 82 Is the same as:83 84 <enscript highlight="scheme">85 (<id>bind (<id>unit 1) (lambda (x) (+ x 1)))86 </enscript>87 88 ==== (return monad value)89 90 11 <macro>(return monad value)</macro> 91 92 Allows any function to lift a value into the monad provided. Ie,93 94 <enscript highlight="scheme">95 (define (foo bar)96 (if (not bar)97 (fail <maybe>)98 (return <maybe> bar)))99 </enscript>100 101 Would be the same as:102 103 <enscript highlight="scheme">104 (define (foo bar)105 (if (not bar)106 (<maybe>fail)107 (<maybe>unit bar)))108 </enscript>109 110 Would be the same as:111 112 <enscript highlight="scheme">113 (define (foo bar)114 (if (not bar)115 'Nothing116 `(Just ,bar)))117 </enscript>118 119 ==== (fail monad [body ...])120 121 12 <macro>(fail monad [body ...])</macro> 122 123 Creates the failure case for the given monad, optionally providing a body to the failure state constructor.124 125 Defaults to throwing an assert for most monads.126 127 ==== (dousing monad [body ...])128 129 13 <macro>(dousing monad [body ...])</macro> 130 131 Similar to the (using) procedure, but allows for even more terseness.132 133 Within dousing the following will be defined:134 135 <table>136 <tr><th>Function</th><th>Usage</th></tr>137 <tr><td>>>=</td><td>Maps to bind</td></tr>138 <tr><td>return</td><td>Maps to unit</td></tr>139 <tr><td>fail</td><td>Maps to fail</td></tr>140 <tr><td>/m</td><td>Shorthand for calling monadspecific functions, details follow</td></tr>141 <tr><td>/m!</td><td>Shorthand for calling monadspecific functions, details follow</td></tr>142 <tr><td><</td><td>Shorthand for binding a symbol to a monadic value, details follow</td></tr>143 </table>144 145 ===== /m! Keyword146 147 The /m! keyword is used as a shortcut for referencing monadspecific procedures which are prefixed with the current monad name.148 149 For example:150 151 <enscript highlight="scheme">152 (dousing <writer> (/m! tell 1))153 </enscript>154 155 Is the same as:156 157 <enscript highlight="scheme">158 (dousing <writer> (<writer>tell 1))159 </enscript>160 161 ===== /m Keyword162 163 The /m keyword is like /m!, except that it references the procedure without executing it.164 165 For example:166 167 <enscript highlight="scheme">168 (dousing <state> (x < (/m get)) (return x))169 </enscript>170 171 Is the same as:172 173 <enscript highlight="scheme">174 (dousing <writer> (x < <state>get) (return x))175 </enscript>176 177 ===== < Keyword178 179 The < keyword is used as a shortcut for binding a value within a monad.180 181 For example:182 183 <enscript highlight="scheme">184 (dousing <maybe>185 (x < (return 1))186 x)187 </enscript>188 189 Is the same as:190 191 <enscript highlight="scheme">192 (dousing <maybe>193 (>>= (return 1)194 (lambda (x)195 (dousing <maybe>196 x))))197 </enscript>198 199 ===== General Example200 201 A simple example:202 203 <enscript highlight="scheme">204 (dousing <maybe>205 (x < (return <maybe> 1))206 x)207 208 ;Returns:209 (Just 1)210 </enscript>211 212 Or, a more complex example:213 214 <enscript highlight="scheme">215 (dousing <maybe>216 (x < (return 1))217 (if (eq? 2 x)218 (return 'Banana)219 (fail))220 (y < (return 'Apple))221 y)222 223 ;Returns:224 Nothing225 </enscript>226 227 ==== (do/m monad [body ...])228 229 14 <macro>(do/m monad [body ...])</macro> 230 15 231 Alias for (dousing monad [body ...]). 232 233 === Basic Monads 234 235 Simple monads predefined by this egg. 236 237 ==== Identity 238 239 <enscript highlight="scheme"> 240 (definemonad 241 <id> 242 (lambda (a) a) 243 (lambda (a f) (f a))) 244 </enscript> 245 246 ==== Maybe 247 248 <enscript highlight="scheme"> 249 (definemonad 250 <maybe> 251 (lambda (a) a) 252 (lambda (a f) (if a (f (cadr a)) #f)) 253 (caselambda (() 'Nothing) 254 ((_ . _) 'Nothing))) 255 </enscript> 256 257 ===== Example 258 259 <enscript highlight="scheme"> 260 > (do/m <maybe> 261 (if #t 262 'Nothing 263 '(Just First)) 264 '(Just Second)) 265 Nothing 266 </enscript> 267 268 ==== List 269 270 <enscript highlight="scheme"> 271 (definemonad 272 <list> 273 (lambda (a) (list a)) 274 (lambda (a f) (concatenate! (map! f a)))) 275 </enscript> 276 277 ===== Example 278 279 <enscript highlight="scheme"> 280 #;> (do/m <list> 281 (x < '(1 2 3)) 282 (y < '(a b c)) 283 (return `(,x ,y))) 284 ((1 a) (1 b) (1 c) (2 a) (2 b) (2 c) (3 a) (3 b) (3 c)) 285 </enscript> 286 287 ==== State 288 289 <enscript highlight="scheme"> 290 (definemonad 291 <state> 292 (lambda (a) (lambda (s) `(,a . ,s))) 293 (lambda (a f) 294 (lambda (s) 295 (let* ((p (a s)) 296 (a^ (car p)) 297 (s^ (cdr p))) 298 ((f a^) s^))))) 299 </enscript> 300 301 ===== Extra Methods 302 303 ====== <state>get 304 305 <procedure>(<state>get s)</procedure> 306 307 Retrieves the current state from a given <state> monad. 308 309 ======= Example 310 311 <enscript highlight="scheme"> 312 #;> ((do/m <state> 313 (x < (/m get)) 314 (return x)) 315 "Hi!") 316 ("Hi!" . "Hi!") 317 </enscript> 318 319 ====== <state>gets 320 321 <procedure>(<state>gets f)</procedure> 322 323 Creates a monad that retrieves a given state after filtering it with the function provided. 324 325 ======= Example 326 327 <enscript highlight="scheme"> 328 #;> ((do/m <state> 329 (x < (/m! gets (lambda (s) (+ s 1)))) 330 (return x)) 331 1) 332 (2 . 1) 333 </enscript> 334 335 ====== <state>modify 336 337 <procedure>(<state>modify f)</procedure> 338 339 Creates a monad that modifies the current state with a given function. 340 341 ======= Example 342 343 <enscript highlight="scheme"> 344 #;> ((do/m <state> 345 (/m! modify (lambda (v) 346 (display (format "Received: ~S\n" v)) 347 (+ v 1)))) 348 1) 349 Received: 1 350 (() . 2) 351 </enscript> 352 353 ====== <state>put 354 355 <procedure>(<state>put v)</procedure> 356 357 Creates a monad that forces a value into the current <state> monad. 358 359 ======= Example 360 361 <enscript highlight="scheme"> 362 #;> ((do/m <state> 363 (/m! put 1)) 364 2) 365 (() . 1) 366 </enscript> 367 368 ==== Reader 369 370 <enscript highlight="scheme"> 371 (definemonad 372 <reader> 373 (lambda (a) (lambda (v) a)) 374 (lambda (a f) (lambda (v) ((f (a v)) v)))) 375 </enscript> 376 377 ===== Extra Methods 378 379 ====== <reader>ask 380 381 <procedure>(<reader>ask m)</procedure> 382 383 Extracts the current value from the current reader monad. 384 385 ======= Example 386 387 <enscript highlight="scheme"> 388 #;> ((do/m <reader> 389 (x < (/m ask)) 390 (return (+ x 1))) 391 1) 392 2 393 </enscript> 394 395 ====== <reader>asks 396 397 <procedure>(<reader>asks f)</procedure> 398 399 Creates a monad that filters the current value in the reader monad with the given function. 400 401 ======= Example 402 403 <enscript highlight="scheme"> 404 #;> ((do/m <reader> 405 (/m! asks (lambda (v) 406 (+ v 1)))) 407 1) 408 2 409 </enscript> 410 411 ====== <reader>local 412 413 <procedure>(<reader>local f m)</procedure> 414 415 Creats a monad that first filters the current reader monad value with the provided function, then passes that filtered value to the provided reader monad. 416 417 ======= Example 418 419 <enscript highlight="scheme"> 420 #;> ((do/m <reader> 421 (/m! local 422 (lambda (v) (+ v 1)) 423 (do/m <reader> 424 (x < (/m ask)) 425 (return x)))) 426 1) 427 2 428 </enscript> 429 430 ==== CPS 431 432 <enscript highlight="scheme"> 433 (definemonad 434 <cps> 435 (lambda (a) (lambda (k) (k a))) 436 (lambda (a f) (lambda (k) (a (lambda (a^) (let ((b (f a^))) (b k))))))) 437 </enscript> 438 439 ===== Extra Methods 440 441 ====== <cps>call/cc 442 443 <procedure>(<cps>call/cc f)</procedre> 444 445 Creates a monad that, when given a continuation, passes a monad to the provided function that applies the continuation to its input; then applies the continuation to the output of that function. 446 447 ==== Exception 448 449 <enscript highlight="scheme"> 450 (definemonad 451 <exception> 452 (lambda (a) `(success ,a)) 453 (lambda (a f) (if (eq? (car a) 'success) (f (cadr a)) a)) 454 (caselambda (() `(failure)) 455 ((a . b) `(failure ,a . ,b)))) 456 </enscript> 457 458 ===== Extra Methods 459 460 ====== <exception>throw 461 462 <procedure>(<exceptionthrow e)</procedure> 463 464 Synonym for <exception>fail. 465 466 ======= Example 467 468 <enscript highlight="scheme"> 469 #;> (do/m <exception> (/m! throw "Error! No more cheerios!")) 470 (failure "Error! No more cheerios!") 471 </enscript> 472 473 ====== <exception>catch 474 475 <procedure>(<exception>catch m f)</procedure> 476 477 Creates a monad that examines an exception monad and passes the value to the provided function if it had failed. 478 479 ======= Example 480 481 <enscript highlight="scheme"> 482 #;> (define somemonad 483 (do/m <exception> 484 (/m! throw "An error happened! Oh no!"))) 485 #;> (do/m <exception> 486 (/m! catch somemonad 487 (lambda (m) 488 (display (format "Caught an exception: ~S" 489 (cadr m)))))) 490 Caught an exception: "An error happened! Oh no!" 491 </enscript> 492 493 ==== Writer 494 495 <enscript highlight="scheme"> 496 (definemonad 497 <writer> 498 (lambda (a) `(,a . ())) 499 (lambda (a f) 500 (let ((b (f (car a)))) 501 `(,(car b) . ,(append (cdr a) (cdr b)))))) 502 </enscript> 503 504 ===== Extra Methods 505 506 ====== <writer>tell 507 508 <procedure>(<writer>tell v)</procedure> 509 510 Creates a monad where the provided value is wrapped in a <writer>. 511 512 ======= Example 513 514 <enscript highlight="scheme"> 515 #;> (do/m <writer> (/m! tell '(1 2 3))) 516 (() 1 2 3) 517 </enscript> 518 519 ====== <writer>listen 520 521 <procedure>(<writer>listen a)</procedure> 522 523 Creates a monad where the value has been extracted out of the writer. 524 525 ======= Example 526 527 <enscript highlight="scheme"> 528 #;> (do/m <writer> 529 (x < (/m! listen 530 (/m! tell '(foo)))) 531 (return x)) 532 ((() foo) foo) 533 </enscript> 534 535 ====== <writer>listens 536 537 <procedure>(<writer>listens f m)</procedure> 538 539 Creates a monad that is the outcome of applying the provided function on the given writer monad. 540 541 ======= Example 542 543 <enscript highlight="scheme"> 544 #;> (do/m <writer> 545 (x < (return (/m! tell '(1 2 3)))) 546 (/m! listens 547 (lambda (l) (map (lambda (v) (+ v 1)) l)) 548 (return x))) 549 ((() 2 3 4)) 550 </enscript> 551 552 ====== <writer>pass 553 554 <procedure>(<writer>pass m)</procedure> 555 556 Creates a monad that is the outcome of mutating the provided writer monad with a given function. Expects to be provided a monad of the form: ((value . function) . restofwriter) 557 558 Not generally used much except by those that know what they're doing, you're likely after <writer>censor for most cases. 559 560 ======= Example 561 562 <enscript highlight="scheme"> 563 #;> (do/m <writer> 564 (x < (/m! listen 565 `((() . ,(lambda (l) 566 (map (lambda (v) (+ v 1)) l))) 567 . (1 2 3)))) 568 (/m! pass x)) 569 (() 1 2 3 2 3 4) 570 </enscript> 571 572 ====== <writer>censor 573 574 <procedure>(<writer>censor f m)</procedure> 575 576 Creates a monad resulting from the application of the provided function on the given monad, censoring the values that were in the given monad. 577 578 ======= Example 579 580 <enscript highlight="scheme"> 581 #;> (do/m <writer> 582 (/m! censor (lambda (l) (map (lambda (v) (+ v 1)) l)) 583 (/m! tell '(1 2 3)))) 584 (() 2 3 4) 585 </enscript> 586 587 === Contribution 16 * Contribution 588 17 589 18 Contributions are welcome provided you accept the license I have chosen for this egg for the contributions themselves. 590 19 591 The github repository is at: [[https://github.com/dleslie/monadegg ]]20 The github repository is at: [[https://github.com/dleslie/monadegghttps://github.com/dleslie/monadegg]] 592 21 593 ===Authors22 * Authors 594 23 595 Original Egg by Daniel J. Leslie24 Original Egg By Daniel J. Leslie 596 25 dan@ironoxide.ca 597 26 598 State, Reader, Writer, CPS and Exception monads contributed by Cameron Swords. 27 Additional Contributors: 28 Cameron Swords. 29 Peter Bex 599 30 600 === Version History 31 * License 601 32 602 ; 4.1 : Fixed #7, updated readme.org 603 ; 4.0 : Dropped Exception and CPS, as they did not work under basic tests; removed do keyword, fixed Writer monad 604 ; 3.3 : Total rewrite, no API changes 605 ; 3.2 : Minor syntax change 606 ; 3.0 : Renamed :! to /m! and : to /m due to : already being used for explicit specialization (oops) 607 ; 2.4 : Added :! keyword, fixed : keyword 608 ; 2.3 : Added fail function for all monads which defaults to assert, but is definied appropriately for the <exception> and <maybe> monads. Added : keyword to using and dousing. Added >>=, return and fail bindings to dousing syntax. 609 ; 2.2 : Added failure states for monads 610 ; 2.1 : Rewrote API to allow for terser execution and a simpler interface. Removed use of promises completely. Removed dotousing, runchain, and run from the API completely. Added dousing syntax. Maybe monad is now selfdefined for it's value or novalue states. 611 ; 2.0 : Internal rewrite that broke the API, immediately followed by 2.1. 612 ; 1.1 : Added Cameron Swords' State, Reader, Writer, CPS and Exception monads 613 ; 1.0 : Initial release 33 Copyright 2012 Daniel J. Leslie. All rights reserved. 614 34 615 === License 35 Redistribution and use in source and binary forms, with or without modification, are 36 permitted provided that the following conditions are met: 616 37 617 Copyright 2012 Daniel J. Leslie. All rights reserved. 618 619 Redistribution and use in source and binary forms, with or without modification, are 620 permitted provided that the following conditions are met: 621 622 1. Redistributions of source code must retain the above copyright notice, this list of 623 conditions and the following disclaimer. 624 625 2. Redistributions in binary form must reproduce the above copyright notice, this list 626 of conditions and the following disclaimer in the documentation and/or other materials 627 provided with the distribution. 628 629 THIS SOFTWARE IS PROVIDED BY DANIEL J. LESLIE ''AS IS'' AND ANY EXPRESS OR IMPLIED 630 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 631 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DANIEL J. LESLIE OR 632 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 633 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 634 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 635 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 636 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 637 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 638 639 The views and conclusions contained in the software and documentation are those of the 640 authors and should not be interpreted as representing official policies, either expressed 641 or implied, of Daniel J. Leslie. 38 1. Redistributions of source code must retain the above copyright notice, this list of 39 conditions and the following disclaimer. 40 41 2. Redistributions in binary form must reproduce the above copyright notice, this list 42 of conditions and the following disclaimer in the documentation and/or other materials 43 provided with the distribution. 44 45 THIS SOFTWARE IS PROVIDED BY DANIEL J. LESLIE ''AS IS'' AND ANY EXPRESS OR IMPLIED 46 WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 47 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DANIEL J. LESLIE OR 48 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 49 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 50 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON 51 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 52 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 53 ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 54 55 The views and conclusions contained in the software and documentation are those of the 56 authors and should not be interpreted as representing official policies, either expressed 57 or implied, of Daniel J. Leslie.
Note: See TracChangeset
for help on using the changeset viewer.