所以我的问题的简短版本是，我们如何在Haskell中编码循环， 一般来说？在Haskell中没有尾部优化保证，爆炸模式甚至不是标准的一部分（对吗？），折叠/展开范例是 不 保证在所有情况下都能工作。这里的 一个很好的例子 只有爆炸模式才能使我在恒定的空间中运行（甚至不使用 $! 帮助......虽然 测试 在Ideone.com完成，使用ghc-6.8.2）。
它基本上是一个嵌套循环，在列表范例中可以表示为
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中编写以上代码，在恒定空间中运行？
这是 测试代码。计算是假的，但问题是一样的。 编辑： 该 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 产生堆栈溢出。改为 foldl 只有在使用爆炸模式时才会成功 f，但它以相反的顺序构建列表。我想懒得以正确的顺序构建它。可以用任何一种方式完成 fold， 为了 惯用的 解？
编辑： 总结我从@ehird得到的答案：没有什么可以担心使用爆炸模式。虽然不是标准的Haskell本身，但很容易将其编码为 f ... c ... = case (seq c False) of {True -> undefined; _ -> ...}。经验教训是，只有模式匹配强制一个值，和 seq 不 不 强迫任何东西，而是安排 什么时候 seq x y 被迫 - 通过模式匹配 - x 将被迫，并且 y 将是答案。与我在在线报告中可以理解的相反， $! 不 不 虽然它自己强迫任何东西 是 叫做 “严格的应用运营商”。
而@stephentetley的观点 - 严格 在控制太空行为方面非常重要。因此，在Haskell中对循环进行编码是完全正确的，并且需要使用严格注释和bang模式，在需要时编写任何需要的特殊折叠（即结构消耗）函数 - 就像我最初做的那样 - 并依靠GHC来优化代码。
非常感谢大家的帮助。
Bang模式简直就是糖 seq - 每当你看到 let !x = y in z，可以翻译成 let x = y in x `seq` z。 seq 是标准的，所以将使用爆炸模式的程序翻译成可移植的形式是没有问题的。
确实，Haskell对性能没有任何保证 - 报告甚至没有定义 评估顺序 （只有它必须是非严格的），更不用说运行时堆栈的存在或行为了。但是，虽然报告没有指定具体的实施方法，但您当然可以优化一种方法。
例如，所有Haskell实现在实践中都使用按需调用（以及共享），这对于优化Haskell代码以实现内存使用和速度至关重要。确实，纯粹的记忆技巧1 （因为依赖于共享（没有它，它只会减慢速度）。
例如，这个基本结构让我们看到堆栈溢出是由于构建过大的thunk而引起的。由于你没有发布你的整个代码，我无法告诉你如何在没有爆炸模式的情况下重写它，但我怀疑 [ (c, [r | t]) | ... ] 应该成为 [ c `seq` r `seq` t `seq` (c, [r | t]) | ... ]。当然，爆炸模式更方便;这就是为什么他们是如此普遍的延伸！ （另一方面，你可能不需要强迫 所有 那些;知道要强制的是完全依赖于代码的特定结构，并且通常会将爆炸模式添加到所有内容中，这通常会减慢速度。）
的确，“尾递归” 本身 在Haskell中并不是那么多意思：如果你的累加器参数不严格，当你以后试图强制它们时你会溢出堆栈，事实上，由于懒惰，很多 非-tail-recursive程序不会溢出堆栈;印花 repeat 1 永远不会溢出堆栈，即使定义 - repeat x = x : repeat x - 显然在非尾部位置递归。这是因为 (:) 第二个论点是懒惰的;如果你遍历列表，你将有恒定的空间使用，如 repeat x thunk被迫，以前的cons细胞被垃圾收集器扔掉了。
在更哲学的注释上，尾递归循环 是 通常被认为是Haskell中的次优。通常，我们宁愿生成一个，而不是迭代地计算步骤中的结果 结构体 与叶子上的所有步长等价物，并在其上进行转换（如折叠）以产生最终结果。这是一个更高层次的事物视图，通过懒惰来提高效率（结构是在处理时构建和垃圾收集的，而不是一次性完成）。2
这可能需要一些人开始习惯，并且它肯定不会在所有情况下都有效 - 极其复杂的循环结构可能很难有效地转换3 - 但是直接将尾递归循环转换为Haskell可能会很痛苦，因为它并不是真正的惯用语。
至于您链接的粘贴， id $! x 不起作用任何东西，因为它是相同的 x `seq` id x，这是一样的 x `seq` x，这是一样的 x。基本上，每当 x `seq` y 被迫， x 被迫，结果是 y。你不能用 seq 在任意点强迫事物;你用它来导致thunk的强迫 依靠 在其他thunk上。
在这种情况下，问题是你正在建立一个大的thunk c，所以你可能想做 auxk 和 auxj 强迫它;一个简单的方法就是添加一个像这样的子句 auxj _ _ c _ | seq c False = undefined到定义的顶部。 （该 守卫 总是被检查，强迫 c 要评估，但总是导致 False，所以从不评估右侧。）
就个人而言，我建议保留最终版本中的爆炸模式，因为它更具可读性，但是 f c _ | seq c False = undefined 也会工作得很好。
1 看到 优雅的备忘录功能备忘录尝试 和 数据memocombinators 图书馆。
2 实际上，GHC通常甚至可以消除中间结构 完全 运用 融合和砍伐森林，生成类似于用低级命令式语言编写计算的机器代码。
3 虽然如果你有这样的循环，这种编程风格很可能会帮助你简化它们 - 懒惰意味着你可以轻松地将计算的独立部分分离成单独的结构，然后过滤和组合它们，而不用担心你会通过进行稍后将被丢弃的中间计算来复制工作。
好的，让我们在这里开始工作。
你有一个条目列表
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用于单独或同时评估。或者您可以向我们展示您的“真实”代码，也许我们可以帮助您找到重新排列数据依赖关系的方法;它可能会证明你没有 需要 总数，或类似的东西。