Haskell的树木

Question

还在学习haskell,我真的看不出它们之间的区别

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]",它将其定义为Rose树.