11

所以我的问题的简短版本是，一般来说，我们应该如何在 Haskell 中编码循环？Haskell 中没有尾部优化保证，爆炸模式甚至不是标准的一部分（对吗？），折叠/展开范式不能保证在所有情况下都有效。这就是一个很好的例子，只有 bang-patterns 对我来说是让它在恒定空间中运行的技巧（甚至没有使用help $!...尽管测试是在使用 ghc-6.8.2 的 Ideone.com 上完成的）。

它基本上是关于一个嵌套循环，在列表范式中可以表示为

prod (sum,concat) . unzip $ 
    [ (c, [r | t]) | k<-[0..kmax], j<-[0..jmax], let (c,r,t)=...]
prod (f,g) x = (f.fst $ x, g.snd $ x)

或者在伪代码中：

let list_store = [] in
for k from 0 to kmax
    for j from 0 to jmax
        if test(k,j) 
            list_store += [entry(k,j)]
        count += local_count(k,j)
result = (count, list_store)

直到我添加了爆炸模式，我得到了内存爆裂甚至堆栈溢出。但是刘海图案不是标准的一部分，对吧？所以问题是，如何在标准 Haskell 中编写上述代码以在恒定空间中运行？

这是测试代码。计算是假的，但问题是一样的。编辑： -formulatedfoldr代码是：

testR m n = foldr f (0,[]) 
               [ (c, [(i,j) | (i+j) == d ])
                 | i<- [0..m], j<-[0..n], 
                   let c = if (rem j 3) == 0 then 2 else 1 ]
  where d = m + n - 3
    f (!c1, [])     (!c, h) = (c1+c,h) 
    f (!c1, (x:_))  (!c, h) = (c1+c,x:h)

尝试运行 print $ testR 1000 1000会产生堆栈溢出。更改为foldl仅在使用 bang-patterns 时才会成功f，但它会以相反的顺序构建列表。我想以正确的顺序懒惰地构建它。fold对于惯用的解决方案，可以使用任何类型的, 来完成吗？

编辑：总结一下我从@ehird 得到的答案：使用爆炸模式没有什么好害怕的。虽然不在标准 Haskell 本身中，但它很容易在其中编码为f ... c ... = case (seq c False) of {True -> undefined; _ -> ...}. 教训是，只有模式匹配会强制一个值，并且seq不会自己强制任何东西，而是安排何时 seq x y强制 - 通过模式匹配 -x也会被强制，y并将成为答案。与我从在线报告中所理解的相反，它$!本身不会强制执行任何操作，尽管它被称为“严格的应用程序操作员”。

@stephentetley 的观点 -严格性对于控制空间行为非常重要。因此，可以在 Haskell 中对循环进行编码，并在需要时正确使用带有 bang 模式的严格性注释，以编写任何需要的特殊折叠（即结构消耗）函数——就像我最终做的那样- 并依靠 GHC 来优化代码。

非常感谢大家的帮助。

4

2 回答 2

15

Bang 模式简直就是糖seq——只要你看到let !x = y in z，就可以翻译成let x = y in x `seq` z. seq是标准的，因此将使用 bang 模式的程序转换为可移植形式没有问题。

确实，Haskell 不保证性能——报告甚至没有定义评估顺序（只是它必须是非严格的），更不用说运行时堆栈的存在或行为了。但是，虽然该报告没有指定具体的实施方法，但您当然可以针对其中一种方法进行优化。

例如，所有 Haskell 实现在实践中都使用按需调用（因此共享），这对于优化 Haskell 代码的内存使用和速度至关重要。事实上，纯粹的记忆技巧1（依赖于共享（没有它，它只会减慢速度）。

这个基本结构让我们看到，例如，堆栈溢出是由构建过大的 thunk 引起的。由于您尚未发布整个代码，因此我无法告诉您如何在没有 bang 模式的情况下重写它，但我怀疑[ (c, [r | t]) | ... ]应该成为[ c `seq` r `seq` t `seq` (c, [r | t]) | ... ]. 当然，刘海模式更方便；这就是为什么它们是如此常见的扩展！（另一方面，您可能不需要强制所有这些；知道要强制什么完全取决于代码的特定结构，并且在所有内容中疯狂添加 bang 模式通常只会减慢速度。）

