BLOG

# More Fun with Monad Do-notation in Scheme

In a previous post, I played around with monad do-notation in Scheme (well, Racket) to have a nicer syntax to play with asynchronous callbacks. This do-notation is actually quite fun to use with other monads as well. What’s interesting is that the same notation gets entirely different meanings and forms depending on which monad you use it with.

There are many interesting monads, and this post shows only a couple of simple ones in action in Scheme (for which you can find the code here). If you want a much better description and in-depth of these monads (and more), I highly recommend you read the awesome Learn You a Haskell for Great Good!

## Generalizing the async do-notation

In the previous post on the async monad, we introduced
do-notation for callbacks in Scheme by defining the monad operations
`return`

and `bind`

for our callback type (which we called `async`

), and define
a `async-do`

macro that used these operations to combine callbacks into a chain. The
basic `async-do`

macro didn’t rely on anything async-specific, only on the `async-bind`

monad operation; the fancier version that automatically created asyncs for
non-async values (aka *lifting* the value into the monad) also
depended on the `async?`

check and the `return`

monad operation.

This means we can generalize all `*-do`

macros that work on monads into a
generic `monad-do`

. In Haskell, the type inferencer can decide which version of the
monad operators to choose based on the type of the context where it is used; since we can’t do this in a dynamic
language like scheme, we instead need to explicitly provide the type-specific operators
as a first argument to the `do`

macro, and thread them through wherever they are needed (which I believe is basically what Haskell does during compilation as well).

The simple version of the generic `monad-do`

macro only needs the `bind`

operator (which we name `>>=`

) passed in as a parameter:

