Changeset 32837 in project


Ignore:
Timestamp:
10/24/15 20:35:27 (4 years ago)
Author:
svnwiki
Message:

Anonymous wiki edit for IP [70.67.150.22]: Maintaining two sets of documentation is unfun.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/4/monad

    r32836 r32837  
    11== Monads
    2 
    32Monads for Scheme
    43
    5 [[toc:]]
     4```[[https://github.com/dleslie/monad-egg/issues|Please file Issues]] if you find a bug or need help; I will attempt to address them!'''
    65
    7 == Description
     6Full documentation, with examples, [[https://github.com/dleslie/monad-egg/blob/master/readme.org|Can be found on GitHub]].
    87
    9 '''[[https://github.com/dleslie/monad-egg/issues|Please 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 b
    20 
    21 2. A unit function: a -> M a
    22 
    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 === Functions
    46 
    47 ==== (define-monad name unit-function bind-function [fail-function])
    488
    499<macro>(define-monad name unit-function bind-function [fail-function])</macro>
    50 
    51 Providing ‘fail-function’ 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>name-unit</td><td>Constructs a new monad from a value using the given unit function</td></tr>
    58 <tr><td>name-bind</td><td>Constructs a new monad from an existing monad and a function using the given bind function</td></tr>
    59 <tr><td>name-fail</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 
    6410<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>&gt;&gt;=</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 
    9011<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       'Nothing
    116       `(Just ,bar)))
    117 </enscript>
    118 
    119 ==== (fail monad [body ...])
    120 
    12112<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 ==== (do-using monad [body ...])
    128 
    12913<macro>(do-using monad [body ...])</macro>
    130 
    131 Similar to the (using) procedure, but allows for even more terseness.
    132 
    133 Within do-using the following will be defined:
    134 
    135 <table>
    136 <tr><th>Function</th><th>Usage</th></tr>
    137 <tr><td>&gt;&gt;=</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 monad-specific functions, details follow</td></tr>
    141 <tr><td>/m!</td><td>Shorthand for calling monad-specific functions, details follow</td></tr>
    142 <tr><td>&lt;-</td><td>Shorthand for binding a symbol to a monadic value, details follow</td></tr>
    143 </table>
    144 
    145 ===== /m! Keyword
    146 
    147 The /m! keyword is used as a shortcut for referencing monad-specific procedures which are prefixed with the current monad name.
    148 
    149 For example:
    150 
    151 <enscript highlight="scheme">
    152 (do-using <writer> (/m! tell 1))
    153 </enscript>
    154 
    155 Is the same as:
    156 
    157 <enscript highlight="scheme">
    158 (do-using <writer> (<writer>-tell 1))
    159 </enscript>
    160 
    161 ===== /m Keyword
    162 
    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 (do-using <state> (x <- (/m get)) (return x))
    169 </enscript>
    170 
    171 Is the same as:
    172 
    173 <enscript highlight="scheme">
    174 (do-using <writer> (x <- <state>-get) (return x))
    175 </enscript>
    176 
    177 ===== <- Keyword
    178 
    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 (do-using <maybe>
    185   (x <- (return 1))
    186   x)
    187 </enscript>
    188 
    189 Is the same as:
    190 
    191 <enscript highlight="scheme">
    192 (do-using <maybe>
    193   (>>= (return 1)
    194     (lambda (x)
    195       (do-using <maybe>
    196         x))))
    197 </enscript>
    198 
    199 ===== General Example
    200 
    201 A simple example:
    202 
    203 <enscript highlight="scheme">
    204 (do-using <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 (do-using <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 Nothing
    225 </enscript>
    226 
    227 ==== (do/m monad [body ...])
    228 
    22914<macro>(do/m monad [body ...])</macro>
    23015
    231 Alias for (do-using monad [body ...]).
    232 
    233 === Basic Monads
    234 
    235 Simple monads pre-defined by this egg.
    236 
    237 ==== Identity
    238 
    239 <enscript highlight="scheme">
    240 (define-monad
    241   <id>
    242   (lambda (a) a)
    243   (lambda (a f) (f a)))
    244 </enscript>
    245 
    246 ==== Maybe
    247 
    248 <enscript highlight="scheme">
    249 (define-monad
    250   <maybe>
    251   (lambda (a) a)
    252   (lambda (a f) (if a (f (cadr a)) #f))
    253   (case-lambda (() '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 (define-monad
    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 (define-monad
    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 (define-monad
    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 (define-monad
    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 (define-monad
    451   <exception>
    452   (lambda (a) `(success ,a))
    453   (lambda (a f) (if (eq? (car a) 'success) (f (cadr a)) a))
    454   (case-lambda (() `(failure))
    455                ((a . b) `(failure ,a . ,b))))
    456 </enscript>
    457 
    458 ===== Extra Methods
    459 
    460 ====== <exception>-throw
    461 
    462 <procedure>(<exception-throw 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 some-monad
    483             (do/m <exception>
    484                 (/m! throw "An error happened! Oh no!")))
    485 #;> (do/m <exception>
    486         (/m! catch some-monad
    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 (define-monad
    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) . rest-of-writer)
    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
    58817
    58918Contributions are welcome provided you accept the license I have chosen for this egg for the contributions themselves.
    59019
    591 The github repository is at: [[https://github.com/dleslie/monad-egg]]
     20The github repository is at: [[https://github.com/dleslie/monad-egg|https://github.com/dleslie/monad-egg]]
    59221
    593 === Authors
     22* Authors
    59423
    595 Original Egg by Daniel J. Leslie
     24Original Egg By Daniel J. Leslie
    59625dan@ironoxide.ca
    59726
    598 State, Reader, Writer, CPS and Exception monads contributed by Cameron Swords.
     27Additional Contributors:
     28Cameron Swords.
     29Peter Bex
    59930
    600 === Version History
     31* License
    60132
    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 &lt;exception&gt; and &lt;maybe&gt; monads. Added : keyword to using and do-using. Added &gt;&gt;=, return and fail bindings to do-using 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 doto-using, run-chain, and run from the API completely. Added do-using syntax. Maybe monad is now self-defined for it's value or no-value 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
     33Copyright 2012 Daniel J. Leslie. All rights reserved.
    61434
    615 === License
     35Redistribution and use in source and binary forms, with or without modification, are
     36permitted provided that the following conditions are met:
    61637
    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
     45THIS SOFTWARE IS PROVIDED BY DANIEL J. LESLIE ''AS IS'' AND ANY EXPRESS OR IMPLIED
     46WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
     47FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL DANIEL J. LESLIE OR
     48CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     49CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
     50SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
     51ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     52NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
     53ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     54
     55The views and conclusions contained in the software and documentation are those of the
     56authors and should not be interpreted as representing official policies, either expressed
     57or implied, of Daniel J. Leslie.
Note: See TracChangeset for help on using the changeset viewer.