事实上，“尾递归”本身在 Haskell 中并不意味着什么：如果你的累加器参数不严格，当你稍后尝试强制它们时，你会溢出堆栈，事实上，由于懒惰，许多非-尾递归程序不会溢出堆栈；打印repeat 1永远不会溢出堆栈，即使定义 - repeat x = x : repeat x- 显然在非尾部位置具有递归。这是因为(:)它的第二个参数是惰性的；如果您遍历列表，您将有恒定的空间使用，因为repeat xthunk 是强制的，并且之前的 cons 单元被垃圾收集器丢弃。

从更哲学的角度来看，尾递归循环在 Haskell中通常被认为是次优的。通常，我们宁愿在叶子上生成一个具有所有步等效项的结构，而不是在步骤中迭代计算结果，并对其进行转换（如折叠）以产生最终结果。这是一个更高层次的事物视图，由于懒惰而变得高效（结构是在处理时构建和垃圾收集的，而不是一次全部）。2

刚开始这可能需要一些时间来适应，而且它肯定不会在所有情况下都有效——极其复杂的循环结构可能很难有效地翻译3——但直接将尾递归循环翻译成 Haskell 可能会很痛苦，因为它不是真的不是那么地道。

就您链接到的粘贴而言，id $! x它无法强制执行任何操作，因为它与 相同x `seq` id x，与 相同x `seq` x，与 相同x。基本上，无论何时x `seq` y被强制，x被强制，结果是y。你不能用来seq在任意点强迫事情；您使用它来强制 thunk依赖于其他 thunk。

在这种情况下，问题在于您正在构建一个大的 thunk in c，因此您可能想要制作auxk并auxj强制它；一个简单的方法是auxj _ _ c _ | seq c False = undefined在定义的顶部添加一个类似的子句。（守卫总是被检查，强制c被评估，但总是导致False，所以右手边永远不会被评估。）

就个人而言，我建议保留最终版本中的爆炸模式，因为它更具可读性，但f c _ | seq c False = undefined也可以正常工作。

1请参阅具有功能性备忘录尝试和数据备忘录组合库的优雅备忘录。

2事实上，GHC 通常甚至可以使用融合和砍伐森林完全消除中间结构，生成类似于用低级命令式语言编写计算的机器代码。

3虽然如果你有这样的循环，这种编程风格很可能会帮助你简化它们——懒惰意味着你可以很容易地将计算的独立部分分离成单独的结构，然后过滤和组合它们，而不用担心你'将通过进行稍后将被丢弃的中间计算来重复工作。

于 2012-02-05T13:18:54.170 回答
2

好的，让我们从头开始工作。

你有一个条目列表

entries = [(k,j) | j <- [0..jmax], k <- [0..kmax]]

根据这些指标，您可以进行测试和计数

tests m n = map (\(k,j) -> j + k == m + n - 3) entries
counts = map (\(_,j) -> if (rem j 3) == 0 then 2 else 1) entries

现在您要建立两件事：“总”计数和“通过”测试的条目列表。当然，问题是您想懒惰地生成后者，而应该严格评估前者（以避免爆炸堆栈）。

如果您分别评估这两件事，那么您必须 1) 防止共享entries（生成两次，每次计算一次），或 2) 将整个entries列表保存在内存中。如果您一起评估它们，那么您必须 1) 严格评估，或者 2) 为计数创建的巨大 thunk 提供大量堆栈空间。两种情况下的选项 #2 都相当糟糕。您的命令式解决方案仅通过同时且严格地评估来解决此问题。对于 Haskell 中的解决方案，您可以将选项 #1 用于单独或同时评估。或者您可以向我们展示您的“真实”代码，也许我们可以帮助您找到重新排列数据依赖关系的方法；结果可能你不需要总数，或者类似的东西。

于 2012-02-05T21:38:35.837 回答