Haskell 定义二叉树

Question

我想在 Haskell 中使用 infinitree :: Tree 定义一个无限树，但想为每个节点设置一个模式，定义每个节点应该是什么。该模式比其父模式多 1。我正在为如何建立一棵树而苦苦挣扎，以及如何以及在何处定义每个节点的模式？

谢谢

Answer 1

无限数据结构通常可以由调用自身但没有基本情况的函数定义。通常这些函数不需要对其参数进行模式匹配。例如，一个等于的列表[1..]可以写成

infiniteList :: [Int]
infiniteList = go 1 where 
  go n = n : go (n+1) 

您可以对树使用完全相同的技术：

data Tree a = Node (Tree a) a (Tree a) | Nil deriving (Show)

infiniteTree :: Tree Int 
infiniteTree = go 1 where 
  go n = Node (go (2*n)) n (go (2*n+1))

这定义了无限树

   1 
 /   \
 2   3 
/ \ / \
4 5 6 7
...