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

这是Cont monad的定义:

newtype Cont ra = Cont { runCont :: (a -> r) -> r } instance Monad (Cont r) where return a = Cont ($ a) m >>= k = Cont $ \c -> runCont m $ \a -> runCont (ka) c 

你能解释一下为什么这个工作原理? 它在做什么?

关于继续monad的第一件事情就是从根本上说,它根本就没有任何事情。 这是真的!

一般而言,延续的基本思想是它代表了计算的其余部分 。 假设我们有这样一个expression式: foo (bar xy) z 。 现在,只提取括号内的部分bar xy这是总expression式的一部分 ,但它不只是一个我们可以应用的函数。 相反,这是我们需要应用一个函数的东西。 所以,在这种情况下,我们可以把“剩余的计算”作为\a -> foo az ,我们可以将它应用于bar xy来重构完整的forms。

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

这个修改后的版本给了我们很大的灵活性 – 不仅从它的上下文中提取了一个子expression式,而且还允许我们在子expression式本身内部操作这个外部的上下文 。 我们可以把它看作是一种暂停的计算 ,让我们明确地控制接下来发生的事情。 现在,我们怎么概括这个? 那么,子expression式几乎没有改变,所以让我们用一个参数代替它,给我们\xk -> kx – 换句话说,只不过是函数应用,反过来 。 我们可以轻松地书写flip ($) ,或添加一些异国情调的外语风格,并将其定义为运算符|>

现在,尽pipe单调乏味,可怕的混淆,将每一个expression方式都翻译成这种forms是很简单的。 幸运的是,还有更好的办法。 作为Haskell程序员,当我们想在后台环境中构build计算时,我们接下来想到的就是这个单子吗? 在这种情况下,答案是肯定的 ,是的。

为了把它变成一个monad,我们从两个基本的构build块开始:

  • 对于monad mmatypes的值表示可以在monad的上下文中访问atypesa值。
  • 我们的“暂停计算”的核心是翻转函数应用程序。

在这种情况下访问某种typesa东西意味着什么? 它只是意味着,对于某个值x :: a ,我们已经将flip ($)应用于x ,给了我们一个函数,它接受一个atypes参数的函数,并将该函数应用于x 。 假设我们有一个暂停的计算,保存了一个Booltypes的值。 这是什么types给我们?

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

所以对于暂停的计算,typesma解决(a -> b) -> b …这也许是一个反作用,因为我们已经知道了Cont的签名,但是现在我幽默了。

这里需要注意的一点是,一种“反转”也适用于monad的types: Cont ba表示一个函数,它使用函数a -> b并计算为b 。 作为一个延续表示计算的“未来”,所以签名中的typesa代表某种意义上的“过去”。

所以,用Cont bareplace(a -> b) -> b ,我们的反函数应用的基本构build块的monadictypes是什么? a -> (a -> b) -> b转换为a -> Cont ba …与return相同的types签名,实际上就是这样。

从这里开始,几乎所有的东西都直接从这些types中分离出来:除了实际的实现之外,基本上没有实现>>=明智的方法。 但是,它究竟在做什么

在这一点上,我们回到我刚才说的话:继续monad实际上并没有太多的事情。 typesCont ra某些东西只是简单地把id作为参数提供给挂起的计算,这简直就是类似于a东西。 这可能会导致人们问,如果Cont ra是monad,但是转换是如此微不足道,那么单独是不是monad? 当然,这是行不通的,因为没有types构造函数来定义Monad实例,但是说我们添加一个简单的包装,如data Id a = Id a 。 这确实是一个monad,也就是monad的身份。

>>=对身份monad做什么? types签名是Id a -> (a -> Id b) -> Id b ,相当于a -> (a -> b) -> b ,这就是简单的函数应用。 已经确定Cont raId a ,我们可以推断在这种情况下, (>>=)就是函数应用

当然, Cont ra是一个疯狂的颠倒的世界,每个人都有一个山泥倾泻的世界,所以实际上发生的事情是以混乱的方式来混淆事物,以便将两个悬浮的计算连锁在一起,形成一个新的暂停的计算,但实质上并没有任何东西不寻常的继续! 在function程序员的生活中,将function应用于论点,哼哼。

斐波纳契:

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

想象一下,你有一台没有调用堆栈的机器 – 它只允许尾recursion。 如何在该机器上执行fib ? 你可以很容易地将函数改写成线性函数,而不是指数时间,但是这需要一点洞察力,而不是机械的。

使其recursion尾部的障碍是第三行,其中有两个recursion调用。 我们只能打一个电话,也得给出结果。 这里是延续input的地方。

