3 ms·
I have translated the pretty long Swift code belabored with manual laziness handling into Haskell where lists are inherently lazy: type BitSequence = [Bool
by kccqzy 8y ago
I have translated the pretty long Swift code belabored with manual laziness handling into Haskell where lists are inherently lazy:
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
- repsilat 8y ago> Here's an example when the function fails to terminate: I figured this seemed too good to be true. In fact, isn't there a simple reduction to the halting problem? Make a "sequence" i -> M halts in i steps for an arbitrary Turing Machine `M`. You can implement the "bit lookups" by simulating `M`. The author says their Swift code can run `anySatisfy` on this "sequence" in finite time, right? EDIT: quoted at the top, but afaict not mentioned later, the article says, >> It is well known that it is impossible to define equality between arbitrary functions. However, there is a large class of functions for which we can determine equality It would have been nice if the author had been explicit about the class of functions for which their program terminates.
- wz1000 8y agoIt works for any decidable/recursive predicate on bit sequences, i.e. one that is guaranteed to halt for any input. `and` on an infinite bit sequence is not guaranteed to halt because it is co-recursively enumerable, i.e. it will reject bit sequences that contain `False`, but it will not halt on bit sequences that contain only `True`, since to verify that a bit sequence only contains `True`, you have to check all elements of the sequence. In ghci, > and $ repeat True <doesn't terminate> > and $ (replicate 10000 True) ++ (False: repeat True) False
- repsilat 8y agoI noticed my post missed the point a bit... I was thinking about functions that check properties of bit sequences, not functions that check properties of predicates on bit sequences. I get how it works now, thanks. Wish I could edit/delete my old post :-/. Just to check my understanding: a terminating program that decides bit sequences will have - a maximum number of bit checks it will make regardless of input, and - a maximum bit index it will access regardless of input, and even - a maximum running time (measured however).
- tikhonj 8y agoIt's worth noting that the references in the blog post—including "Seemingly Impossible Functional Programs" which the title refers to—are all written in Haskell. Haskell is the natural setting to experiment with this kind of code.
- kccqzy 8y agoI have to make a correction in my earlier comment (can't edit any more). I previously stated that this has nothing to do with topology or continuous functions or compactness but in fact it does. It's actually a kind of Baire space. I'll try to more precisely explain this part that's only vaguely told as a story in the original article. So topologically a continuous function (from a topological space to another) is defined as one where the preimage of every open set is open. (This definition for real numbers is equivalent to the traditional epsilon-delta definition.) Now for bit sequences we can define a topology via neighborhoods: a neighborhood of a bit sequence is simply those that share a finite prefix. Then an open set means that for every point (bit sequence) in it, there's a finite prefix such that all sequences with this finite prefix are in the open set. Compare this with the traditional open set definition for real numbers: a set is open if for every real number in it, there's an epsilon-neighborhood such that all real numbers within this neighborhood are in the open set. In fact it's the same definition once we choose a definition for neighborhoods. Then for booleans we just use the discrete topology so any subset is open. So what I was saying in the parent comment (function only examining a finite prefix to produce a boolean) basically implies that it's continuous: for every possible output boolean, the preimage must consist of a union of neighborhoods with finite prefixes. So if a function only examines a finite prefix of a bit sequence, its preimage cannot be more than a union of neighborhoods. (On the other hand, it is possible that a function chooses to examine more than just a finite prefix and still be continuous. In this case we don't know that the function will throw away information gleaned from examining the infinite sequence. It just won't terminate.)
- Veedrac 8y agoI found it easier to read when `anySatisfy` was inlined: find :: (BitSequence -> Bool) -> BitSequence find p = if p (False : find (\s -> p (False : s))) then False : find (\s -> p (False : s)) else True : find (\s -> p (True : s))
- kccqzy 8y agoThat's slightly wrong. When you substitute the definition of anySatisfy, you need to note that it uses the argument p twice, so you need to substitute both uses, not just the second one.
- Veedrac 8y agoI did, anySatisfy (\s -> p (False : s)) ==> (\s -> p (False : s)) (find (\s -> p (False : s))) ==> p (False : find (\s -> p (False : s)))