c - 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 函数更类型安全，后者基本上看起来就像上面一样，只是只有一种类型 float (指向节点的指针) .

Answer 1

这个:

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):“它发出 [s] 一些类似 case 的条件来检查左树是 Leaf 还是分支”。

至于为什么它比你用 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;

这将导致“类型”Tree 的无效值。