再帰関数呼び出しが終了するか、その実装に誤りがありますか？

Question

私はのハスケルプログラミングから私が正しくの質問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 

私はそれがTrue枝を取り、Nothing/Leafを返すようにifの原因となるまで、各a/xは、最終的にインクリメント/デクリメントされることをを思うだろう。

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引数と同じ名前を持つのが好きではなかったからです。 が枝明確周り次回Nothingに評価を残し、unfolder 0については

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

が、右ブランチがあると評価され、unfolder 1です：境界に近く

は、 unfolderこれらの値を返します。 Just (0,1,2)など、無期限に。