嚴格指導遞歸？

比方說，我們有一個簡單的樹在Haskell創建算法：嚴格指導遞歸？

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

makeTree :: Tree Int -> Tree Int 
makeTree (Node 0 l r) = Node 0 EmptyTree EmptyTree 
makeTree (Node n l r) = Node n (makeTree $ newTree (n - 1)) 
           (makeTree $ newTree (n - 1)) 
    where 
    newTree n = Node n EmptyTree EmptyTree

對於非常大的數字，我們希望這個算法失敗，一個「堆棧大小溢出」錯誤。這是因爲該算法是二進制遞歸，而不是尾遞歸。我可以使用bang模式（在產生的左子樹「！（makeTree $ newTree（n-1））」）引導二進制遞歸進入尾遞歸，因爲遞歸現在應該由於嚴格性而定向？

編輯：

事實證明，真正的問題是沒有樹的創作，但功能消耗的樹。有用來壓平樹的另一個功能，其中實例如下：因此

import qualified Data.Foldable as F 

instance F.Foldable Tree where 
    foldMap f EmptyTree = mempty 
    foldMap f (Node x l r) = F.foldMap f l `mappend` 
          f x   `mappend` 
          F.foldMap f r 

flatten = F.foldMap (:[])

調用樹的扁平化，這是可能在這些地方發生溢出。如果是這樣，解決方案就像假設將foldl轉換爲foldl'一樣簡單？還是二元摺疊會增加額外的問題？

來源

2013-07-28 user1104160

咦？即使這是嚴格的，這些遞歸也不能是尾部的，因爲尾部調用必須是函數的最後一件事。在這裏你也調用了這兩個遞歸之後調用Node構造函數。 – tohava

這段代碼是不可編譯的 –

如果你修復了編譯的代碼，這個函數就不會發生堆棧溢出。懶惰有幫助... – augustss

我假設你的意思是創建一個非常深樹，像

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

makeTree :: Int -> Tree Int 
makeTree 0 = EmptyTree 
makeTree n = Node n (makeTree (n - 1)) (makeTree (n - 1))

的關鍵是，Haskell是懶惰。所以在調用該函數之後，除了thunk之外，沒有實際創建任何內容，需要時進行評估。沒有分配到堆棧，因爲makeTree的調用不涉及遞歸調用。在檢查根節點之後，將調用遞歸調用，但也只調用一個級別。這意味着檢查每個節點僅花費一些有限的時間和內存（在這種情況下是常量），而不取決於樹的深度。重要的屬性是每個遞歸調用都在構造函數中。這有時稱爲corecursion或守護遞歸。

堆棧溢出可能會發生在使用該樹的函數中，但這是另一回事。

來源

2013-07-28 15:54:51

有趣的，我想我做了一個愚蠢的假設，樹的創建是問題。然後是的，我以後會消耗這棵樹（我把樹壓扁了）。這個可摺疊樹的實例在編輯的問題中。雖然（如果這真的發生了），爲什麼thunk會出現在摺疊而不是樹的創建中？是什麼讓這個foldMap實例變得不同？ – user1104160

@ user1104160想象一下Haskell的數據像數學對象。當你「創造」他們時，他們不存在。他們只是在沉睡，就像數學物體在我們的想象中一樣。由於懶惰，Haskell只在需要時纔開始創建它們。 –

所以你說的是，我不應該得到一個堆棧大小溢出與平坦的樹，因爲它遍歷整個樹就像創建樹一樣，所以相同數量的「只有當需要」被執行？ – user1104160

嚴格指導遞歸？

回答

相關問題