## 2010 August 25

### Fun with the Lazy State Monad, Part 2

Filed under: Uncategorized — lpsmith @ 5:52 am

In a previous post, I demonstrated how to use the lazy state monad to turn Geraint Jones and Jeremy Gibbon’s breadth-first labeling algorithm into a reusable abstraction, and mentioned that I did not know how to combine the result with continuations. In this post, I will do exactly that.

A hat tip goes to Twan van Laarhoven for suggesting that I split my `fresh` operator into two, which I adopt in this post. In the comments, `down` is defined as:

```type Fresh n a = State [n] a

down :: Fresh n a -> Fresh n a
down m = do
(n:ns) <- get
put ns
a <- m
ns' <- get
put (n:ns')
return a```

Now, if we naïvely apply the continuation transformer in the Monad Transformer Library, the `get` and `put` operators are lifted as follows:

```type FreshCC r n a = ContT r (State [n]) a

lift :: Monad m => m a -> ContT r m a
lift m = ContT (m >>=)

down :: FreshCC r n a -> FreshCC r n a
down m = do
(n:ns) <- lift get
lift (put ns)
a <- m
ns' <- lift get
lift (put (n:ns'))
return a```

The problem is that this replaces the `>>=` of the lazy state monad with the `>>=` of the continuation transformer, and these two operators have different strictness properties. This, in turn, leads to non-termination. The trick is not to lift `get` and `put`, but rather conjugate `down`:

```lower :: Monad m => ContT a m a -> m a
lower m = runContT m return

down :: FreshCC a n a -> FreshCC r n a
down m = lift \$ do
(n:ns) <- get
put ns
a <- lower m
ns' <- get
put (n:ns')
return a

-- *or*

down = lift . original_down . lower```

Now, the conjugation preserves the use of the lazy state monad’s `>>=` in the definition of `down`, however it changes the type of the argument from `FreshCC r n a` to `FreshCC a n a`! The other definitions contained in the previous post stay much the same.

Feel free to download freshcc.hs, a full working demonstration of this post. One can even use `callCC`, `fresh`, and `down` in the same computation and terminate! Sadly, I don’t have any demonstrations of this combination, nor do I have any applications in mind. My intuition about `callCC` is currently quite limited in this context.

I have implemented Dan Friedman’s angel-devil-milestone control operators in conjunction with fresh and down, and have used it to duplicate labels and change the shape of a spirited tree; but I’m definitely cheating at this point, as all I have done is observe that the definitions compute something. I have no control over what’s going on, nor do I know what the definitions are supposed to compute. (yet)