树与否（Haskell类型理解）

Question

在"A Gentle Introduction to Haskell"中我们有这样的树类型声明：

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根本不是树，见：

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

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

Answer 1

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

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

即树中a2的两个"copies"

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

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

Answer 2

我们应该区分表达式的值和它的内存表示。

例如，这两个表达式具有相同的值:

e1 = ("Hello", "Hello")
e2 = let s = "Hello" in (s, s)

的确，在Haskell中没有办法区分上面表达式的求值结果。它们在语义上是等价的。

Haskell 实现（例如 GHC）可以自由地以任何不破坏语义的方式在内存中表示这些值。例如：

它可能会将字符串"Hello"存储在内存中两次，然后使用一对指针(p1, p2)。
它可能会在内存中存储一次字符串"Hello"，然后使用一对指针(p, p)。

请注意，从理论上讲，这两种表示都可以用于上述任何一个表达式 e1,e2。实际上，GHC 会将前者用于 e2，将后者用于 e1，但这并不重要。

在你的树中，同样的问题出现了。你的 a6 的值是一棵树。 GHC 可能将该树表示为非树 DAG（即，如果转换为无向图，则有一个循环的 DAG），但这并不重要，它只是一个实现细节。重要的方面是这种表示尊重树的语义。

然后有人可能想知道如果值是一棵树，为什么 DAG 表示是合理的。这是因为在 Haskell 中我们无法比较 GHC 使用的基础 "references" p。如果我们有一个比较此类引用的函数 comparePtr :: a -> a -> Bool，我们可以通过在 e1 之间使用 comparePtr (fst e) (snd e) 来区分 e1 和 e2，e2。这将严重破坏实施的稳健性。不过，在 Haskell 中我们没有。

（嗯，从技术上讲，有一个 unsafe 函数可以做到这一点，但是 unsafe 函数不应该在 "normal" 代码中使用。我们通常假装它们不存在。）

树与否（Haskell类型理解）

Tree or not (Haskell type understanding)

binary-tree

haskell

types

graph-theory