type BitSequence = [Bool]
allSatisfy :: (BitSequence -> Bool) -> Bool
allSatisfy p = not (anySatisfy (not . p))
anySatisfy :: (BitSequence -> Bool) -> Bool
anySatisfy p = p (find p)
find :: (BitSequence -> Bool) -> BitSequence
find p =
if anySatisfy (\s -> p (False : s))
then False : find (\s -> p (False : s))
else True : find (\s -> p (True : s))
The code still works the same. But now, it is clearer what actually happens. The lexical call chain goes like this: anySatisfy p
===>
find p
===>
anySatisfy (\s -> p (False : s))
===>
find (\s -> p (False : s))
===>
anySatisfy (\s -> (\s -> p (False : s)) (False : s))
===>
find (\s -> (\s -> p (False : s)) (False : s))
=== (by alpha conversion)
find (\s -> (\s1 -> p (False : s1)) (False : s))
=== (by beta reduction)
find (\s -> p (False : False : s))
where I used the long arrow to mean a deeper lexical call chain, and triple-equal to mean a single step of reduction and/or .In other words, as long as the given predicate p consumes a finite prefix of the infinite bit sequence to produce a result, this will successfully return a result. Which is quite intuitive because the function is essentially doing an exhaustive search. It has nothing to do with topology or continuous functions or compactness, IMO. It also has nothing to do with Curry–Howard correspondence.
Here's an example when the function fails to terminate:
anySatisfy and
Here's another example: let parity (False : s) = parity s; parity (True : s) = not (parity s) in anySatisfy parity