Better Monads

(require 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.

1 Usage

What follows is a brief tutorial on the usage of this library.

1.1 mlet*

The most important special form in the library is the 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 mlet* expression, and hence mlet* is very similar to let*, in that it takes a series of binding pairs and then evaluates a body of expressions, as in a begin form.

In fact, at the top level, mlet* behaves identically to let*:

(require functional/better-monads)

(mlet* ((x 10)

(y 11))

(+ x y))

By default, mlet* performs its bindings in whatever monad is stored in the lexical variable current-monad, which Better Monads exports as the identity monad (also available in the variable 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:

(struct doublet (a b))

(mlet* (((list x y) (list 1 2))

((doublet q r) (doublet 100 101)))

(list x y q r))

Will return '(1 2 100 101).

1.2 Working with a Monad

Besides extending let* with pattern matching, the library doesn’t do much until you start using monads other than the-identity-monad. Alternative monads are introduced using the in: option in mlet*. For instance:

(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:

(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 x and y, which is the behavior of the-list-monad.

Note the use of the function return in the body of the mlet* expression. In the context of an mlet* expression, the symbosl bind, and return are bound to the appropriate functions in the specified monad. If the monad also defines plus and/or zero, these will also be appropriately bound. Otherwise they will be bound to #f. In the lexical scope of an mlet* expression, the current-monad will be bound to the monad specified after in:.

1.3 Defining Additional Monads

The use may define her own monads by creating an instance of the monad structure. For instance, we might define the "maybe" monad like this:

(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:

(mlet* in: the-maybe-monad

((y (Just 10))

(x (Just 11)))

(return (+ x y)))

Which evaluates to (Just 21). We might also write:

(mlet* in: the-maybe-monad

((y (Just 10))

(x (None))

(z (Just 13)))

(return (+ x y z)))

Which will evaluate to (None).

In this example, we bound the monad to a symbol, but monads may be specified anonymously.

1.4 Lagniappe (Bonus Features)

It is often useful to bind values non-monadically during a monadic expression. These can be introduced using the is: syntax. For instance:

(mlet* in: the-list-monad

((x '(1 2 3))

(q is: (+ x 10))

(y '(a b c)))

(return (list q y)))

Will produce (list (list 11 a) (list 11 b) ...). And so on. The symbol q is bound as in a let expression for all expressions subsequent. The binding symbol can also be a match pattern.

2 Other Forms and Functions

At the moment, the library provides a few extra functions and features.

2.1 monadic-do

The form monadic-do provides an alternative, more Haskell-ish, monadic binding form. Each expression (except the last) in the body of a monadic-do must be either a binding expression:

(pattern <- monadic-value)

A "letting" expression:

(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:

(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 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 <- for monadic binding and is: for regular binding.

2.2 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.

2.2.1 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:

(mlet* in: the-list-monad

((x '(1 2 3))

(y 4))

(return (+ x y)))

2.2.2 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 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 the-list-monad, the-state-monad makes an attempt treat unexpected values correctly. Literals are returned 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 state-fail struct or a (state-error error-value) struct to indicate failure. Such return values short-circuit all further state function bindings. For the state monad, then, state-fail is the monadic zero and state-error allows the monad to report errors.

2.3 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:

(define list+ (lift 2 + the-list-monad))

(list+ '(1 2 3) '(4 5 6))

Short-cut functions of the form lift1,lift2 and so on are also exported.

The library also exports mapm and 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 reducem is the same, but assumes the initial value is the car of the list and folds over the cdr.

3 Functions/Values

(bind monadic-value monadic-function) → [monadic-value any/c]

monadic-value : any/c

monadic-function : any/c

Binds a monadic-value to the free variable in the calculation represented by the monadic-function. User defined binds might coerce either argument into an appropriate form, hence the weak contracts.

(return item) → (monadic-value any/c)

item : any/c

Inserts value into the currently operating monad.

zero : any/c

The currently defined monadic-zero, #f if the zero is not defined.

(plus mval1 mval2) → (mval any/c)

mval1 : any/c

mval2 : any/c

Combines two monadic values, if the operating is meaningful in the current monad. Will be #f otherwise.

(list-bind lst list-fun) → (lst list?)

lst : (or/c list? any/c)

list-fun : (any/c . -> . (or/c list? any/c))

The bind operation for the list monad. Applies the function list-fun to each item in lst, returns the concatenated result as a single list. Non-list values are wrapped in lists if encountered.

(list-return item) → (item-in-list list?)

item : any/c

(list-plus a b) → (c list?)

a : list?

b : list?

The list-monad plus procedure, equivalent to append.

list-zero : list?

Is the empty list.

the-list-monad : monad?

The list monad.

The return operation for the list monad. Puts item into a list.

the-identity-monad : monad?

The default monad, which does nothing.

(state-return item)   →   (state-function (any/c . -> .                        state-doublet?))

item : any/c

The state monad return operation. Creates a state function which leaves its input state unmodified and inserts item into the proper return value slot of a state doublet.

(state-promote object)   →   (state-function  (any/c . -> .         (or/c state-doublet?               state-error?               state-fail?)))

object : any/c

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.

(state-promote-producer object)

→   (state-function-function  (any/c . -> .         (any/c . -> .                (or/c state-doublet?               state-error?               state-fail?))))

object : any/c

Similar to state-promote but wraps object into another function so that the result is a monadic function.

(state-bind [val] fun)

→   (any/c . -> .                             (or/c                              state-doublet?                              state-error?                              state-fail?))

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?))))

The state-monad bind operation. Returns a new state function which applies 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 state-error or state-fail is encountered, it is passed through.

(state-plus sf1 sf2)   →   (sf (any/c . -> .                          (or/c                           state-doublet?                           state-error?                           state-fail?)))

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?)))

Combines two state functions into a third, which applies sf1, ignores its output, and then applies and returns the result of sf2. Errors/failures are handled correctly.

state-zero  :  (any/c . -> .         state-fail?)

The zero of the state monad. Always returns a state-fail structure.

(lift n f monad) → (lf procedure?)

n : (and/c integer? positive?)

f : procedure?

monad : monad?

Lifts f into the monad monad. The number of arguments to lift must be provided in n.

(mapm monad f lists ...) → (monadic-value any/c)

monad : monad?

f : procedure?

lists : list?

Create a monadic value in the specified monad by applying f to each of the arguments specified in lists in turn. Return a monadic value containing a list of the results.

(foldlm monad f init lst) → (monadic-value any/c)

monad : monad?

f : (-> [item any/c] [acc any/c] [result any/c])

init : any/c

lst : list?

Returns a monadic value in the monad obtained by applying the monadic function f iteratively to the items in list and an accumulator.

(reducem monad f lst) → (monadic-value any/c)

monad : monad?

f : (-> [item any/c] [acc any/c] [result any/c])

lst : list?

Like foldlm but init is taken to be (car lst) and the tail of the list is folded over.

4 Structures

(struct monad (bind return plus zero))

bind : (any/c . -> . any/c)

return : (any/c . -> . any/c)

plus : (any/c . -> . any/c)

zero : any/c

The structure representing a monad.

(struct state-doublet (proper-return-value state))

proper-return-value : any/c

state : any/c

Represents a value/state pair for the state monad.

(struct state-error (error-string last-state))

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 last-state is the last state before the error.

(struct state-fail ())

Completely dumb state error condition. Provides no error information. Is the state monad’s zero.

5 Syntax

(with-monad monad body ...)

Introduces a context for the expressions in body ... in which the appropriate values, bind, plus, zero, return, and current-monad are bound to the values specified in monad.

(mlet* in: monad [binding ...] body ...)

Monadic binding expression. Each binder must be either a (pattern value) pair, which binds and destructures monadically, or a (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 in: monad part may be neglected, in which case the current lexical current-monad is used.

(monadic-do in: monad expr ...)

Haskell-flavored monadic expression. Each expr must be either a monadic binding expression, like (pattern <- value) which introduces the bindings specified by pattern through the monad monad, a regular binding expression like (pattern is: value) which does a plain bind, or an expression resulting in a monadic value. The final expr must be a monadic value, not a binding form.

As in mlet*, the in: monad may be neglected, in which case the current lexically bound current-monad is used.

6 Conclusions

This should be enough to get you going. Enjoy the monads!