尾递归优化保证 - Haskell 中的循环编码

Question

尾递归优化保证 - Haskell 中的循环编码

11

所以我的问题简而言之就是，在Haskell中，我们应该如何编码循环，总的来说？在Haskell中没有尾部优化保证，bang模式甚至不是标准的一部分（对吗？），而fold / unfold范例不能保证在所有情况下都能正常工作。这里有一个例子，只有使用bang-patterns才能让它在恒定空间内运行（即使没有使用$!也没有帮助...尽管测试是在使用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)

在我添加了bang-pattern之前，我要么遇到内存溢出，要么甚至遇到堆栈溢出。但是bang pattern不是标准的一部分，对吧？所以问题是，如何用标准的Haskell编写上述代码以在恒定空间中运行？

这里是测试代码。计算是虚假的，但问题是相同的。编辑：foldr形式的代码是：

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会导致堆栈溢出。如果在f中使用bang-patterns，则更改为foldl仅成功，但它以相反的顺序构建列表。我想懒惰地按正确的顺序构建它。是否可以使用任何类型的fold进行操作，以获得惯用解决方案？

编辑: 总结来自@ehird的答案: 使用bang模式没有什么可担心的。虽然不是标准的Haskell本身，但很容易在其中编码为f ... c ... = case (seq c False) of {True -> undefined; _ -> ...}。教训是，只有模式匹配强制一个值，而seq本身并不强制任何东西，而是安排当seq x y被强制执行时-通过模式匹配-x也将被强制执行，并且y将是答案。与我从在线报告中理解的相反，$!本身不会强制执行任何内容，尽管它被称为"严格应用运算符"。

@stephentetley的观点很重要 - 严格性在控制空间行为方面非常重要。因此，使用严格性注释和感叹号模式来编码Haskell中的循环是完全可以的，必要时可以编写任何所需的特殊折叠（即结构消耗）函数 - 就像我最初做的那样 - 并依赖于GHC来优化代码。

非常感谢大家的帮助。

- Will Ness

@ivanm 当然，一门编程语言应该有编码循环或等效结构的基本手段，不是吗？ - Will Ness

3

可以遍历数据等等；但是通常当人们问“如何在Haskell中编写循环”时，这是因为他们正在尝试逐行移植一些命令式代码，而这通常不是最佳方式。此外，为什么将循环的概念视为“基本结构”？我认为循环只是迭代数据的命令式观点。 - ivanm

@ivanm 通过迭代生成的数据来创建数据，以恒定空间运行的“循环”或其他名称。我个人更喜欢尾递归公式，但那只是语法。迭代过程即在恒定空间中运行的过程，肯定是计算的基本概念（参见SICP等）。例如，在Prolog中，编码循环的唯一方法是通过尾递归。但是Haskell没有尾递归，那么如何在其中编写循环呢？ - Will Ness

1

@Will Ness - 你在刨根问底地争辩“Haskell没有尾部递归”的说法 - 你可能是指TCO？-并且说标准并不能保证TCO，但GHC（通常与“Haskell”同义，除非另有区分）在进行优化编译时可以执行TCO。那么我会承认，“Haskell”比Scheme的TCO要少，但我仍然坚持认为它与OCaml相当可比。 - stephen tetley

1

@Will Ness - 从我在维基百科上了解到，“TCO modulo cons”是David Warren的Prolog中一种实现策略，它在一定程度上推广了TCO。就我所知，Haskell（以及Scheme，OCaml等）中没有这个功能，因此您必须使用无cons的尾递归样式编写算法。您还必须注意累加器的严格性（与TCO不同的问题）。如果您正在使用成对数据，例如您的汉明码，那么在递归组件中，您必须非常小心地避免“Walder pair space leak”。 - stephen tetley

显示剩余13条评论

