Не сразу понятно, как выразить этот тип Haskell в C:

data Tree = Leaf Int | Inner Tree Tree

В отличие от таких языков, как Haskell и Rust, в C отсутствует встроенная поддержка
непересекающиеся союзы. Тем не менее, он предоставляет все ингредиенты, необходимые для их представления, если мы готовы немного больше печатать.

Первое, что нужно осознать, это то, что непересекающийся союз состоит из:

• Несколько различных вариантов
• Каждый из которых связан с некоторыми данными.

В нашем примере с двоичным деревом у нас есть два варианта: «листовой» и «внутренний». Листовой вариант хранит одно целое число (его данные), а внутренний вариант хранит два дерева (представляющие его левого и правого дочерних элементов).

Мы можем представить такое животное на языке C, используя структуру с двумя полями:

1. Тег типа, обычно целое число, указывающее, какой вариант представлен.
2. Поле данных, в котором хранятся данные, связанные с вариантом.

Теги различных типов вариантов удобно определять с помощью перечисления:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

А как насчет хранения данных? Это тот тип проблем, для решения которых существуют профсоюзы.

Союзы

Объединение — это просто участок памяти, способный хранить несколько различных типов данных. Например, вот объединение, которое может хранить либо 32-битное целое число, либо массив из 5 символов.

union int_or_chars {
        int num;
        char letters[5];
};

Переменная типа Union int_or_chars может содержать либо целое число, либо массив из 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;

Объединение, подобное объединению int_or_chars, имеет в своем распоряжении участок памяти, достаточно большой для хранения самого большого из его членов. Вот схема, показывающая, как это работает:

  ----   ----   ----   ----   ----  
| byte |      |      |      |      |
  ----   ----   ----   ----   ----  
||
||

Это помогает объяснить, почему печать quux.num привела к «мусору» после того, как мы сохранили массив символов в quux: это был не мусор, это была строка «abcd», интерпретируемая как целое число. (На моей машине quux.num печатается в шестнадцатеричном виде как 64636261. Символ «a» имеет значение ASCII 0x61, «b» имеет значение 0x62, «c» — 0x63, а «d» — 0x64. порядок обратный, так как мой процессор имеет прямой порядок байтов.)

И последнее замечание по поводу объединений: вы можете быть удивлены размером, сообщенным sizeof:

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

На моей машине объединение типов int_or_chars имеет размер 8 байт, а не 5, как мы могли ожидать. Некоторые дополнения были добавлены из-за требований к выравниванию, предусмотренных архитектурой моего процессора.

Вернемся к двоичным деревьям

Теперь мы готовы продолжить перевод типа двоичного дерева с Haskell на C. Мы уже определили перечисление для представления типа варианта. Теперь нам нужен союз для хранения данных:

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

где struct Internal_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.
};

В первом случае объединение содержит структуру Internal_data, тогда как во втором он хранит указатель на эту структуру. В результате первое объединение немного больше и составляет 16 байт по сравнению с 8 для версии с указателем на моей машине. К сожалению, затронуты не только внутренние узлы: листовые узлы используют то же самое 16-байтовое объединение, но хранят только одно (4-байтовое) целое число. Это кажется немного расточительным.

Однако это еще не все. Нам придется платить за дополнительную косвенность каждый раз, когда мы обращаемся к левому и правому дочернему узлу внутреннего узла: чтение не обязательно дешево, особенно если память, на которую указывает, не кэшируется.

Я подозреваю, что основной подход, представленный здесь, является лучшей отправной точкой в ​​большинстве случаев, и что попытка сократить несколько байтов (белые влекут за собой дополнительные чтения) просто не стоит того, пока это не произойдет.