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
...

Answer 2

没有叶子的无限二叉树的类型：

data Tree a = Tree (Tree a) a (Tree a)

执行此类操作的一种通用模式称为 unfold。对于此特定类型：

unfold :: (a -> (a,b,a)) -> a -> Tree b

您能看到如何定义此函数并将其用于您的目的吗？

Haskell 定义二叉树

Haskell Defining a Binary Tree

binary-tree

haskell

functional-programming