haskell - 有没有直接的方法来评估递归函数广度优先？

Question

注意以下程序:

foo :: Int -> Int -> Bool
foo n x | x == n    = True
foo n x | otherwise = foo n (x * 2) || foo n (x * 2 + 1)

main :: IO ()
main = print (foo 10 0)

它实现了一个函数foo，该函数在两个分支中递归地调用自身，并在沿着树递归时增加第二个参数。如果它的第二个参数等于第一个参数(这种情况)，它“应该”返回 True，因为 ((0 * 2 + 1) * 2 + 1) * 2 == 10. .但这并没有发生，因为 Haskell 在尝试以深度优先方式评估左分支时陷入困境。

通常，这可以通过实现 BFS 来解决，但在 Haskell 中这样做很尴尬。我想知道是否有任何自动化的或至少不那么引人注目的方法来评估递归函数广度优先？

Answer 1

您可以使用 unamb 只需进行最少的调整即可使原始代码正常工作包裹。关键的观察结果是“柏拉图式”(||) 是对称的，因为它可以在任一方向短路； UNMB 为您提供了一种实现这一点的方法。

foo :: Int -> Int -> Bool
foo n x | x == n    = True
foo n x | otherwise = foo n (x * 2) `por` foo n (x * 2 + 1)

可以工作，但留下了一个以 100% CPU 运行的僵尸:

> foo 10 1
True

这可能是一个错误，尽管我现在不太想追究它......

附注如果您决定使用 unamb，我可能更喜欢 foo 的这种拼写，因为它在语法上比使用防护更紧凑:

foo :: Int -> Int -> Bool
foo n x = x == n || por (foo n (2*x)) (foo n (2*x+1))