比代数数据类型更喜欢CPS的要求是什么？
我对代数数据类型的经验很少，因为我使用一种没有本地支持的语言。通常可以使用延续传递风格来获得远程相似的体验，但处理 CPS 编码类型不太舒服。
考虑到这一点，为什么像 Parsec 这样的库会使用 CPS？
newtype ParsecT s u m a
= ParsecT {unParser :: forall b .
State s u
-> (a -> State s u -> ParseError -> m b) -- consumed ok
-> (ParseError -> m b) -- consumed err
-> (a -> State s u -> ParseError -> m b) -- empty ok
-> (ParseError -> m b) -- empty err
-> m b
}
一个线索是try解析器，它通过在两种情况下传递空错误延续来排除消耗的错误情况：
try :: ParsecT s u m a -> ParsecT s u m a
try p =
ParsecT $ s cok _ eok eerr ->
unParser p s cok eerr eok eerr
-- ^^^^ ^^^^
这是可能的，因为 continuationcerr和continuationeerr的类型相同，只是位置不同，这让我想起了结构类型。虽然我认为你不能用 ADT 做到这一点，但可能有一种方法可以用它们实现相同的行为。除此之外，单个组合器无法证明依赖 CPS 的影响深远的决定是合理的。那么为什么会做出这个决定呢？
回答
此更改由 Antoine Latter于 2009 年 3 月 2 日在提交 a98a3ccb 中进行。提交评论只是：
commit a98a3ccbca9835fe749b8cd2d475a0494a84a460
Author: Antoine Latter <aslatter@gmail.com>
Date: Mon Mar 2 00:20:00 2009 +0000
move core data type over to CPS
它取代了 ParsecT 的原始 ADT：
data ParsecT s u m a
= ParsecT { runParsecT :: State s u -> m (Consumed (m (Reply s u a))) }
使用您问题中的新版本，添加一个runParsecT适配器以将所有内容转换回来：
runParsecT :: Monad m => ParsecT s u m a -> State s u -> m (Consumed (m (Reply s u a)))
runParsecT p s = unParser p s cok cerr eok eerr
where cok a s' err = return . Consumed . return $ Ok a s' err
cerr err = return . Consumed . return $ Error err
eok a s' err = return . Empty . return $ Ok a s' err
eerr err = return . Empty . return $ Error err
我看到他在 2009 年 2 月发表了一篇博客文章，其中他写了关于最终理解 CPS 风格的文章，并写了关于MaybeT. 他没有谈论任何性能上的优势，而只是指出，CPS风格有优势Monad，并MonadPlus为实例MaybeT可能不调用写入>>=或return底层单子或做明确的情况下，分析Maybe值。
在2009 年 12 月晚些时候的一篇博客文章中，他写到了他“对功能化 monad 转换器的痴迷”，给出了一个例子ErrorT并明确指出：
我还没有对这是否对任何事情更快进行基准测试，但我发现整个事情很有趣。
然而，他随后在同一篇博文中继续讨论如何向 Parsec 3 添加功能以使其成为 monad 转换器而不是普通的旧 monad 并在输入类型上对其进行参数化导致性能不佳（在某些情况下大约慢 1.8 倍）基准）。他发现转换为 CPS 风格使 Parsec 3 与 Parsec 2 一样快，至少在没有使用这些新抽象（转换器）时是这样。
推测时间，我认为 Antoine 认为 CPS 很“酷”并且有吸引他的风格优势，所以他在研究 Parsec 3 时把它放在首位。当 Parsec 3 中的新抽象导致性能问题时，他偶然发现将其转换为 CPS 似乎可以修复它们，尽管他没有详细研究原因（只是博客文章中的一些推测）。然而，我有点不清楚他是在发现性能优势之前真正先转换为 CPS，还是在尝试 CPS 时期望它可能有助于性能。博客文章读起来像是有意进行转换以解决性能问题，但这可能只是为了在博客文章中进行更简单的阐述。
回答
一个大问题是ParsecTmonad 转换器，使用 ADT 定义的 monad 转换器比使用 CPS 的 monad 转换器更能阻止优化。
该表达式pure x >>= k :: ExceptT e m a给出了一个最小的说明性示例。
-
使用
ExceptT e m a定义为m (Either e a)，该表达式不能很好地简化，因为它涉及抽象(>>=)的底层 monadm。 -
与
ExceptT e m a定义为forall r. (Either e a -> m r) -> m r，pure x >>= k基本上的β-减少了k x，未做任何假设m。
您需要专门m优化一个类型的术语m (Either e a)，而基于延续的变体可以在没有专门化的情况下走很长的路。
然而，CPS 也不是 Haskell 中的理想表示，因为延续是在堆上分配的函数。功能很便宜，但不是零成本。
归根结底，mmonad 转换器的抽象性确实妨碍了，要优化，您必须专门化，即打破模块化。因此，一个更有前景的方法是使用一些特殊的原始 monad ( IO) 和来自运行时系统的专门支持，作为效果系统的基础。
另请参阅Alexis King和相关库eff 的Less 效果。