Algorithms that don't terminate in a lazy language

Question

According to 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.

The former is of course well known, but the latter strikes me as, if true, considerably more than a mild shocker.

Does anyone know an algorithm that terminates in an eager language but not in a lazy one?

Answer 1

Wikipedia answers this question for lambda calculus: Lambda Calculus Reduction Strategies

The key parts are:

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

This shows an even stronger property of lazy evaluation: if there is an evaluation strategy that makes a particular program terminate, then the program also terminates with lazy evaluation. So in particular strict evaluation (applicative order) does not allow any program to terminate that loops under lazy evaluation.

The references on the wikipedia page provide proofs.

Answer 2

I'm going to go out on a limb and state that no algorithm that terminates in a pure functional eager environment, will fail to terminate in a pure functional lazy environment.

The article that was being discussed does not mention this, the comment is followed by a request for an example that is not meet. Therefore until an example is found I'm going to say no.