この Haskell 型を C:
で表現する方法はすぐにはわかりません。

data Tree = Leaf Int | Inner Tree Tree

Haskell や Rust などの言語とは異なり、C には
の組み込みサポートがありません。 素の結合。ただし、もう少し入力を加えても、表現するために必要なすべての要素が提供されます。

最初に理解すべきことは、素の結合は次のもので構成されているということです:

• さまざまなバリアント
• それぞれに、データが関連付けられています。

バイナリ ツリーの例には、「リーフ」と「インナー」という 2 つのバリアントがあります。リーフ バリアントは 1 つの整数 (そのデータ) を格納し、内部バリアントは 2 つのツリー (その左右の子を表す) を格納します。

2 つのフィールドを持つ構造体を使用して、C でこのような動物を表すことができます:

1. どのバリアントが表現されているかを示す「型タグ」。通常は整数です。
2. バリアントに関連付けられたデータを保存する data フィールド。

列挙型を使用してさまざまなバリアント型のタグを定義すると便利です:

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 |      |      |      |      |
  ----   ----   ----   ----   ----  
||
||

これは、quux に文字の配列を格納した後、quux.num を印刷すると「ガベージ」が発生する理由を説明するのに役立ちます。これはガベージではなく、文字列「abcd」が整数として解釈されたためです。 (私のマシンでは、quux.num は 64636261 と 16 進数で表示されます。文字「a」の ASCII 値は 0x61、「b」の値は 0x62、「c」は 0x63、「d」は 0x64 です。私のプロセッサはリトルエンディアンなので、順序が逆になります。)

共用体に関する最後の注意として、sizeof:
によって報告されるサイズに驚かれるかもしれません。

printf("%ld\n", sizeof(union int_or_chars));
// => 8

私のマシンでは、union int_or_chars 型のサイズは、予想されていた 5 バイトではなく、8 バイトです。私のプロセッサのアーキテクチャで規定されているアライメント要件のため、一部のパディングが追加されています。

二分木に戻る

これで、バイナリ ツリー型を Haskell から C に変換し続ける準備ができました。バリアントの型を表す enum をすでに定義しました。次に、データを保存するためのユニオンが必要です:

union tree_data {
        int leaf;
        struct inner_data inner;
};

ここで、struct inner_data は、「inner」バリアントの左右の子を含む構造体です:

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.
};

最初のケースでは、共用体には struct inner_data が含まれますが、2 番目のケースでは、この構造体への ポインタ が格納されます。その結果、最初の共用体は 16 バイトと少し大きくなります。これに対し、私のマシンのポインター バージョンでは 8 バイトです。残念ながら、影響を受けるのは内部ノードだけではありません。リーフ ノードはこれと同じ 16 バイトの共用体を使用しますが、単一 (4 バイト) int のみを格納します。ちょっともったいない気がします。

しかし、それだけではありません。内部ノードの左右の子にアクセスするたびに、追加の間接費を支払うことになります。特に、指すメモリがキャッシュされていない場合、読み取りは必ずしも安価であるとは限りません。

ここで紹介する主なアプローチは、ほとんどの場合、より良い出発点であると思います。また、数バイト (追加の読み取りが発生する白) を削減しようとしても、それが実現するまでは価値がないと思います。