haskell - 比代数数据类型更喜欢 CPS 的要求是什么？

Question

我对代数数据类型几乎没有经验，因为我使用的语言没有原生支持。通常可以使用延续传递样式来获得远程相似的体验，但 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
--                   ^^^^     ^^^^

这是可能的，因为两个延续 cerr和 eerr具有相同的类型，只是它们的位置不同，这让我想起了结构类型。虽然我认为你不能用 ADT 做到这一点，但可能有一种方法可以用它们实现相同的行为。除此之外，单个组合器无法证明依赖 CPS 的影响深远的决定是合理的。那么为什么会做出这个决定呢？

Answer 1

此更改于 2009 年 3 月 2 日在 commit 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

我看到他做了一个 blog post in February 2009在那里他写了关于最终理解 CPS 风格的文章并写了一篇关于 MaybeT 的 CPS 版本的文章。 .他没有谈论任何性能优势，只是指出 CPS 样式具有 Monad 的优势。和 MonadPlus MaybeT 的实例无需调用 >>= 即可编写或 return在底层 monad 或对 Maybe 进行显式案例分析值(value)观。
在以后的 December 2009 blog post ，他写到他“痴迷于函数化 monad 转换器”，举了一个 ErrorT 的例子并明确指出:

I haven't benchmarked whether or not this is faster for anything, but I find the whole thing a lot of fun.

但是，然后，他在同一篇博客文章中继续讨论如何向 Parsec 3 添加功能以使其成为 monad 转换器而不是普通的旧 monad，并在输入类型上对其进行参数化导致性能不佳(在某些基准测试中大约慢 1.8 倍) .他发现转换为 CPS 样式使 Parsec 3 与 Parsec 2 一样快，至少在不使用那些新的抽象(转换器)时是这样。
推测时机，我认为 Antoine 认为 CPS 很“酷”并且具有吸引他的风格优势，因此他在处理 Parsec 3 时将其放在首位。当 Parsec 3 中的新抽象导致性能问题时，他偶然发现将其转换为 CPS 似乎可以修复它们，尽管他没有详细研究原因(只是博客文章中的一些猜测)。但是，我有点不清楚他是否 实际上在发现性能优势之前先转换为 CPS，或者尝试 CPS 并期望它可能有助于提高性能。博客文章看起来像是有意进行转换以解决性能问题，但这可能只是为了在博客文章中进行更简单的说明。