返回無限樹在Haskell

只包含節點的考慮下面的簡單Tree返回無限樹在Haskell

data Tree = 
    Leaf 
    | Node Tree Tree 
    deriving (Eq, Show)

是有辦法恢復使用遞歸節點的無限量（一個Tree只有Nodes，無葉）？

到目前爲止，我只知道如何返回數據類型，如Boolean和Integer。我該如何着手返回Tree？

來源

2014-11-08 user3277633

順便說一句，這是一個有趣的實際應用程序是純粹的功能memoization（緩存，基本上）。使用從函數輸入派生的二進制序列（例如，右，左，右對應二進制101，一個整數輸入）對樹進行索引，並向「Node」構造函數添加一個額外的參數，併爲其填充函數結果節點的索引。然後感謝懶惰，即使樹是無限的，每個值只會根據需要計算一次。 – 2014-11-08 23:31:42

infiniteTree :: Tree 
infiniteTree = Node infiniteTree infiniteTree

來源

2014-11-08 23:16:39

這也是學習['fix]]的好時機（http://hackage.haskell.org/package/base-4.7.0.1/docs/Data-Function.html#v:fix）：'infiniteRightTree =修復（樹葉）'，'infiniteLeftTree =修復（翻轉樹葉）'， – rampion 2014-11-08 23:40:49

謝謝，我會研究它！ – user3277633 2014-11-08 23:48:39

@rampion你的意思是'修復（Node Leaf）'。 :) – 2014-11-09 15:00:53

定義無限樹的另一種方法是使用Cofree comonad。

無限二叉樹：

import Data.Functor.Product 
import Data.Functor.Identity 
import Control.Comonad 
import Control.Comonad.Trans.Cofree 

binaryTreeOfBs :: Cofree (Product Identity Identity) Char 
binaryTreeOfBs = cofree $ 'b' :< Pair (Identity binaryTreeOfBs) 
             (Identity binaryTreeOfBs)

無限玫瑰樹：

roseTreeOfBs :: Cofree [] Char 
roseTreeOfBs = cofree $ 'b' :< [roseTreeOfBs]

您可以使用所有的comonad功能在他們身上，例如像extract在頭節點來獲取值：

>>> extract roseTreeOfBs 
'b'

而且您可以使用coiterT函數展開樹木：

linearRoseTreeOfIncreasingIntegers :: Cofree [] Integer 
linearRoseTreeOfIncreasingIntegers = coiterT (pure . fmap succ) (Identity 1)

來源

2014-11-09 09:59:05 danidiaz

返回無限樹在Haskell

回答

相關問題