Haskell中的递归数据类型

Question

以下内容摘自 http://www.haskell.org 的一篇教程，考虑下面的定义：

data Tree a                = Leaf a | Branch (Tree a) (Tree a) 
fringe                     :: Tree a -> [a]
fringe (Leaf x)            =  [x]
fringe (Branch left right) =  fringe left ++ fringe right

我不太清楚函数fringe执行时运行时会发生什么。

在编译表达式fringe left时，（1）编译器是否已经知道left树是Branch还是Leaf - 即它只操作静态已知的树 - 还是（2）它会发出一些if/switch条件来检查left树是一个Leaf还是Branch。

如果是后者即（2），那么为什么这比等效的C函数更类型安全，基本上看起来与上面的代码类似，除了只有一个类型浮动（指向节点的指针）。

- MK.

---

答案是（2）。如果不是这样，fringe将不得不为每个二叉树“形状”生成单独的版本。类型安全是编译时评估的不同概念。 - Alec

“[...] 等效的 C 函数 [中] 只有一种类型存在”-- 但这里只有一种类型: Leaf "foo" 和 Branch (Leaf "foo") (Leaf "bar") 都具有相同的类型，即 Tree String。请注意，此处的翻译保留了原始语句的含义和上下文，并尽力使之更加易于理解，但并未添加任何额外信息或解释。 - duplode

Answer 1

This:

fringe (Leaf x)            =  [x]
fringe (Branch left right) =  fringe left ++ fringe right

这实际上等同于一个单变量函数，然后立即进行模式匹配：

fringe t = case t of
    Leaf x            -> [x]
    Branch left right -> fringe left ++ fringe right

因此，这回答了你第一个问题为(2)："它发出一些类似于case的条件，以检查左树是Leaf还是Branch。"

至于为什么它比在C语言中所做的更安全，那么，在C语言中你会怎么做呢？

通常情况下，您最终会存储一个标记的产品，它显示某个东西是Leaf还是Branch，以及有效负载，后者是a和(Tree a, Tree a)的未标记联合。然后，您编写的代码大致如下（这可能不是100％合法的C代码，但应该能说明问题）:

enum TreeTag { Tree_Leaf; Tree_Branch; };

struct Tree {
  TreeTag tag;
  union payload {
    struct { 
      int x;    // yeah let's not touch on parametric polymorphism here...
    } Leaf;
    struct {
      Tree l;
      Tree r;
    } Branch;
  };
};


switch (t.tag) {
  case Tree_Leaf: ... use t.payload.Leaf.x here
  case Tree_Branch: ... use t.payload.Branch.left and t.payload.Branch.right here
}

问题在于，没有任何静态防止您在“Tree_Leaf”情况下意外使用“t.payload.Branch.left”等内容。此外，没有任何静态防止您执行以下操作：

t.tag = Tree_Branch;
t.payload.Leaf.x = 42;

这可能导致"type" Tree的值无效。

- Cactus

---

此外，在C语言中，你不会从任何穷尽性/冗余性检查中受益，这些检查可以确保你没有忘记任何情况。 - ghilesZ

使用C11，可以使用相对简单的语法（利用匿名联合/结构体）编写标记联合。当然，仍然没有强类型安全性。 - chi