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

• A+
Category：Languages

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?

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)) ``