Haskell Cont monad如何以及为何工作？

Question

这是续单子是如何定义的：

newtype Cont r a = Cont { runCont :: (a -> r) -> r } 

instance Monad (Cont r) where 
    return a = Cont ($ a) 
    m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c 

你能解释一下如何以及为什么这个工程？它在做什么？

Answer 1

关于延续monad的第一件事情是，从根本上说，它并不是真的做什么都没有。这是真的！

继续的基本思想一般是它代表计算的其余部分。假设我们有这样一个表达式：foo (bar x y) z。现在，只提取括号内的部分，bar x y - 这是部分的总表达式，但它不仅仅是我们可以应用的函数。相反，这是我们需要应用功能到。因此，在这种情况下，我们可以谈论“其余计算”为\a -> foo a z，我们可以将其应用于bar x y以重建完整的表单。

现在，这种“剩余计算”的概念很有用，但是使用起来很尴尬，因为它是我们正在考虑的子表达式之外的东西。为了让事情变得更好，我们可以将事情从内到外：提取我们感兴趣的子表达式，然后将其包含在一个函数中，该函数接受一个表示其余计算的参数：\k -> k (bar x y)。

这个修改后的版本给我们带来了很大的灵活性 - 它不仅提取及其上下文的子表达式，但它让我们操纵子表达式本身内外部环境。我们可以认为它是一种暂停计算，给我们明确控制接下来会发生什么。现在，我们怎么概括这个？那么，这个子表达式几乎没有改变，所以让我们用一个参数替换它，然后给我们\x k -> k x--换句话说，只不过是功能应用，反转。我们可以轻松地编写flip ($)，或添加一些异国情调的外语风格，并将其定义为运营商|>。

现在，将每一个表达片段翻译成这种形式简单，尽管繁琐且令人生畏地混淆。幸运的是，还有更好的方法。作为Haskell程序员，当我们认为在后台上下文中构建计算接下来我们认为是说，这是一个单子吗？而在这种情况下，答案是是的，是的。

要变成一个单子，我们开始具有两个基本组成部分：

• 对于单子m，m a类型的值表示单子的范围内具有访问a类型的值。
• 我们的“暂停计算”的核心是翻转函数应用程序。

在这种情况下访问a类型的东西是什么意思？这仅表示对于某些值x :: a，我们已应用flip ($)至x，给我们一个函数，该函数采用一个函数，该函数采用类型为a的参数，并将该函数应用于x。假设我们有一个暂停的计算，其值为Bool。这给了我们什么类型？

> :t flip ($) True 
flip ($) True :: (Bool -> b) -> b 

所以对暂停计算，m a工程以(a -> b) -> b ...这也许是一个虎头蛇尾的，因为我们已经知道了签名Cont对于现在的类型，但我的幽默。

一个有趣的事情，这里要注意的是，一种“逆转”也适用于单子的类型：Cont b a代表一个函数，函数a -> b和评估为b。作为延续表示计算的“未来”，因此签名中的a代表某种意义上的“过去”。

因此，用Cont b a替换(a -> b) -> b，我们的反函数应用的基本构建块的monadic类型是什么？ a -> (a -> b) -> b转换为a -> Cont b a ...与return相同的类型签名，实际上，这正是它的原因。

从这里开始，一切都差不多从类型中去除了：除了实际的实现之外，基本上没有明智的方法来实现>>=。但究竟是做？

在这一点上我们回到我刚才说的话：延续单子并不是真的做什么都没有。 Cont r a类型的东西只是简单地通过将id作为参数提供给挂起的计算而简单地等同于a类型的东西。这可能会导致人们询问，如果Cont r a是一个monad但转换是如此微不足道，不应该单独a也成为monad？当然，这不起作用，因为没有类型构造函数来定义为Monad实例，但是说我们添加了一个简单的包装，如data Id a = Id a。这确实是一个monad，即身份monad。

>>=对身份monad做什么？类型签名是Id a -> (a -> Id b) -> Id b，相当于a -> (a -> b) -> b，这只是简单的函数应用程序。确定Cont r a简直等于Id a，我们可以推断在这种情况下，(>>=)只是功能应用。