我们将使fib (n-1)具有额外的参数,这是一个函数,指定在计算结果后应该做什么,称之为x 。 当然,它会添加fib (n-2) 。 所以:计算一下你计算fib (n-1)后,如果你调用结果x ,计算fib (n-2) ,之后如果调用结果y ,则返回x+y

换句话说,你必须告诉:

如何做以下计算:“ fib' nc =计算fib n并将c应用于结果”?

答案是你做了下面的事情:“计算fib (n-1)并且将d应用于结果”,其中dx表示“计算fib (n-2)并将e应用于结果”,其中ey表示c (x+y) 。 在代码中:

 fib' 0 c = c 0 fib' 1 c = c 1 fib' nc = fib' (n-1) d where dx = fib' (n-2) e where ey = 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传递给下一个。

最后三行闻起来像一个阻止,事实上

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

按照monad Cont的定义是一样的,直到新型。 注意区别。 有\c ->在开头,而不是x <- ...... $ \x ->c而不是return

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

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

 do a <- m t <- ka return t 

翻译回来,在风格相同的方式,你会得到

 \c -> m $ \a -> ka $ \t -> ct 

简化\t -> ctc

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

添加你得到的新types

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

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

Monads和延续

如果你看看这个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) 

看起来像延续! 实际上,当你应用一个参数时,(>> =)的types是(a -> mb) -> mb ,它是Cont (mb) a 。 见sigfpe的所有单子的母亲的解释。 我认为这是一个很好的继续monad教程,虽然它不是这个意思。

由于延续和单子在双向上如此密切相关,我认为适用于单子的适用于延续:只有辛勤工作才能教会你,而不是阅读一些卷饼比喻或类比。

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

我已经写了一个教程直接解决这个问题,我希望你会发现有用的。 (这当然有助于巩固我的理解!)在堆栈溢出主题中放置一段时间太长了,所以我把它移植到了Haskell Wiki中。

请参阅: 引擎盖下的MonadCont

我认为掌握Cont monad最简单的方法是理解如何使用它的构造函数。 我现在要假定以下定义,尽pipetransformers包的实际情况略有不同:

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

这给了:

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

所以为了build立一个typesCont ra值的值,我们需要给Cont一个函数:

 value = Cont $ \k -> ... 

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

  • 我们可以将k应用于ktypesa多个值,并以某种方式组合结果。
  • 我们可以将k应用于atypes的值,观察结果,然后决定将k应用于其他的基础上。
  • 我们完全可以忽略k ,只是自己产生一个rtypes的值。

但是,这是什么意思? k最终成为什么? 那么,在一个块,我们可能有这样的东西:

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

下面是有趣的部分:我们可以在我们的想法中,在一些非正式的情况下,在Cont构造函数的出现处将do块分割成两部分,然后把整个计算的其余部分作为一个值本身。 但是坚持下去,它取决于x是什么,所以它实际上是一个从atypesax到某个结果值的函数:

 restOfTheComputation x = do thing3 x thing4 

事实上,这个restOfTheComputation k最终成立的。 换句话说,你用一个成为你的Cont计算的结果x的值来调用k ,剩下的计算运行,然后产生的r作为调用k的结果回到你的lambda中。 所以:

  • 如果多次调用k ,则其余的计算将会多次运行,并且结果可能会根据您的需要进行组合。
  • 如果你完全没有调用k ,那么整个计算的其余部分将被跳过,并且封闭的runCont调用将会返回你设法合成的任何rtypes的值。 也就是说,除非其他部分的计算是从他们的 k调用 ,并搞乱了结果…

如果你现在还在和我在一起,应该很容易看出这可能是相当强大的。 为了说明这一点,我们来实现一些标准的types类。

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

我们给出了一个types为a绑定结果x和一个函数f :: a -> bCont值,并且我们要使用types为b绑定结果fx创build一个Cont值。 那么,要设置绑定结果,只需调用k

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

等等,我们从哪里得到x ? 那么,这将涉及c ,我们还没有使用。 记住c是如何工作的:它得到一个函数,然后用它的绑定结果调用这个函数。 我们要调用我们的函数与f应用到绑定的结果。 所以:

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

田田! 接下来, Applicative

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

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

  pure x = Cont $ \k -> kx 

现在, <*>

  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或一个案例或让解压新types。

这个答案已经很长了,所以我不会进入ContT (简而言之,它和Cont是完全一样的,唯一不同的是types构造函数的types,所有的实现都是相同的)或者callCC (a有用的组合器,提供了一个方便的方法来忽略k ,实现从一个子块提前退出)。

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