haskell 中的递归数据类型
recursive datatypes in haskell
考虑从 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
还是
a Leaf
- 即它只在静态已知的树上运行 - 或者(2)它是否发出一些 if
/switch
之类的条件来检查 left
树是否是 Leaf
或 Branch
如果是后者,即 (2),那么,为什么这应该比等效的 C 函数更类型安全,后者基本上看起来就像上面一样,只是只有一种类型浮动(指向节点)。
这个:
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):"it emit[s] some case
-like conditions to check if the left tree is a Leaf
or a Branch
".
至于为什么它比你在 C 中做的更安全,那么你会在 C 中做什么?
通常你最终会存储一个 product 的标签,它显示某物是 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
.
的无效值
考虑从 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
还是
a Leaf
- 即它只在静态已知的树上运行 - 或者(2)它是否发出一些 if
/switch
之类的条件来检查 left
树是否是 Leaf
或 Branch
如果是后者,即 (2),那么,为什么这应该比等效的 C 函数更类型安全,后者基本上看起来就像上面一样,只是只有一种类型浮动(指向节点)。
这个:
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):"it emit[s] some case
-like conditions to check if the left tree is a Leaf
or a Branch
".
至于为什么它比你在 C 中做的更安全,那么你会在 C 中做什么?
通常你最终会存储一个 product 的标签,它显示某物是 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
.