当然，Cont r a是一个疯狂倒立的世界里，每个人都有山羊胡，所以实际发生周围混淆的方式，以链上的两个暂停的计算涉及到洗牌的东西放在一起进入一个新的暂停计算，但在本质上，ISN实际上什么都不正常！将函数应用于参数，哼哼，功能程序员生活中的另一天。

Answer 2

编辑：文章迁移到下面的链接。

我已经写了一个教程直接解决这个问题，我希望你会觉得有用。 （这当然有助于巩固我的理解！）在堆栈溢出主题中放置一段时间太长了，所以我将它移植到了Haskell Wiki。

请参阅：MonadCont under the hood

Answer 3

这里的斐波那契数：

fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

想象一下，你有一台机器没有调用栈 - 只允许尾递归。如何在该机器上执行fib？您可以轻松地将函数重写为线性工作，而不是指数时间，但这需要一点洞察力，而且不是机械的。

使其尾递归的障碍是第三行，其中有两个递归调用。我们只能打一个电话，也必须给出结果。这里是延续输入的地方。

我们将fib (n-1)作为附加参数，这是一个函数，指定在计算结果后应该做些什么，称之为x。当然，它会增加。所以：要计算fib n那么你在那之后计算fib (n-1)，如果你调用结果x，则计算，之后，如果你调用结果y，则返回x+y。

在你要告诉换句话说：

如何做好以下计算：“fib' n c =计算fib n和应用c到结果”？

答案是，你做了以下内容：“计算fib (n-1)和应用d的结果”，其中d x的意思是“计算和应用e的结果”，其中e y意味着c (x+y)。在代码：

fib' 0 c = c 0 
fib' 1 c = c 1 
fib' n c = fib' (n-1) d 
      where d x = fib' (n-2) e 
       where e y = c (x+y) 

同样地，我们可以使用lambda表达式：

fib' 0 = \c -> c 0 
fib' 1 = \c -> c 1 
fib' n = \c -> fib' (n-1) $ \x -> 
       fib' (n-2) $ \y -> 
       c (x+y) 

要获得实际的斐波那契使用身份：fib' n id。您可以认为行fib (n-1) $ ...将其结果x传递给下一个。

最后三行闻起来像do块，而事实上

fib' 0 = return 0 
fib' 1 = return 1 
fib' n = do x <- fib' (n-1) 
      y <- fib' (n-2) 
      return (x+y) 

是一样的，最多newtypes，由单子Cont的定义。注意差异。在开头有\c ->，而不是x <- ...有... $ \x ->和c而不是return。

尝试使用CPS以尾部递归样式编写factorial n = n * factorial (n-1)。

>>=如何工作？m >>= k相当于

do a <- m 
    t <- k a 
    return t 

使得翻译回来，在相同的风格在fib'，你

\c -> m $ \a -> 
     k a $ \t -> 
     c t 

简化\t -> c t到c

m >>= k = \c -> m $ \a -> k a c 

添加newtypes你

m >>= k = Cont $ \c -> runCont m $ \a -> runCont (k a) c 

这是在这个页面的顶部。这很复杂，但如果您知道如何在do表示法和直接使用之间进行翻译，则无需知道>>=的确切定义！如果你看看do-blocks，继续单子更清晰。

单子和延续

如果你看看这个使用列表单子...

do x <- [10, 20] 
    y <- [3,5] 
    return (x+y) 

[10,20] >>= \x -> 
    [3,5] >>= \y -> 
    return (x+y) 

([10,20] >>=) $ \x -> 
    ([3,5] >>=) $ \y -> 
    return (x+y) 

，看起来像延续！实际上，当您应用一个参数时，（>> =）的类型为(a -> m b) -> m b，即Cont (m b) a。有关说明，请参阅sigfpe的Mother of all monads。我认为这是一个很好的继续monad教程，尽管它不是这个意思。因为continuations和monad在两个方向上如此密切相关，我认为适用于monad的适用于continuations：只有努力工作才能教会你，而不是阅读一些卷饼比喻或类比。

