It's not immediately clear how to express this Haskell type in C:
data Tree = Leaf Int | Inner Tree Tree
Unlike languages like Haskell and Rust, C lacks built-in support for
disjoint unions. However, it does provide all the ingredients we need to represent them, if we're willing to do a little extra typing.
The first thing to realize is that a disjoint union consists of:
- A number of different variants
- Each of which has some data associated with it.
In our binary tree example, we have two variants: "leaf" and "inner". The leaf variant stores a single integer (its data), and the inner variant stores two Trees (representing its left and right children).
We can represent such an animal in C using a struct with two fields:
- A "type tag", typically an integer, indicating which variant is being represented.
- A data field which stores the data associated with the variant.
It's convenient to define the different variant type tags using an enum:
enum tree_type {
TREE_LEAF,
TREE_INNER,
};
What about storing the data? This is the type of problem that unions exist to solve.
Unions
A union is just a chunk of memory capable of storing a number of different types of data. For instance, here's a union that can store either a 32-bit int or an array of 5 chars.
union int_or_chars {
int num;
char letters[5];
};
A variable whose type is union int_or_chars can hold either an int or an array of 5 chars at any particular time (just not both at the same time):
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;
A union like union int_or_chars has at its disposal a chunk of memory big enough to hold the largest of its members. Here's a schematic showing how this works:
+ ---- + ---- + ---- + ---- + ---- +
| byte | | | | |
+ ---- + ---- + ---- + ---- + ---- +
|<-- int uses these 4 -->|
|<-- array of chars uses all 5 -->|
Which helps explain why printing quux.num resulted in "garbage" after we stored an array of chars in quux: it wasn't garbage, it was the string "abcd" being interpreted as an integer. (On my machine, quux.num is printed in hex as 64636261. The character 'a' has an ASCII value of 0x61, 'b' has a value of 0x62, 'c' is 0x63, and 'd' is 0x64. The order is reversed since my processor is little-endian.)
As a final note on unions, you might be surprised by the size reported by sizeof:
printf("%ld\n", sizeof(union int_or_chars));
// => 8
On my machine, the type union int_or_chars has a size of 8 bytes, not 5 like we might have expected. Some padding has been added because of alignment requirements stipulated by my processor's architecture.
Back to Binary Trees
We're now ready to continue translating the binary tree type from Haskell to C. We've already defined an enum to represent the variant's type. Now we need a union to store its data:
union tree_data {
int leaf;
struct inner_data inner;
};
where struct inner_data is a struct containing the left and right children of an "inner" variant:
struct inner_data {
struct tree *left;
struct tree *right;
};
Notice that the "inner" variant maintains pointers to its left and right children. The indirection is necessary because otherwise struct tree wouldn't have a fixed size.
With these pieces in place, we're ready to define our tree type:
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;
};
Playing with Trees
Let's write some functions to construct trees:
// 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;
}
and print them:
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;
}
}
This allows us to translate the Haskell expression:
Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)
into C as:
inner(inner(leaf(1), leaf(2)), leaf(3));
For example:
struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)
As a slightly more interesting example, let's translate this depth-first search function:
-- 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
Using our tree type:
// 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)
);
}
}
It's certainly more verbose, but the translation process is straightforward (to the extent that a compiler could presumably do this sort of thing for us...).
Tradeoffs
We end with a little digression about the tradeoffs involved in an alternative representation. Specifically, suppose instead of:
union tree_data {
int leaf;
struct inner_data inner;
};
we used:
union tree_data {
int leaf;
struct inner_data *inner;
// ^ The difference.
};
In the first case, the union contains a struct inner_data, whereas in the second it stores a pointer to this struct. As a result, the first union is a bit larger at 16 bytes, vs 8 for the pointer version on my machine. Unfortunately it's not just inner nodes that are affected: leaf nodes use this same 16-byte union but only store a single (4-byte) int. This feels a bit wasteful.
However, that's not the whole story. We're going to pay for the extra indirection every time we access the left and right children of an inner node: reads aren't necessarily cheap, particularly if the memory pointed to isn't cached.
I suspect the main approach presented here is a better starting point in most cases, and that trying to shave a few bytes (white incurring additional reads) just ain't worth it until it is.
Top comments (1)
Good write. Learned something new today