```
; Generic macro for *-do notation.
; The first parameter of the macro (`>>=) is the monad-specific
; `bind` operator.
(define-syntax monad-do
(syntax-rules (<-)
[(_ (>>=) e) e]
[(_ (>>=) (<- var e1) e2 ...)
(>>= e1 (λ (var) (monad-do (>>=) e2 ...)))]
[(_ (>>=) e1 e2 ...)
(>>= e1 (λ (_) (monad-do (>>=) e2 ...)))]))
```

The fancy auto-lift version also requires the `return`

and `monad?`

to be passed in as
parameters (and threaded through to the `->monad`

conversion macro):

```
; Generic macro for *-do notation.
; The first parameter of the macro are the monad-specific
; operations.
(define-syntax monad-do
(syntax-rules (<-)
[(_ (return >>= monad?) e)
(->monad (return monad?) e)]
[(_ (return >>= monad?) (<- var e1) e2 ...)
(>>= (->monad (return monad?) e1)
(λ (var) (monad-do (return >>= monad?) e2 ...)))]
[(_ (return >>= monad?) e1 e2 ...)
(>>= (->monad (return monad?) e1)
(λ (_) (monad-do (return >>= monad?) e2 ...)))]))
; Lift non-monadic values into the monad if necessary
; The first parameter of the macro is the monad-specific
; type check and `return` operation
(define-syntax ->monad
(syntax-rules ()
[(_ (return monad?) e)
(let ([e-result e])
(if (monad? e-result)
e-result
(return e-result)))]))
```

We can either use this `monad-do`

macro directly as a replacement for `async-do`

:

```
(monad-do (async-return async-bind async?)
(do-something-first)
(<- foo (fetch "foo"))
(do-something-with foo)
(<- bar (fetch "bar"))
(do-something-else)
(<- baz (fetch "baz"))
(do-something-with foo baz)))
```

or redefine the `async-do`

macro in terms of `monad-do`

:

```
(define-syntax async-do
(syntax-rules ()
[(_ e ...)
(monad-do (async-return async-bind async?) e ...)]))
(async-do
(do-something-first)
(<- foo (fetch "foo"))
(do-something-with foo)
(<- bar (fetch "bar"))
(do-something-else)
(<- baz (fetch "baz"))
(do-something-with foo baz))
```

With this generic `monad-do`

, we can now experiment with other monads.

## The Maybe monad: Computations with optional results

The *Maybe* type from Haskell is similar to the *Optional* type in languages such as
Java or Swift. A simple definition of it in Racket could look like this:

```
(struct maybe (value? value))
(define (just value)
(maybe #t value))
(define (nothing)
(maybe #f #f))
(define (nothing? m)
(not (maybe-value? m)))
```

Maybe can also be used as a monad. The `return`

operation is the same as the `just`

constructor,
and the bind operation simply applies the given function to the `maybe`

's value if there
is one:

```
(define (maybe-bind m f)
(if (maybe-value? m)
(f (maybe-value m))
(nothing)))
(define-syntax maybe-do
(syntax-rules ()
[(_ e ...)
(monad-do (just maybe-bind maybe?) e ...)]))
```

This monad represents computations that may fail (and therefore not return a value).
For example, we can define a potentially failing version of `+`

:

```
(define (?+ ?x ?y)
(maybe-do
(<- x ?x)
(<- y ?y)
(+ x y)))
```

The potentially failing `?+`

takes 2 `maybe`

values as parameters, extracts the
actual values out of them (if they have them), and adds them together into a new `maybe`

.
If one of the parameters doesn’t have a value, the `maybe-do`

block is aborted and returns
a `nothing`

. For example:

```
> (?+ (just 4) (just 5))
(maybe #t 9)
> (?+ (just 4) (nothing))
(maybe #f #f)
```

Because our `do`

macro auto-lifts, we can even pass in regular values
instead of always wrapping them in `maybe`

s:

```
> (?+ 4 5)
(maybe #t 9)
```

We can also define a `?/`

operator that returns `nothing`

for divisions by zero:

```
(define (?/ ?x ?y)
(maybe-do
(<- x ?x)
(<- y ?y)
(if (= y 0)
(nothing)
(/ x y))))
```

And use it in computations:

```
> (?/ 8 0)
(maybe #f #f)
> (?+ 2 (?/ 8 0))
(maybe #f #f)
```

Again, because the inner `?/`

in the last example generated no result, the last
computation short-circuited the `?+`

and no value is returned.

## The Error monad: Simple Error handling

The Maybe monad chains operations that can fail, but doesn’t return any failure reason. A logical extension is to add a reason, which is exactly what the Error monad does.

To use it, we introduce a simple datatype for representing an either succesful result with a value, or an error result with a reason, which we will return in our potentially failing functions.

```
(struct result (error value) #:transparent)
(define (error-result reason)
(result reason #f))
(define (value-result value)
(result #f value))
(define (error-result? r)
(result-error r))
(define (value-result? r)
(not (error-result? r)))
```

The monad operations for this result type are very similar to the Maybe ones:

```
(define (result-bind r f)
(if (value-result? r)
(f (result-value r))
r))
(define-syntax result-do
(syntax-rules ()
[(_ e ...) (monad-do (value-result result-bind result?) e ...)]))
```

New we can define a potentially failing version of `/`

, called `!/`

:

```
(define (!/ x y)
(if (= y 0)
(error-result "Division by zero")
(value-result (/ x y))))
```

And play around with it first:

```
> (!/ 8 4)
(result #f 4)
> (!/ 8 0)
(result "Division by zero" #f)
```

We can also use this in more complex computation functions, where each step extracts the value out of potentially failing operations.

```
(define (get-magic-number x y)
(result-do
(<- a (- x y))
(<- b (!/ x a))
(+ b a)))
(define (get-super-magic-number x y)
(result-do
(<- a (* x y))
(<- b (get-magic-number x y))
(- b a)))
```

If one of the operation fails, the other ones are skipped, and the result is an error value:

```
> (get-magic-number 2 2)
(result "Division by zero" #f)
```

Failures at deeper levels get propagated all the way up:

```
> (get-super-magic-number 2 2)
(result "Division by zero" #f)
```

You could define a `try`

operation, which catches the result of a sequence of
computations if it fails:

```
(define (try result handler)
(if (error-result? result)
(handler (result-error result))
(result-value result)))
(define (safe-get-super-magic-number x y)
(try
(result-do
(<- a (* x y))
(<- b (get-magic-number x y))
(- b a))
(λ (e)
(display "Error occurred: ") (display e) (newline)
-1)))
```

```
> (safe-get-super-magic-number 2 2)
Error occurred: Division by zero
-1
> (safe-get-super-magic-number 3 2)
-2
```

So, the error monad gives you an imperative notation for simple error handling, not unlike the mechanism used in Swift.

## The List monad: Non-deterministic computations

The final one is a bit mind-bending: the list type can *also* be used as a monad. Since
`return`

is simply the `list`

constructor, this only leaves `list-bind`

to be defined:

```
(define (list-bind xs f)
(append* (map f xs)))
(define-syntax list-do
(syntax-rules ()
[(_ e ...)
(monad-do (list list-bind list?) e ...)]))
```

Contrary to the Maybe monad representing chains of potentially failing computations,
this list monad represents chaining of *non-deterministic* computations.
For example, take the following definition (using the do-notation for the list monad):

```
(define my-pair-list
(list-do
(<- n '(1 2))
(<- ch '("a" "b"))
(cons n ch)))
```

This assigns a non-deterministic value from the list `(1 2)`

to `n`

, then a value of
`("a" "b")`

to ch, and then combines both into a pair. The result of the entire block
is a list of all possible pairs:

```
> my-pair-list
'((1 . "a") (1 . "b") (2 . "a") (2 . "b"))
```

So, in this context, the do-notation took the form of a list comprehension! The only thing missing is a way to filter values, but it turns out this is easy too. I’ll skip the rationale here, but all you need is a guard function that returns the empty list if the guard fails, or a singleton if the guard succeeds:

```
(define (where x)
(if x (list (void)) '()))
(define my-pair-list
(list-do
(<- x (range 0 4))
(<- y (range 0 4))
(where (< x y))
(cons x y)))
> my-pair-list
'((0 . 1) (0 . 2) (0 . 3)
(1 . 2) (1 . 3)
(2 . 3))
```

Monads just blow my mind!