Answer 4

我认为掌握Cont monad最简单的方法是了解如何使用它的构造函数。我要承担现在下面定义，虽然transformers包的现实稍有不同：

newtype Cont r a = Cont { runCont :: (a -> r) -> r } 

这给：

Cont :: ((a -> r) -> r) -> Cont r a 

所以要建立Cont r a类型的值，我们需要给一个函数来Cont：

value = Cont $ \k -> ... 

现在，k本身的类型为a -> r，并且lambda的主体需要具有类型r。一个显而易见的做法是将k应用于类型为a的值，并获得类型r的值。我们可以这样做，是的，但这只是我们可以做的许多事情之一。请记住value在r中不需要是多态，它可能是Cont String Integer或其他具体的类型。所以：

• 我们可以申请k于a类型的几个值，并将结果以某种方式结合起来。
• 我们可以将k应用于类型为a的值，观察结果，然后决定将k应用于基于此的其他内容。
• 我们可以完全忽略k，只是自己产生一个类型r的值。

但这是什么意思？ k最终会成为什么？那么，在一个做块，我们可能有一些看起来像这样：

flip runCont id $ do 
    v <- thing1 
    thing2 v 
    x <- Cont $ \k -> ... 
    thing3 x 
    thing4 

这里是最有趣的部分：我们可以在我们的脑海中，有点非正式的，两个在的发生分裂做块Cont的构造函数，并将作为本身的值考虑整个计算的其余部分。但是且慢，什么是取决于什么x是，所以这是一个真正的功能从值xa型的一些结果值：

restOfTheComputation x = do 
    thing3 x 
    thing4 

事实上，这restOfTheComputation是粗略地讲什么k结束了。换句话说，您呼叫k的值为Cont计算的结果x，其余计算运行，然后r产生的风返回到您的lambda中，作为调用k的结果。所以：

• 如果您多次调用k，其余计算将运行多次，并且结果可能会与您想要的结合。
• 如果您根本没有拨打k，则整个计算的其余部分将被跳过，并且封闭的runCont调用将返回您设法合成的r类型的值。也就是说，除非计算的其他部分正在呼吁你从他们k，并摆弄结果...

如果你还是跟我在这一点上应该很容易看到这可能是相当强大的。为了说明这一点，我们来实现一些标准类型类。

instance Functor (Cont r) where 
    fmap f (Cont c) = Cont $ \k -> ... 

我们给予Cont值和绑定结果a型x和功能f :: a -> b，我们希望做一个Cont值与b类型的绑定结果f x。好了，设置绑定结果，只需调用k ...

fmap f (Cont c) = Cont $ \k -> k (f ... 

等待，我们在哪里得到x而来？那么，这将涉及我们尚未使用的c。记住c是如何工作的：它得到一个函数，然后用它的绑定结果调用该函数。我们想要我们的函数与f适用于该绑定结果。所以：

fmap f (Cont c) = Cont $ \k -> c (\x -> k (f x)) 

田田！接下来，Applicative：

instance Applicative (Cont r) where 
    pure x = Cont $ \k -> ... 

这一个简单的。我们希望绑定结果是我们得到的x。

pure x = Cont $ \k -> k x 

现在，<*>：

Cont cf <*> Cont cx = Cont $ \k -> ... 

这有点麻烦，但本质上使用相同的想法，在FMAP：首先从第一Cont获得的功能，通过使拉姆达为它调用：

Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> ... 

然后从第二获得的价值x，使fn x绑定结果：

Cont cf <*> Cont cx = Cont $ \k -> cf (\fn -> cx (\x -> k (fn x))) 

Monad是大同小异，虽然需要runCont或情况，或让解压NEWTYPE。

这个答案已经很长了，所以我不会进入ContT（简而言之：它与Cont完全一样！唯一的区别在于类型构造函数的种类，所有的实现都是相同的）或callCC（一种有用的组合子，提供了一种方便的方式来忽略k，实现从子块中提前退出）。

对于一个简单而合理的应用程序，试试Edward Z. Yang的博客文章labelled break and continue in for loops。