Re:Seemingly impossible functional programs (2007)
by evanpw on Tuesday November 17, 2015 @02:25PM
(#10583370)
This is exactly right. The lazy version seems like magic, but it's really just exploiting the fact that if computing p(a) never evaluates a(n) for n >= m, then p(b) = p(a) whenever the first m elements of a and b agree, so you can cut off an infinite portion of the search space without checking them all.
I wrote up a Python gist (https://gist.github.com/evanpw/d69f1ccb5edd0b672e9e) which performs this same trick by explicitly snooping on the callbacks. It seems a lot less magical than the Haskell version.
EDIT: The main "cheat" seems to be the ability to identify the predicate which returns false on every input (e.g., by seeing if returns false without evaluating its argument). The continuity argument described in the article basically says that if p is not always false, then there's some input a with a(n) = 0 for all sufficiently large n that causes p to return true, so you could just enumerate all such inputs until one returns true.
As a result, laziness reveals information about a function's implementation in a way that strict evaluation does not. It matters which parts of the input a function actually reads.
Similarly, in non-lazy languages, functions that take callbacks reveal information about themselves by calling the callback (or not). We can write tests demonstrating the order in which a function calls its callback.