Should recursive function call terminate or is its implementation faulty?

Question

I'm working my way through Haskell Programming From First Principles and am stuck proving that I've correctly answered question 1 of the Finally something other than a list exercise subsection. The following function invocation doesn't terminate and I can't tell if that's expected or if my implementation is faulty.

data BinaryTree a = Leaf 
                  | Node (BinaryTree a) a (BinaryTree a) 
                    deriving (Eq, Ord, Show)

unfold :: (a -> Maybe (a, b, a)) -> a -> BinaryTree b
unfold func seed = 
  case (func seed) of
    Just (l, m, r) -> Node (unfold func l) m (unfold func r)
    Nothing -> Leaf

I would think that each a/x would eventually be decremented/incremented until it causes the if to take the True branch and return a Nothing/Leaf.

func = (\x -> if (x < 0 || x > 10) 
                then Nothing  
                else Just (x - 1, x, x + 1))
unfold func 5
-- Node (Node (Node (Node (Node (Node Leaf 0 ... ad infinitum

Answer 1

The reason the program never terminates can be understood if you try to invoke func outside unfold. Here, I renamed func to unfolder, because the Haskell linter didn't like that it had the same name as the func argument.

Close to the boundaries, unfolder returns these values:

*So> unfolder 1
Just (0,1,2)
*So> unfolder 0
Just (-1,0,1)
*So> unfolder (-1)
Nothing

For unfolder 0, the left branch clearly evaluates to Nothing the next time around, but the right branch is unfolder 1, which evaluates to Just (0,1,2), and so on ad infinitum.

Answer 2

Your implementation generates infinitely many calls to unfold.

Consider the first recursive call, where your initial seed value of 5 is split into 4 and 6 for the left and right subtree. There you split this new seed into 3 and 5 on the left and 5 and 7 on the right, hence you define an infinitely large tree.