5

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.

lucas
  • 53
  • 3
  • 4
    Reminds me of http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/ – alias Dec 08 '21 at 15:48

1 Answers1

5

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.

chepner
  • 497,756
  • 71
  • 530
  • 681
Paul Johnson
  • 17,438
  • 3
  • 42
  • 59
  • This computes an infinite list of (finite) lists that satisfy the predicate, not a single infinite list that satisfies the predicate. – chepner Dec 08 '21 at 17:12
  • 1
    No it doesn't. The outputs from `intToBools` are all infinite, its just that they all have a tail with an infinite list of `False` (so e.g. a list consisting of an infinite alternation of `True, False` will never be produced). But as long as `p` is total that doesn't matter. – Paul Johnson Dec 08 '21 at 17:20
  • Ah, missed that detail. – chepner Dec 08 '21 at 17:23