#lang planet/scribble
@(require (for-label racket))
@title{Better Monads}
@defmodule[functional/better-monads]
This library is an attempt to facilitate pure functional programming
by providing a set of functions and special forms for working with
monads. It also provides the definition of several common monads
extended in such a way as to make their use in dynamic languages more
convenient. The user can define their own monads for later use as
well.
@section{Usage}
What follows is a brief tutorial on the usage of this library.
@subsection{mlet*}
The most important special form in the library is the @racket[mlet*]
syntax, which is the "Schemeish" monadic binding form, roughly
equivalent to Haskell's "do" notation.
Monads allow you to extend the meaning of variable binding within an
@racket[mlet*] expression, and hence @racket[mlet*] is very similar to
@racket[let*], in that it takes a series of binding pairs and then
evaluates a body of expressions, as in a @racket[begin] form.
In fact, at the top level, @racket[mlet*] behaves identically to
@racket[let*]:
@racketblock[
(require functional/better-monads)
(mlet* ((x 10)
(y 11))
(+ x y))]
By default, @racket[mlet*] performs its bindings in whatever monad is
stored in the lexical variable @racket[current-monad], which Better
Monads exports as the identity monad (also available in the variable
@racket[the-identity-monad]).
One difference, which applies to all monads, is that Racket's built-in
"match" patterns can be substituted for the symbols in the binding
form. For example:
@racketblock[
(struct doublet (a b))
(mlet* (((list x y) (list 1 2))
((doublet q r) (doublet 100 101)))
(list x y q r))]
Will return @racket['(1 2 100 101)].
@subsection{Working with a Monad}
Besides extending @racket[let*] with pattern matching, the library
doesn't do much until you start using monads other than
@racket[the-identity-monad]. Alternative monads are introduced using
the @racket[in:] option in @racket[mlet*]. For instance:
@racketblock[
(struct doublet (a b) #:transparent)
(mlet* in: the-list-monad
((x '(1 2 3 4))
(y '(a b c d)))
(return (doublet x y)))]
Will result in:
@racketblock[(list
(doublet 1 'a)
(doublet 1 'b)
(doublet 1 'c)
(doublet 1 'd)
(doublet 2 'a)
...)]
And so on, to include all the combinations of the items bound to
@racket[x] and @racket[y], which is the behavior of
@racket[the-list-monad].
Note the use of the function @racket[return] in the body of the
@racket[mlet*] expression. In the context of an @racket[mlet*]
expression, the symbosl @racket[bind], and @racket[return] are bound
to the appropriate functions in the specified monad. If the monad
also defines @racket[plus] and/or @racket[zero], these will also be
appropriately bound. Otherwise they will be bound to @racket[#f]. In
the lexical scope of an @racket[mlet*] expression, the
@racket[current-monad] will be bound to the monad specified after
@racket[in:].
@subsection{Defining Additional Monads}
The use may define her own monads by creating an instance of the
@racket[monad] structure. For instance, we might define the "maybe"
monad like this:
@racketblock[
(struct Just (val) #:transparent)
(struct None () #:transparent)
(define (maybe-return item)
(Just item))
(define (maybe-bind monadic-value
monadic-function)
(match monadic-value
[(Just val)
(monadic-function val)]
[(None)
monadic-value]))
(define
the-maybe-monad
(monad maybe-bind maybe-return #f #f))]
Having done such, we may write:
@racketblock[
(mlet* in: the-maybe-monad
((y (Just 10))
(x (Just 11)))
(return (+ x y)))]
Which evaluates to @racket[(Just 21)]. We might also write:
@racketblock[
(mlet* in: the-maybe-monad
((y (Just 10))
(x (None))
(z (Just 13)))
(return (+ x y z)))]
Which will evaluate to @racket[(None)].
In this example, we bound the monad to a symbol, but monads may be
specified anonymously.
@subsection{Lagniappe (Bonus Features)}
It is often useful to bind values non-monadically during a monadic
expression. These can be introduced using the @racket[is:] syntax.
For instance:
@racketblock[
(mlet* in: the-list-monad
((x '(1 2 3))
(q is: (+ x 10))
(y '(a b c)))
(return (list q y)))]
Will produce @racket[(list (list 11 a) (list 11 b) ...)]. And so on.
The symbol @racket[q] is bound as in a @racket[let] expression for all
expressions subsequent. The binding symbol can also be a
@racket[match] pattern.
@section{Other Forms and Functions}
At the moment, the library provides a few extra functions and
features.
@subsection{monadic-do}
The form @racket[monadic-do] provides an alternative, more
Haskell-ish, monadic binding form. Each expression (except the last)
in the body of a @racket[monadic-do] must be either a binding
expression:
@racketblock[(pattern <- monadic-value)]
A "letting" expression:
@racketblock[(pattern is: expression)]
Or an expression resulting in a monadic value. The last expression in
a monadic-do form can't bind or let any variables, but must evaluate
to a monadic value. This version of the form might be more useful for
monads like the state monad which have many monadic values for which
the resulting binding isn't important.
Eg:
@racketblock[
(define (state-push value)
(lambda (state)
(state-doublet 'no-one-cares (cons value state))))
(define state-pop
(lambda (state)
(state-doublet (car state) (cdr state))))
(monadic-do in: the-state-monad
(state-push 10)
(state-push 13)
(y <- state-pop)
(state-push (+ y 100)))]
That is, we don't care about the value returned by @racket[state-push]
for binding in subsequent expressions. This form threads our values
through the monad, but lets us avoid the noise of providing dummy
variable names. Bindings to actual symbols is indicated specifically
by @racket[<-] for monadic binding and @racket[is:] for regular
binding.
@subsection{Bundled Monads}
The library comes with several monads pre-defined. We've seen most of
them already, but its worth remarking on a few peculiarities.
@subsubsection{The List Monad}
The list monad behaves just like the list monad in Haskell or any
other language, in that bind is essentially "map-cat". However,
unlike in Haskell, the list monad in this library will "return"
non-list values if they appear where a list should be. You can say,
eg:
@racketblock[
(mlet* in: the-list-monad
((x '(1 2 3))
(y 4))
(return (+ x y)))]
When "bind" encounters "4" either in a place where a monadic value or
monadic function should be, it replaces it with the "right" value
(either @racket[(list 4)] or @racket[(lambda (_) (list 4))],
respectively). If you want to return a list, you must @racket[return]
it explicitely. @margin-note{Being able to squeeze values into our
monad like this is a nice benefit of working with monads in a language
with run-time type-checking.}
@subsubsection{The State Monad}
The state monad is useful for constructing functions of state out of
smaller state functions. Monadic values in this monad are functions
which take a state and return a @racket[state-doublet] struct. The
first part of this doublet is the "proper return value" of the state
function, which is the value bound in binding expressions. The second
value is the modified state.
Like @racket[the-list-monad], @racket[the-state-monad] makes an
attempt treat unexpected values correctly. Literals are
@racket[return]ed into the monad if they appear where a monadic value
should be. Functions can return a simple value, rather than a
state-doublet, in which case the bind assumes that the intent was to
simple insert that value into the monad without modifying the
accumulating state.
State functions may also return either a @racket[state-fail] struct or
a @racket[(state-error error-value)] struct to indicate failure. Such
return values short-circuit all further state function bindings. For
the state monad, then, @racket[state-fail] is the monadic zero and
@racket[state-error] allows the monad to report errors.
@subsection{Other Utility Functions/Forms}
It is often convenient to "lift" a function into a monad. This is
provided for by a suite of lift functions. Because functions have
variable arity in Racket, you must specifiy the number of arguments to
lift over, although this can be specified at run time (unlike the
Clojure library), up to 20 arguments.
Eg:
@racketblock[
(define list+ (lift 2 + the-list-monad))
(list+ '(1 2 3) '(4 5 6))]
Short-cut functions of the form @racket[lift1],@racket[lift2] and so
on are also exported.
The library also exports @racket[mapm] and @racket[foldlm]. The
former takes a monadic function and a list of values and returns a
monadic function which returns the list resulting from monadically
binding those values through the monad.
The latter takes a monadic function, an initial state, and a list of
values and returns a monadic function which folds over those values in
the monad, returning a monadic value which is the result of that
folding. The function @racket[reducem] is the same, but assumes the
initial value is the @racket[car] of the list and folds over the
@racket[cdr].
@section{Functions/Values}
@defproc[(bind [monadic-value any/c] [monadic-function any/c])
[monadic-value any/c]]
Binds a @racket[monadic-value] to the free variable in the calculation
represented by the @racket[monadic-function]. User defined binds might
coerce either argument into an appropriate form, hence the weak contracts.
@defproc[(return [item any/c])
(monadic-value any/c)]
Inserts @racket[value] into the currently operating monad.
@defthing[zero any/c]
The currently defined monadic-zero, @racket[#f] if the zero is not defined.
@defproc[(plus [mval1 any/c] [mval2 any/c])
(mval any/c)]
Combines two monadic values, if the operating is meaningful in the
current monad. Will be @racket[#f] otherwise.
@defproc[(list-bind [lst (or/c list? any/c)] [list-fun (any/c . -> . (or/c list? any/c))])
(lst list?)]
The bind operation for the list monad. Applies the function @racket[list-fun] to
each item in @racket[lst], returns the concatenated result as a single list.
Non-list values are wrapped in lists if encountered.
@defproc[(list-return [item any/c])
(item-in-list list?)]
@defproc[(list-plus (a list?) (b list?))
(c list?)]
The list-monad plus procedure, equivalent to @racket[append].
@defthing[list-zero list?]
Is the empty list.
@defthing[the-list-monad monad?]
The list monad.
The return operation for the list monad. Puts @racket[item] into a list.
@defthing[the-identity-monad monad?]
The default monad, which does nothing.
@defproc[(state-return (item any/c))
(state-function (any/c . -> .
state-doublet?))]
The state monad return operation. Creates a state function which
leaves its input state unmodified and inserts @racket[item] into
the proper return value slot of a state doublet.
@defproc[(state-promote (object any/c))
(state-function
(any/c . -> .
(or/c state-doublet?
state-error?
state-fail?)))]
This function promotes non-monadic values into
monadic values in the state monad. This is applied
to objects before being passed to bind, so that the
user can specify simple values instead of wrapping
them with return.
Handles doublets, errors and failures correctly. "Returns"
all other values into the state monad.
@defproc[(state-promote-producer (object any/c))
(state-function-function
(any/c . -> .
(any/c . -> .
(or/c state-doublet?
state-error?
state-fail?))))]
Similar to @racket[state-promote] but wraps
object into another function so that the result
is a monadic function.
@defproc[(state-bind [val (or/c
(any/c . -> .
(or/c
state-doublet?
state-error?
state-fail?)))
any/c]
[fun
(or/c
(any/c . -> .
(any/c . -> .
(or/c
state-doublet?
state-error?
state-fail?))))])
(any/c . -> .
(or/c
state-doublet?
state-error?
state-fail?))]
The state-monad bind operation. Returns a new state function
which applies @racket[val] to the incoming state, extracts
the proper return value from the doublet, and creates and applies
a new state function to the new state. If either a @racket[state-error]
or @racket[state-fail] is encountered, it is passed through.
@defproc[(state-plus [sf1 (or/c
(any/c . -> .
(or/c
state-doublet?
state-error?
state-fail?)))]
[sf2 (or/c
(any/c . -> .
(or/c
state-doublet?
state-error?
state-fail?)))])
(sf (any/c . -> .
(or/c
state-doublet?
state-error?
state-fail?)))]
Combines two state functions into a third, which applies @racket[sf1],
ignores its output, and then applies and returns the result of @racket[sf2].
Errors/failures are handled correctly.
@defthing[state-zero
(any/c . -> .
state-fail?)]
The zero of the state monad. Always returns a @racket[state-fail] structure.
@defproc[(lift [n (and/c integer? positive?)]
[f procedure?]
[monad monad?])
(lf procedure?)]
Lifts @racket[f] into the monad @racket[monad]. The number of arguments
to lift must be provided in @racket[n].
@defproc[(mapm [monad monad?]
[f procedure?]
[lists list?] ...)
(monadic-value any/c)]
Create a monadic value in the specified @racket[monad] by applying
f to each of the arguments specified in @racket[lists] in turn. Return
a monadic value containing a list of the results.
@defproc[(foldlm [monad monad?]
[f (-> [item any/c] [acc any/c] [result any/c])]
[init any/c]
[lst list?])
(monadic-value any/c)]
Returns a monadic value in the @racket[monad] obtained
by applying the monadic function @racket[f] iteratively
to the items in list and an accumulator.
@defproc[(reducem [monad monad?]
[f (-> [item any/c] [acc any/c] [result any/c])]
[lst list?])
(monadic-value any/c)]
Like @racket[foldlm] but @racket[init] is taken to be
@racket[(car lst)] and the tail of the list is folded over.
@section{Structures}
@defstruct*[monad ([bind (any/c . -> . any/c)] [return (any/c . -> . any/c)] [plus (any/c . -> . any/c)] [zero any/c])]
The structure representing a monad.
@defstruct*[state-doublet ([proper-return-value any/c] [state any/c])]
Represents a value/state pair for the state monad.
@defstruct*[state-error ([error-string (or/c string? any/c)] [last-state any/c])]
Represents a state-monad error condition. The error string contains
information about the error, while @racket[last-state] is the last
state before the error.
@defstruct*[state-fail ()]
Completely dumb state error condition. Provides no error information.
Is the state monad's zero.
@section{Syntax}
@defform[#:id with-monad (with-monad monad body ...)]
Introduces a context for the expressions in @racket[body ...] in which
the appropriate values, @racket[bind], @racket[plus], @racket[zero], @racket[return],
and @racket[current-monad] are bound to the values specified in @racket[monad].
@defform[#:id mlet* #:literals (in:) (mlet* in: monad [binding ...] body ...)]
Monadic binding expression. Each binder must be either a @racket[(pattern value)]
pair, which binds and destructures monadically, or a @racket[(pattern is: value)]
triple which binds and destructures non-monadically. The body is finally evaluated,
returning the last value. This is almost always necessarily a monadic value.
The @racket[in: monad] part may be neglected, in which case the current lexical
@racket[current-monad] is used.
@defform[#:id monadic-do (monadic-do in: monad expr ...)]
Haskell-flavored monadic expression. Each @racket[expr] must be either
a monadic binding expression, like @racket[(pattern <- value)] which introduces
the bindings specified by @racket[pattern] through the monad @racket[monad],
a regular binding expression like @racket[(pattern is: value)] which does
a plain bind, or an expression resulting in a monadic value. The final @racket[expr]
must be a monadic value, not a binding form.
As in @racket[mlet*], the @racket[in: monad] may be neglected, in which
case the current lexically bound @racket[current-monad] is used.
@section{Conclusions}
This should be enough to get you going. Enjoy the monads!