Can we construct an infinite list that satisfies a given bit predicate?

Question

If we have a given predicate p :: [Bool] -> Bool that take an infinite list as parameter and return True or False based on some unknown conditions, and we have no idea what this predicate is.

Can we work out a function f :: ([Bool] -> Bool) -> [Bool] that take such predicate and return an infinite list l where p l == True, assuming that the predicate is satisfiable.

Answer 1

You can think of an infinite list [Bool] as being a binary number with the least significant bit first:

0 = repeat False
1 = True : repeat False
2 = False : True : repeat False
3 = True : True : repeat False

and so on to infinity.

So if you construct a function like this:

intToBools :: Integer -> [Bool]

then you can write

f p = head $ filter p $ map intToBools [0..]

Will this work for every predicate p? Well, if we restrict ourselves to total functions then the p must inspect a finite prefix of its argument, and if any finite prefix is acceptable then that prefix must be reached eventually.

If p is not total but can return True for at least one argument (e.g. the predicate "argument contains at least one True"), then this problem cannot be solved as written because we can't know if p x will ever terminate. However if p could be expressed as a state machine:

newtype BoolPredicate = BoolPredicate (Bool -> Either Bool BoolPredicate)

then you could enumerate every possible input by recursively applying True and False to the output of the previous step in a breadth-first search until you find Left True.