Should the recursive function call be interrupted or is it being implemented?
I am working through Haskell Programming From First Principles and I am stuck proving that I answered question 1 "Something other than a subsection" correctly. The next function call does not complete and I cannot tell if it was expected or if my implementation is wrong.
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
will eventually decrease / increase until it takes if
for a branch True
and returns 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
source to share
Your implementation generates an infinite number of calls unfold
.
Consider the first recursive call, where the initial seed value is 5
split into 4
and 6
for the left and right subtree. There, you will split this new seed into 3
both 5
left 5
and 7
right, so you define an infinitely large tree.
source to share
The reason the program never ends can be understood if you try to call func
outside unfold
. Here I renamed func
to unfolder
because the Haskell liner didn't like it having the same name as the argument func
.
Near borders, unfolder
returns the following values:
*So> unfolder 1
Just (0,1,2)
*So> unfolder 0
Just (-1,0,1)
*So> unfolder (-1)
Nothing
For the unfolder 0
left branch next time will evaluate as Nothing
, but the right branch unfolder 1
that evaluates as Just (0,1,2)
, etc. to infinity.
source to share