how can I implement this monad transformer with a continuation?

Question

motivation. I'm trying to create a monad transformer, with a special instruction f <||> g that means "repeat this entire block containing f <||> g, once with f, the next time with g". This is intended to be for a DSL transformation, though you can imagine other applications.

example usage. The computation monad expresses different possible choices (in this case, of things to print). The printme function says what to do with each different result. In this case, we print "start computation" before it runs, and "---" after.

computation = do lift (print "start -- always") (lift (print "first choice") <||> lift (print "second choice")) lift (print "intermediate -- always") (lift (print "third choice") <||> lift (print "fourth choice")) lift (print "end -- always") printme x = do putStrLn "=== start computation" xv <- x putStrLn "---\n" return xv test = runIndep printme computation

the output is as follows,

=== start computation "start -- always" "first choice" "intermediate -- always" "third choice" "end -- always" --- === start computation "start -- always" "first choice" "intermediate -- always" "fourth choice" "end -- always" --- === start computation "start -- always" "second choice" "intermediate -- always" "third choice" "end -- always" --- === start computation "start -- always" "second choice" "intermediate -- always" "fourth choice" "end -- always" ---

question. Is there a clean way to achieve the above behavior using some kind of continuation passing style monad transformer? I've looked at Oleg et al.'s "Backtracking, Interleaving, and Terminating Monad Transformers" paper, but can't seem to fully grasp their implementation (once they get to the msplit implementation with continuations).

current implementation. My current implementation is to pass in a list of branching decisions to be made. The monad will return the a list of the branches it actually chooses, and then next time we'll switch the last possible branch. The code is as follows (should run in 7.0.3),

import Control.Monad.Trans.Class data IndepModelT 𝔪 α = IndepModelT { unIndepModelT :: [Bool] -> 𝔪 (α, [Bool]) } instance Monad 𝔪 => Monad (IndepModelT 𝔪) where return x = IndepModelT $ \choices -> return (x, []) (IndepModelT x) >>= f = IndepModelT $ \choices -> do (xv, branches) <- x choices let choices' = drop (length branches) choices (fxv, branches') <- unIndepModelT (f xv) choices' return (fxv, branches ++ branches') instance MonadTrans IndepModelT where lift x = IndepModelT $ \c -> liftWithChoice [] x liftWithChoice cs mx = mx >>= \xv -> return (xv, cs) (<||>) :: Monad 𝔪 => IndepModelT 𝔪 α -> IndepModelT 𝔪 α -> IndepModelT 𝔪 α (IndepModelT f) <||> (IndepModelT g) = IndepModelT go where go (False:cs) = do (fv, branches) <- f cs return (fv, False : branches) go (True:cs) = do (fv, branches) <- g cs return (fv, True : branches) run_inner next_choices k comp@(IndepModelT comp_inner) = do (xv, branches) <- k $ comp_inner next_choices case (get_next_choices branches) of Nothing -> return () Just choices -> run_inner (choices ++ repeat False) k comp where get_next_choices [] = Nothing get_next_choices [True] = Nothing get_next_choices [False] = Just [True] get_next_choices (c:cs) | Just cs' <- get_next_choices cs = Just $ c:cs' | c Prelude.== False = Just [True] | otherwise = Nothing runIndep :: Monad 𝔪 => (𝔪 (α, [Bool]) -> 𝔪 (β, [Bool])) -> IndepModelT 𝔪 α -> 𝔪 () runIndep = run_inner (repeat False) runIndepFirst (IndepModelT comp) = comp (repeat False)

Have you seen haskell.org/haskellwiki/ListT_done_right , and in particular the alternative implementation haskell.org/haskellwiki/ListT_done_right_alternative ? — John L
– John L, Commented Dec 5, 2011 at 0:44
I don't think you need continuations. What you seem to have is a kind of tree, where each <||> operation represents a branch. But I can't figure out the right data type. — Paul Johnson
– Paul Johnson, Commented Dec 5, 2011 at 11:58

Sjoerd Visscher · Accepted Answer · 2011-12-06 12:34:31Z

Here's the problem: this is not a monad! The behavior isn't even well-defined. F.e. what should it do in this case:

do b <- ...randomly True or False... if b then ...some choices... else ...some other choices...

However, it is Applicative. The type we need is [IO a], which is the composition of 2 applicative functors, so we can use Data.Functor.Compose from the transformers package. This gives an Alternative instance with <|> for free as well. We'll use Rebindable Syntax to use the do-notation for Applicatives:

{-# LANGUAGE RebindableSyntax #-} import Prelude hiding ((>>), (>>=)) import Control.Applicative import Data.Functor.Compose lift :: Applicative f => g a -> Compose f g a lift = Compose . pure (>>) :: Applicative f => f a -> f b -> f b (>>) = (*>) computation :: Alternative f => Compose f IO () computation = do lift (print "start -- always") lift (print "first choice") <|> lift (print "second choice") lift (print "intermediate -- always") lift (print "third choice") <|> lift (print "fourth choice") lift (print "end -- always") printme x = do putStrLn "=== start computation" x putStrLn "---\n" test = mapM printme $ getCompose computation

Sjoerd Visscher · Accepted Answer · 2011-12-05 10:27:42Z

The suggestion you've gotten so far don't work. Here's how that would go:

f <||> g = ContT $ \k -> do xs <- runContT f k ys <- runContT g k return $ xs ++ ys test = runContT computation (return . (:[]))

But that doesn't restart the whole computation for each choice, the result is this:

"start -- always" "first choice" "intermediate -- always" "third choice" "end -- always" "fourth choice" "end -- always" "second choice" "intermediate -- always" "third choice" "end -- always" "fourth choice" "end -- always"

I haven't found a good solution yet.

Indeed, thanks for pointing it out. @John L's suggestion of the "ListT done right" transformer looks better for rerunning the whole computation, but I should cons up a test program.

acfoltzer · Accepted Answer · 2011-12-05 14:10:40Z

If you're looking specifically for a continuation-based approach, you're not going to get much simpler than the SFKT success/failure continuation implementation in the LogicT paper.

If msplit is too much (and it is quite a subtle beast), you can just ignore it for this application. Its purpose is to allow fair conjunction and disjunction, which isn't part of your specification if those lines of sample output are meant to print in order. Just focus on the Monad and MonadPlus implementations in section 5.1 and you'll be all set.

Update: As Sjoerd Visscher points out, this isn't right as the restarting only happens from mplus rather than the whole computation. This is a much trickier problem than it appears at first read.

Collectives™ on Stack Overflow

how can I implement this monad transformer with a continuation?

3 Answers 3

Comments

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Related