haskell - 比代数数据类型更喜欢 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
-- ^^^^ ^^^^
这是可能的,因为两个延续cerr
和eerr
具有相同的类型,只是它们的位置不同,这让我想起了结构类型。虽然我认为你不能用 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 上编写实例或对值进行显式案例分析的情况下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 并期望它可能有助于提高性能。博客文章看起来像是有意进行转换以解决性能问题,但这可能只是为了在博客文章中进行更简单的说明。
推荐阅读
- javascript - 在基于 Chromium 的浏览器中使用 D3 向 SVG 路径添加样式属性不起作用
- spring - 如何在我的 Spring Boot 应用程序中使用 Bcrypt 来保护密码?
- css - 语义反应/左侧带有文本的按钮
- javascript - 使用 mongo 客户端异步访问 mongo 集合时出错
- php - 在两个表上使用内连接后如何添加多行
- url - URL 是否有效需要协议(例如 http 或 https)?
- spring-boot - 没有 'org.springframework.test.web.servlet.MockMvc 类型的限定 bean
- django - 如何在Django模板中的if语句中调用函数
- angular - 当result为数组时合并两个api调用结果
- postgresql - pgAdmin 中锁定的几何列和查看器未正确显示