Haskell中的二叉树类型构造函数 [英] Binary Tree type constructor in Haskell

问题描述

 数据Tree a = Leaf a |分支a（树a）（树a）
  

我们如何证明并非所有种类的二叉树都可以由此构造函数表示？我们如何改进这个定义来涵盖所有类型的二叉树？它是如何工作的？

解决方案

您树一个有类型的标签 a 在每个分支和每个叶子构造函数中。因此，例如， Branch'u'（Branch'n'（Leaf'i'）（Leaf'p'））（Leaf'z'）看起来像这样：

  +  - 'u' -  + 
 | | 
 +  - 'n' -  +'z'
 | | 
'i''p'
  

例如，排除了具有不同标签的树节点和树叶，或仅在内部或仅在外部标记的树。例如，这棵树的叶子上有数字，节点上有字符。

  +  - 'o' -  + 
 | | 
 +  - 'h' -  + 9 
 | | 
 7 2 
  



<您可以使用树（或nl） 但不包含只有 n s出现在内部且只有 l ）

由于这看起来是一项家庭作业，我不会告诉你更常见的树会是什么样子，但我确定你可以弄明白。

I'm trying binary tree type constructor which is:

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

How we prove that not all kinds of binary tree can be represented by this constructor? How we improve this definition to cover all types of binary tree? And how it works?

解决方案

Your Tree a has labels of type a at every Branch and every Leaf constructor. So, for example, Branch 'u' (Branch 'n' (Leaf 'i') (Leaf 'p')) (Leaf 'z') looks like this:

    +-'u'-+
    |     |
 +-'n'-+ 'z'
 |     |
'i'   'p'

That excludes, say, trees with different labels at the nodes and leaves, or trees that are labelled only internally or only externally. For example, this tree has numbers at the leaves and characters at the nodes.

    +-'o'-+
    |     |
 +-'h'-+  9
 |     |
 7     2

(You can use Tree (Either n l) but that doesn't encode the invariant that only ns appear internally and only ls appear externally.)

Since this appears to be a homework assignment I won't tell you what a more general type of tree might look like, but I'm sure you can figure it out.

这篇关于Haskell中的二叉树类型构造函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！