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

> (?+ 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!