13

我很喜欢 Haskell，但空间泄漏对我来说有点担心。我通常认为 Haskell 的类型系统比 C++ 更安全，但是使用 C 风格的循环我可以相当肯定它会在不耗尽内存的情况下完成，而 Haskell 的“折叠”可能会耗尽内存，除非你小心适当的字段是严格的。

我想知道是否有一个库使用 Haskell 类型系统来确保可以编译和运行各种结构，而不会产生 thunk。例如，no_thunk_fold如果有人以一种可以建立 thunk 的方式使用它，则会引发编译器错误。我知道这可能会限制我可以做的事情，但我想要一些我可以使用的功能作为一个选项，这会让我更有信心我没有不小心在某个地方留下一个重要的非严格字段并且我会用完的空间。

4

2 回答 2

10

听起来您担心惰性评估的一些不利方面。你想确保你的折叠、循环、递归在常量内存中处理。

创建的 iteratee 库解决了这个问题， 管道、 管道、 枚举器、 迭代器、 迭代器。

最流行和最近的是 管道和 导管。两者都超出了迭代模型。

管道库专注于理论上的 合理性，以消除错误并允许设计的恒常性打开高效但高层次的抽象（我的话不是作者）。如果需要，它还提供双向流，这是迄今为止该库独有的优势。

管道在 理论上不如管道那么好，但它的巨大优势是目前在其上构建了更多相关库，用于解析和处理 http 流、xml 流等。在包页面上查看hackage中的导管部分。它被用于 Haskell较大且知名的 Web 框架之一。

我很喜欢使用管道库编写我的流应用程序，特别是能够制作代理转换器堆栈的能力。当我需要获取网页或解析一些 xml 时，我一直在使用管道库。

我还应该提到 io-streams刚刚发布了它的第一个正式版本。它的目标特别是 IO，它的名字并不奇怪，它使用更简单的类型机制，更少的类型参数，然后是 管道或 管道。主要的缺点是你被困在 IO monad 中，所以它对纯代码不是很有帮助。

{-# language NoMonoMorphismRestriction #-}                                       
import Control.Proxy

从简单的翻译开始。

map (+1) [1..10]

变成：

runProxy $ mapD (+1) <-< fromListS [1..10]

迭代者喜欢为简单的翻译提供更冗长的内容，但通过更大的示例提供更大的胜利。

以恒定空间生成斐波那契数的代理管道库示例

fibsP = runIdentityK $ (\a -> do respond 1                                       
                                 respond 1                                       
                                 go 1 1)                                         
  where                                                                          
    go fm2 fm1 = do  -- fm2, fm1 represents fib(n-2) and fib(n-1)                                                            
        let fn = fm2 + fm1                                                       
        respond fn -- sends fn downstream                                                              
        go fm1 fn

这些可以通过 runProxy $ fibsP >-> printD 流式传输到标准输出 - printD 仅打印下游值，代理是管道包的双向提供。

你应该看看我刚刚发现的代理教程和管道教程现在在 FP Complete 的 Haskell 学校。

找到平均值的一种方法是：

> ((_,l),s) <- (`runStateT` 0) $ (`runStateT` 0) $ runProxy $  foldlD' ( flip $ const (+1)) <-< raiseK (foldlD' (+)) <-< fromListS [1..10::Int]
> let m = (fromIntegral . getSum) s / (fromIntegral . getSum) l
5.5

现在很容易添加地图或过滤代理。

> ((_,l),s) <- (`runStateT` 0) $ (`runStateT` 0) $ runProxy $  foldlD' ( flip $ const (+1)) <-< raiseK (foldlD' (+)) <-< filterD even <-< fromListS [1..10::Int]

编辑：重写代码以利用状态单子。

更新：

关于以可比较的方式对大量数据流进行多次计算的更多方法，然后在博客文章美丽折叠中演示了编写直接递归。折叠转换为数据并在使用严格累加器时组合。我没有定期使用这种方法，但它似乎确实隔离了需要严格性的地方，使其更容易应用。您还应该查看另一个类似问题的答案，该问题使用应用程序实现相同的方法，并且可能更容易阅读，具体取决于您的偏好。

于 2013-03-13T01:30:51.700 回答
7

Haskell 的类型系统不能做到这一点。我们可以用一个完全多态的术语来证明这一点，以吃掉任意数量的 ram。

takeArbitraryRAM :: Integer -> a -> a
takeArbitraryRAM i a = last $ go i a where
  go n x | n < 0 = [x]
  go n x | otherwise = x:go (n-1) x

做你想做的事需要子结构类型。线性逻辑对应于 lambda 演算的一个高效可计算片段（尽管您还需要控制递归）。添加结构公理可以让您花费超指数时间。

Haskell 允许您伪造线性类型，以便使用索引单子管理某些资源。不幸的是，空间和时间都融入了语言，所以你不能为他们这样做。您可以按照评论中的建议进行操作，并使用 Haskell DSL 生成具有性能限制的代码，但此 DSL 中的计算项可能需要任意时间并使用任意空间。

不用担心空间泄漏。抓住他们。轮廓。证明复杂性界限的代码的原因。无论您使用哪种语言，您都必须这样做。

于 2013-03-13T08:35:40.627 回答