递归函数调用应该终止还是它的实现是错误的？

Question

我正在从第一性原则开始Haskell编程，我一直在努力证明我已经正确地回答了最后一个问题的问题1，而不是列表练习小节。下面的函数调用不会终止，我无法判断这是预期的，还是我的实现是错误的。

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

我认为每个a/x最终都会减少/递增，直到它导致if接受True分支并返回一个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

您的实现会生成无限多个对unfold的调用。

考虑第一个递归调用，其中5的初始种子值被拆分为左和右子树的4和6。在这里，您将这个新种子拆分为左边的3和5，右边的5和7，因此您定义了一个无限大的树。

Answer 2

如果尝试在func之外调用unfold，则可以理解程序永不终止的原因。在这里，我将func重命名为unfolder，因为Haskell不喜欢它有与func参数相同的名称。

在边界附近，unfolder返回以下值：

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

对于unfolder 0，下一次左分支明显地计算为Nothing，但右边的分支是unfolder 1，它的计算结果为Just (0,1,2)，等等。