haskell - 递归函数调用应该终止还是其实现有问题？

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

如果您尝试调用func，就可以理解程序永远不会终止的原因。外面unfold 。在这里，我重命名为func至unfolder ，因为 Haskell linter 不喜欢它与 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) ，如此循环往复。