返回无限树在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

回答

相关问题