haskell - 树与否(Haskell 类型理解)

Question

在“A Gentle Introduction to Haskell”中，我们有这样的 Tree 类型声明:

data Tree a = Leaf a | Branch (Tree a) (Tree a)
     deriving (Eq,Ord,Show,Read)

让我们创建一些这种类型的值:

a1 = Leaf 1
a2 = Leaf 2
a3 = Leaf 3
a4 = a1 `Branch` a2
a5 = a2 `Branch` a3
a6 = a4 `Branch` a5

在ghci中:

*Main> :t a6
a6 :: Tree Integer

但是 a6 根本不是 Tree，请参阅:

      a6
     / \
   a4   a5
  / \  /  \
a1   a2    a3

这个图中有一个循环!
怎么了？ Tree 的类型定义是否正确？
或者，我在理解这个例子时无法发现一些错误......

Answer 1

简短的回答是，从概念上讲， a2 "is" Tree a ，而不是对 Tree a 的引用。从这个意义上说，a6 真的看起来像

          a6
       /      \
     a4        a5
    /   \    /    \
  a1   a2   a2    a3

也就是说，树中有两个 a2 的“副本”。

实际上，由于所有值都是不可变的，因此实现可以使用相同的内存来表示 a4 的右 child 和 a5 的左 child ，但是这两个节点在 Tree a 类型表示的抽象级别上保持不同。

为了真正有一个循环，需要有一些能够从 a4 到达 a5 和 a2 的概念，并且这种类型不提供任何此类 child-to-parent 链接的表示，这使得不可能判断 a4 的左 child 和 a5 的右 child 是同一个节点，还是两个看起来完全相似的不同节点。对于这种数据类型，根本不存在区别。