Is there any straightforward way to evaluate a recursive function breadth-first?

Question

Mind the following program:

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)

It implements a function foo that calls itself recursively in two branches, increasing the second argument as it recurses down the tree. It "should" return True if its second argument ever becomes equal to the first, which is the case, because ((0 * 2 + 1) * 2 + 1) * 2 == 10. But that doesn't happen, because Haskell gets stuck trying to evaluate the left branch depth-first.

Usually, this would be solved by implementing a BFS, but doing that is awkward in Haskell. I wonder if there is any automated, or at least less-obtrusive way to evaluate a recursive function breadth-first?

Answer 1

You can make the original code work with minimal tweaks using the unamb package. The key observation is that the "platonic" (||) is symmetric in that it can short-circuit in either direction; and unamb gives you a way to realize that.

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

Works, but leaves a zombie behind running at 100% CPU:

> foo 10 1
True

That's probably a bug, though I don't feel super into chasing it down just now...

P.S. I'd probably prefer this spelling of foo if you decide to use unamb, just because it's syntactically more compact than using guards:

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