Wil*_*ess 11 haskell loops tail-call-optimization
所以我的问题的简短版本是,我们如何在Haskell 中编码循环呢？在Haskell中没有尾部优化保证,爆炸模式甚至不是标准的一部分(对吗？),并且折叠/展开范例不能保证在所有情况下都能工作.在这种情况下,只有爆炸模式才能让我在恒定的空间中运行(甚至没有使用$!帮助......虽然测试是在使用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中对上面的代码进行编码,以便在恒定的空间中运行？
这是测试代码.计算是假的,但问题是一样的.编辑:该foldr-formulated代码是:
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来优化代码.
非常感谢大家的帮助.
ehi*_*ird 15
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中有这么多:如果你的累加器参数不严格,当你以后试图强制它们时你会溢出堆栈,事实上,由于懒惰,许多非 -尾递归程序不会溢出堆栈; 打印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 c,所以你可能想制造auxk和auxj强制它; 一个简单的方法是添加一个类似于auxj _ _ c _ | seq c False = undefined定义顶部的子句.(始终检查防护装置,强制c进行评估,但总是导致False,因此永远不会评估右侧.)
就个人而言,我建议保留最终版本中的爆炸模式,因为它更具可读性,但f c _ | seq c False = undefined同样也可以.
1请参阅使用功能备忘录尝试的优雅记忆和data-memocombinators库.
2实际上,GHC通常甚至可以完全使用融合和砍伐森林来消除中间结构,产生的机器代码类似于用低级命令式语言编写计算的方式.
3虽然如果你有这样的循环,这种编程风格很可能会帮助你简化它们 - 懒惰意味着你可以轻松地将计算的独立部分分离成单独的结构,然后过滤和组合它们,而不必担心你'将通过进行稍后将被丢弃的中间计算来复制工作.