Haskell 树遍历困惑

Question

我对 haskell 很陌生，我似乎无法理解这段代码：

data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)

-- animals tree 
animals :: Tree String
animals = Node "elephant"
              (Node "bat"
                   (Leaf "aardvark")
                   (Node "cow"
                        (Leaf "chicken")
                         Empty))
              (Node "hare"
                   (Node "fox"
                         Empty
                         (Leaf "goat"))
                   (Leaf "jackal"))

具体来说，创建该数据类型比我在课堂上尝试的简单数据类型更复杂。 Animals 函数创建了树，但是它如何利用该类型来实现这一点呢？

然后用这个函数遍历它：

traverse :: (Tree a) -> [a]
traverse Empty = []
traverse (Leaf x) = [x] --leaf returns list of 1 item
traverse (Node x left_sub_tree right_sub_tree) =
 (traverse left_sub_tree) ++
  [x] ++
 (traverse right_sub_tree)

我不确定这段代码是如何工作的，可能是因为我不确定该数据类型如何允许我们创建树。我基本上看不到类型创建之间的“链接”以及该算法如何使用这些函数类型来创建树。

帮助理解这一点将是令人难以置信的，谢谢！

Answer 1

数据类型递归地定义一棵树。树由单元组成，每个单元可以是“空”、“叶”或“节点”。 “Node”案例有 2 个子节点，它们也是树，这是递归定义。这个想法是，一棵树可以是空的，也可以是单个元素，或者是附加到另外两棵树的单个元素。

traverse

代码也可以递归地工作。如果遇到空树，则返回一个空列表。如果遇到单个元素，则会返回该元素。如果遇到“节点”，则对两个子树递归运行，然后用

++

运算符将结果组合起来。