我怎样才能用延续来实现这个 monad 转换器？

Question

动机。我正在尝试创建一个 monad 转换器，并使用特殊指令 f <||> g 表示“重复包含 f <||> g 的整个块，一次使用 f，下一次使用 g代码>”。这旨在用于 DSL 转换，但您可以想象其他应用程序。

示例用法。 computation monad 表达了不同的可能选择（在本例中，是要打印的内容）。 printme 函数说明如何处理每个不同的结果。在这种情况下，我们在运行之前打印“开始计算”，在运行之后打印“---”。

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

输出如下，

=== 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"
---

问题。有没有一种干净的方法来使用某种连续传递风格的 monad 转换器来实现上述行为？我看过 Oleg 等人的“回溯、交错和终止 Monad Transformers”论文，但似乎无法完全掌握他们的实现（一旦他们到达带有延续的 msplit 实现） ）。

当前实现。我当前的实现是传递要做出的分支决策列表。 monad 将返回它实际选择的分支列表，然后下次我们将切换最后一个可能的分支。代码如下（应该在7.0.3中运行），

import Control.Monad.Trans.Class

data IndepModelT 
              

Answer 1

问题是：这不是一个 monad！该行为甚至没有明确定义。 Fe 在这种情况下应该做什么：

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

但是，它是Applicative。我们需要的类型是[IO a]，它是2个applicative functor的组合，所以我们可以使用Data.Functor.Compose 来自变压器包。这也免费提供了带有 <|> 的 Alternative 实例。我们将使用可重新绑定语法来使用 Applicatives 的 do 表示法：

{-# 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

Answer 2

到目前为止您收到的建议不起作用。这是如何进行的：

f <||> g = ContT $ \k -> do
  xs <- runContT f k
  ys <- runContT g k
  return $ xs ++ ys

test = runContT computation (return . (:[]))

但这不会为每个选择重新启动整个计算，结果是这样的：

"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"

我还没有找到一个好的解决方案。

Answer 3

如果您专门寻找基于延续的方法，那么您不会比 LogicT 论文。

如果 msplit 太多（而且它是一个非常微妙的野兽），您可以在此应用程序中忽略它。其目的是允许公平的结合和析取，如果这些示例输出行要按顺序打印，那么这不是您的规范的一部分。只需关注 5.1 节中的 Monad 和 MonadPlus 实现即可。

更新：正如 Sjoerd Visscher 指出的那样，这是不对的，因为重新启动仅发生在 mplus 中，而不是整个计算中。这是一个比乍一看要棘手得多的问题。