2个回答

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）防止共享条目（为每个计算生成两次），要么2）将整个条目列表保存在内存中。如果同时评估它们，则必须要么1）严格评估，要么2）为计数创建的巨大thunk需要大量堆栈空间。对于这两种情况，选项＃2都相当糟糕。您的命令式解决方案通过同时严格评估来处理此问题。对于Haskell中的解决方案，您可以选择单独或同时评估选项＃1。或者，您可以展示您的“真实”代码，也许我们可以帮助您找到重新安排数据依赖项的方法；可能会发现您不需要总计数等内容。

- Dan Burton

感谢回答。我在问题中已经链接到了真正的代码，它在这里。我只是不太放心使用惊叹号模式，因为它们不是标准的，但是ehird向我展示了如何在标准Haskell中对它们进行编码，所以现在没问题了。我最终写了一种特殊类型的折叠函数，GHC也能处理得很好。 - Will Ness

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ehird · Accepted Answer

Bang模式只是对seq的简化 - 每当你看到let !x = y in z，它可以被翻译成let x = y in x `seq` z。seq是标准的，因此将使用Bang模式的程序转换为可移植形式没有问题。

虽然Haskell不保证性能-报告甚至没有定义评估顺序（仅要求它必须是非严格的），更不用说运行时堆栈的存在或行为了。但是，虽然报告没有指定特定的实现方法，但您肯定可以针对其中一个进行优化。

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

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

实际上，在Haskell中，“尾递归”本身并没有太多意义：如果您的累加器参数不是严格的，那么在稍后尝试强制它们时，您将溢出堆栈；由于惰性，许多非尾递归程序确实不会溢出堆栈；即使是打印repeat 1，也永远不会溢出堆栈，尽管定义 - repeat x = x：repeat x - 明显在非尾位置有递归。这是因为（:) 对其第二个参数是惰性的；如果您遍历列表，您将具有恒定的空间使用率，因为repeat x thunks被强制执行，并且垃圾收集器抛弃了以前的cons单元。

更加哲学的一面，尾递归循环在Haskell中通常被认为是次优的。通常情况下，我们不是迭代地计算结果，而是生成一个带有所有步骤等价物的结构，并对其进行转换（如折叠）以产生最终结果。这是一个更高级别的视角，通过惰性实现高效（该结构在处理时被建立和垃圾回收，而不是一次性全部完成）。这可能需要一些时间来适应，当然并不适用于所有情况 - 极其复杂的循环结构可能难以有效地翻译 - 但是直接将尾递归循环翻译成Haskell可能会很痛苦，因为它并不真正符合惯用法。

关于你提供的粘贴内容，id $! x 并不能强制执行任何操作，因为它与 x `seq` id x 相同，而这与 x `seq` x 相同，而这与 x 相同。基本上，每当强制执行 x `seq` y 时，都会强制执行 x，结果是 y。你无法使用 seq 在任意点上强制执行东西；你使用它来导致延迟计算依赖于其他延迟计算。

在这种情况下，问题在于你正在构建一个大的延迟计算（thunk）在 c 中，所以你可能想让 auxk 和 auxj 强制执行它；一个简单的方法是在定义顶部添加一个类似于 auxj _ _ c _ | seq c False = undefined 的从句。（guard 总是被检查，强制评估 c，但总是导致 False，因此右侧永远不会被评估。）

个人建议您在最终版本中保留当前的bang模式，因为它更易读，但是 f c _ | seq c False = undefined 也同样有效。

¹参见 利用函数式记忆树进行优雅的记忆化 和 data-memocombinators 库。

²确实，GHC通常甚至可以使用fusion和deforestation完全消除中间结构，生成类似于低级命令式语言中编写计算的机器代码。

³虽然如果您有这样的循环，采用这种编程风格可能会帮助您简化它们——惰性意味着您可以轻松地将计算的独立部分分离出来放入单独的结构中，然后过滤和组合它们，而不必担心通过进行稍后将被丢弃的中间计算来复制工作。