目前还不清楚如何在 C 中表达此 Haskell 类型：
data Tree = Leaf Int | Inner Tree Tree
与 Haskell 和 Rust 等语言不同，C 缺乏对
的内置支持
不相交的联合。然而，如果我们愿意做一些额外的输入，它确实提供了代表它们所需的所有成分。
首先要认识到的是，不相交的并集包括：
在我们的二叉树示例中，我们有两个变体：“叶子”和“内部”。叶变量存储单个整数（其数据），内部变量存储两棵树（代表其左子树和右子树）。
我们可以使用具有两个字段的结构在 C 中表示这样的动物：
使用枚举定义不同的变体类型标签很方便：
enum tree_type {
TREE_LEAF,
TREE_INNER,
};
存储数据怎么样？这就是工会存在要解决的问题类型。
联合只是一块能够存储多种不同类型数据的内存。例如，这是一个可以存储 32 位 int 或 5 个字符数组的联合。
union int_or_chars {
int num;
char letters[5];
};
类型为 union int_or_chars 的变量可以在任何特定时间保存 int 或 5 个字符的数组（但不能同时保存）：
union int_or_chars quux;
// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42
// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd
// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261
return 0;
像 union int_or_chars 这样的联合拥有足够大的内存块可供使用，可以容纳其最大的成员。这是显示其工作原理的示意图：
+ ---- + ---- + ---- + ---- + ---- + | byte | | | | | + ---- + ---- + ---- + ---- + ---- + |<-- int uses these 4 -->| |<-- array of chars uses all 5 -->|
这有助于解释为什么在我们在 quux 中存储字符数组后打印 quux.num 会导致“垃圾”：它不是垃圾，而是字符串“abcd”被解释为整数。 （在我的机器上，quux.num 以十六进制打印为 64636261。字符“a”的 ASCII 值为 0x61，“b”的值为 0x62，“c”为 0x63，“d”为 0x64。由于我的处理器是小端字节序，所以顺序颠倒了。）
关于联合的最后一点，您可能会对 sizeof 报告的大小感到惊讶：
printf("%ld\n", sizeof(union int_or_chars));
// => 8
在我的机器上，union int_or_chars 类型的大小为 8 个字节，而不是我们预期的 5 个字节。由于我的处理器架构规定的对齐要求，已添加一些填充。
我们现在准备继续将二叉树类型从 Haskell 转换为 C。我们已经定义了一个枚举来表示变体的类型。现在我们需要一个联合来存储其数据：
union tree_data {
int leaf;
struct inner_data inner;
};
其中 struct inner_data 是包含“内部”变体的左右子级的结构：
struct inner_data {
struct tree *left;
struct tree *right;
};
请注意，“内部”变体维护着指向其左子节点和右子节点的指针。间接是必要的，因为否则结构树将没有固定的大小。
这些部分就位后，我们就可以定义我们的树类型了：
enum tree_type {
TREE_LEAF,
TREE_INNER,
};
struct tree;
struct inner_data {
struct tree *left;
struct tree *right;
};
union tree_data {
int leaf;
struct inner_data inner;
};
// A representation of a binary tree.
struct tree {
enum tree_type type;
union tree_data data;
};
让我们编写一些函数来构造树：
// Construct a leaf node.
struct tree *leaf(int value) {
struct tree *t = malloc(sizeof(*t));
t->type = TREE_LEAF;
t->data.leaf = value;
return t;
}
// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
struct tree *t = malloc(sizeof(*t));
t->type = TREE_INNER;
t->data.inner.left = left;
t->data.inner.right = right;
return t;
}
并打印它们：
void print_tree(struct tree *t) {
switch (t->type) {
case TREE_LEAF:
printf("%d", t->data.leaf);
return;
case TREE_INNER:
printf("(");
print_tree(t->data.inner.left);
printf(" ");
print_tree(t->data.inner.right);
printf(")");
return;
}
}
这使我们能够翻译 Haskell 表达式：
Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)
转换成 C 为：
inner(inner(leaf(1), leaf(2)), leaf(3));
例如：
struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3)); print_tree(t); // => ((1 2) 3)
作为一个稍微有趣的例子，我们来翻译一下这个深度优先搜索函数：
-- Check if a value is in a tree. search :: Int -> Tree -> Bool search v (Leaf w) = v == w search v (Inner l r) = search v l || search v r
使用我们的树类型：
// Check if a value is in a tree.
int search(int value, struct tree *t) {
switch (t->type) {
case TREE_LEAF:
return t->data.leaf == value;
case TREE_INNER:
return (
search(value, t->data.inner.left) ||
search(value, t->data.inner.right)
);
}
}
这当然更冗长，但翻译过程很简单（编译器大概可以为我们做这种事情......）。
我们最后稍微题外话一下替代表示中涉及的权衡。具体来说，假设不是：
union tree_data {
int leaf;
struct inner_data inner;
};
我们使用：
union tree_data {
int leaf;
struct inner_data *inner;
// ^ The difference.
};
在第一种情况下，联合体包含一个结构体inner_data，而在第二种情况下，它存储一个指向该结构体的指针。因此，第一个联合体稍大一些，为 16 字节，而我的机器上的指针版本为 8 字节。不幸的是，受影响的不仅仅是内部节点：叶节点使用相同的 16 字节联合，但仅存储单个（4 字节）int。感觉有点浪费。
然而，这并不是故事的全部。每次访问内部节点的左子节点和右子节点时，我们都会为额外的间接寻址付出代价：读取不一定便宜，特别是在指向的内存未缓存的情况下。
我怀疑这里提出的主要方法在大多数情况下是一个更好的起点，并且尝试削减一些字节（白色导致额外的读取）是不值得的，直到它成为现实。
以上是C 中的不相交联合的详细内容。更多信息请关注PHP中文网其他相关文章！
