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)
Leave a Reply