树与否(Haskell型理解)

Question

在"对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根本不是树,请参阅:

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

这个图表中有一个循环!怎么了？树的类型定义是否正确？或许,我不能在理解这个例子时遇到一些错误......

Answer 1

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

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

也就是说,a2树中有两个"副本" .

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

为了实际有一个循环,需要有一些能够同时到达a4和a5来自的概念a2,并且这种类型不提供任何这样的子到父链接的表示,这使得无法判断是否a4'左边的孩子和a5右边的孩子是同一个节点,或两个看起来完全相同的不同节点.对于此数据类型,区别根本不存在.

Answer 2

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

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

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

实际上,在Haskell中,没有办法区分上述表达式的评估结果.它们在语义上是等价的.

Haskell实现(例如GHC)可以以任何不破坏语义的方式自由地在内存中表示这些值.例如:

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

请注意,理论上,这两种表示都可以用于e1,e2上述任何一种表达式.在实践中,GHC将使用前者e2和后者e1,但这并不重要.

在你的树上,出现了同样的问题.你的价值a6是一棵树.GHC可能将树表示为非树DAG(即DAG,如果转换为无向图,则具有循环),但无关紧要,它只是一个实现细节.重要的方面是这种表示尊重树的语义.

然后人们可能想知道为什么如果值是树,DAG表示是合理的.这是因为在Haskell中我们无法比较pGHC使用的基础"引用" .如果我们有一个comparePtr :: a -> a -> Bool比较这些参考的功能,我们可以区分e1和e2使用comparePtr (fst e) (snd e),e之间e1,e2.这将严重打破执行的可靠性.但是在Haskell中,我们没有那个.

(从技术上讲,有一个unsafe函数可以做到这一点,但unsafe函数不应该用在"普通"代码中.我们通常假装那些不存在.)