functional-programming - 不会以惰性语言终止的算法

Question

根据 http://www.reddit.com/r/programming/comments/gwqa2/the_real_point_of_laziness/c1rslxk

Some algorithms don't terminate in an eager language, that do in a lazy one, and (a mild shocker for me to find,) vice-versa.

前者当然是众所周知的，但后者让我印象深刻，如果是真的，那不仅仅是一个轻微的震惊。

有谁知道一种以急切语言终止但不以懒惰语言终止的算法？

Answer 1

维基百科为 lambda 演算回答了这个问题:Lambda Calculus Reduction Strategies

关键部分是:

Applicative order is not a normalising strategy. [...] In contrast, normal order is so called because it always finds a normalising reduction if one exists.

这显示了惰性求值的一个更强大的特性:如果存在使特定程序终止的求值策略，那么程序也会以惰性求值终止。因此，特别是严格评估(应用顺序)不允许任何程序在惰性评估下终止该循环。

维基百科页面上的引用资料提供了证据。