我们可以构造一个满足给定位谓词的无限列表吗？

Question

如果我们有一个给定的谓词p :: [Bool] -> Bool，它以一个无限列表作为参数，returnTrue或False基于一些未知的条件，我们没有想知道这个谓词是什么。

我们可以计算出一个函数 f :: ([Bool] -> Bool) -> [Bool] 接受这样的谓词和 return 一个无限列表 l 其中 p l == True，假设谓词是可满足的。

Answer 1

您可以将无限列表 [Bool] 视为二进制数，最低有效位在前：

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

以此类推直到无穷大。

因此，如果您构造这样的函数：

intToBools :: Integer -> [Bool]

那你可以写

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

这是否适用于每个谓词 p？好吧，如果我们将自己限制在总函数上，那么 p 必须检查其参数的有限前缀，如果任何有限前缀是可接受的，那么最终必须达到该前缀。

如果 p 不是全部但可以 return True 对于至少一个参数（例如谓词“参数包含至少一个 True”），则这个问题不能像写的那样解决，因为我们不知道 p x 是否会终止。但是，如果 p 可以表示为状态机：

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

然后您可以通过在广度优先搜索中递归地将 True 和 False 应用于上一步的输出来枚举每个可能的输入，直到找到 Left True.

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