Haskell Cont monad是如何以及为什么工作的？

Question

这就是Cont monad的定义方式:

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程序员,当我们认为在后台环境中构建计算时,我们认为接下来的事情是,这是一个monad吗？在这种情况下答案是肯定的,是的.

要将其转换为monad,我们从两个基本构建块开始:

• 对于monad m,type的值m a表示可以访问amonad上下文中的type类型的值.
• 我们的"暂停计算"的核心是翻转功能应用程序.

a在这种情况下访问某种类型的东西意味着什么？这只是意味着,对于一些价值x :: a,我们已经申请flip ($)到x,给我们一个功能,需要一个函数,它接受类型的参数a,并应用功能x.假设我们有一个暂停的计算,其值为type Bool.这给了我们什么类型？

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

因此,对于暂停计算,类型m a可以解决(a -> b) -> b......这可能是一个反复无常,因为我们已经知道了签名Cont,但现在我很幽默.

这里要注意的一件有趣的事情是,一种"逆转"也适用于monad的类型:Cont b a表示一个函数,它接受一个函数a -> b并进行求值b.由于延续表示计算的"未来",因此a签名中的类型在某种意义上表示"过去".

那么,替换(a -> b) -> b为Cont b a,我们的反向功能应用基本构建块的monadic类型是什么？a -> (a -> b) -> b转换为a -> Cont b a...相同类型的签名return,事实上,这正是它的本质.

从现在开始,一切都直接从类型中脱颖而出:>>=除了实际实现之外,基本上没有合理的实现方式.但它到底在做什么呢？

在这一点上,我们回到我最初所说的:延续monad并没有真正做很多事情.类似的东西Cont r a通常a只是通过提供id暂停计算的参数来简单地等同于类型的东西.这可能导致人们询问,如果Cont r a是a单身但是转换是如此微不足道,不应该单独也是一个单子？当然,这不起作用,因为没有类型构造函数可以定义为Monad实例,但是我们要添加一个简单的包装器,比如data Id a = Id a.这确实是一个单子,即身份单子.

什么是>>=对身份的单子呢？类型签名Id a -> (a -> Id b) -> Id b相当于a -> (a -> b) -> b,它只是简单的函数应用程序.已经建立了Cont r a相当于Id a,我们可以推断出在这种情况下,(>>=)只是功能应用.

当然,这Cont r a是一个疯狂的倒置世界,每个人都有山羊胡子,所以实际发生的事情包括以混乱的方式改变事物,以便将两个暂停的计算链接到一个新的暂停计算,但实质上,实际上并没有任何不寻常的事情发生上!将函数应用于参数,哼哼,在函数式程序员的生命中的另一天.

Answer 2

这是斐波那契:

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

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

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

我们将制作fib (n-1)额外的参数,这将是一个函数,指定计算结果后应该做什么,调用它x.fib (n-2)当然,它会增加它.所以:计算fib n你fib (n-1)之后计算,如果你调用结果x,你计算fib (n-2),之后,如果你调用结果y,你返回x+y.

换句话说,你必须告诉:

如何进行以下计算:" fib' n c=计算fib n并应用于c结果"？

答案是您执行以下操作:"计算fib (n-1)并应用于d结果",其中d x表示"计算fib (n-2)并应用于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)

同样,我们可以使用lambdas:

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)

根据monad的定义,与newtypes相同Cont.注意差异.有\c ->开头,而不是x <- ...有... $ \x ->和c代替return.

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

>>=工作怎么样？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

添加你得到的新类型

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

这是在这个页面的顶部.它很复杂,但如果你知道如何在do符号和直接使用之间进行转换,你不需要知道确切的定义>>=!如果你看看do-blocks,继续monad会更清晰.

Monads和延续

如果你看一下list monad的用法......

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.有关解释,请参阅sigfpe的所有monad的母亲.我认为这是一个很好的延续monad教程,虽然它可能并不意味着它.

由于延续和单子在两个方向上都有很强的相关性,我认为适用于monad的内容适用于延续:只有努力才会教你,而不是阅读一些卷饼比喻或类比.

Answer 3

编辑:文章迁移到下面的链接.

我已经写了一个直接解决这个主题的教程,希望你会发现它很有用.(这当然有助于巩固我的理解!)在Stack Overflow主题中,它有点太长了,所以我已经将它迁移到了Haskell Wiki.

请参阅:引擎盖下的MonadCont

Answer 4

我认为掌握Contmonad 的最简单方法是了解如何使用它的构造函数.我现在将假设以下定义,尽管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最终会被？好吧,在do-block中,我们可能看起来像这样:

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

这里是最有趣的部分:我们可以在我们的脑海中,有点非正式,在发生一分为二的DO-块Cont构造,并认为整个计算的休息后,它本身就是一种价值.但是且慢,什么是取决于什么x是,所以这是一个真正的函数从数值x型的a一些结果值:

restOfTheComputation x = do
  thing3 x
  thing4

事实上,这restOfTheComputation是粗略地讲什么k最终被.换句话说,你调用k一个值作为x你的Cont计算结果,其余的计算运行,然后r由于调用的结果产生的风回到你的lambda k.所以:

• 如果你k多次调用,其余的计算将多次运行,结果可能会结合你想要的.
• 如果你根本没有调用k,那么将跳过整个计算的其余部分,并且封闭runCont调用将只返回r你设法合成的任何类型的值.也就是说,除非计算的其他部分是从他们那里召唤你的 k,并且搞乱结果......

如果你现在还和我在一起,应该很容易看出这可能非常强大.为了说明一点,让我们实现一些标准类型类.

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

我们给出了一个Cont带有x类型的绑定结果a和一个函数f :: a -> b的Cont值,并且我们想要使用f x类型的绑定结果创建一个值b.好吧,要设置绑定结果,只需调用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,通过为其调用lambda:

  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或一个案例或者让我们解压缩新类型,但是大致相同.

这个答案已经很长了,所以我不会介绍ContT(简而言之:它完全相同Cont!唯一的区别在于类型构造函数的类型,一切的实现是相同的)或callCC(一个有用的组合器,提供了一种方便的方法来忽略k,实现从子块中提前退出).

对于一个简单而合理的应用程序,请尝试Edward Z. Yang的博客文章实现标记的break并继续for循环.