树木在Haskell

Question

仍在学习哈斯克尔，我实在看不出

data Tree a = Leaf a | Branch [Tree a] 

和

data Tree a = Leaf a | Branch (Tree a) (Tree a) 

什么是最好根据你之间的区别？这两种写作方式的含义是什么？

Answer 1

第一个分支包含树的列表，因此可能包含任意数量的子树。第二个是明确的两个子树，因此是二叉树。

Answer 2

前者定义了一棵树，其中每个分支可以有任意多个子树（表示为树列表），而后者定义了一棵树，其中每个分支恰好具有两棵子树。

换句话说，前者是一般树，后者是二叉树。

那么选择哪一个取决于您是要对一般树还是二叉树进行建模。

Answer 3

我已经把这个作为一个答案，而不是评论，因此有一定的格式：

data Rose a = Branch a [Rose a] 
    deriving (Show) 


sample1 :: Rose Int 
sample1 = Branch 1 [Branch 2 [], Branch 3 [Branch 5 []], Branch 4 []] 

这是一样的库模块Data.Tree，虽然Data.Tree采用现场标签和一个键入同义词。

我已经看到这棵树和你的第一个定义叫做“玫瑰树”，虽然它们有稍微不同的形状，所以术语似乎并不完全精确。我的解释是，它是嵌入在单个递归构造函数中的列表“[Rose a]”，它将其定义为玫瑰树。