Não está imediatamente claro como expressar esse tipo Haskell em C:

data Tree = Leaf Int | Inner Tree Tree

Ao contrário de linguagens como Haskell e Rust, C não possui suporte integrado para
sindicatos disjuntos. No entanto, ele fornece todos os ingredientes que precisamos para representá-los, se estivermos dispostos a digitar um pouco mais.

A primeira coisa a perceber é que uma união disjunta consiste em:

• Várias variantes diferentes
• Cada um deles tem alguns dados associados a ele.

Em nosso exemplo de árvore binária, temos duas variantes: "leaf" e "inner". A variante folha armazena um único número inteiro (seus dados), e a variante interna armazena duas árvores (representando seus filhos esquerdo e direito).

Podemos representar tal animal em C usando uma struct com dois campos:

1. Uma "tag de tipo", normalmente um número inteiro, indicando qual variante está sendo representada.
2. Um campo dados que armazena os dados associados à variante.

É conveniente definir as diferentes tags de tipo de variante usando um enum:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

E quanto ao armazenamento dos dados? Este é o tipo de problema que os os sindicatos existem para resolver.

Sindicatos

Uma união é apenas um pedaço de memória capaz de armazenar vários tipos diferentes de dados. Por exemplo, aqui está uma união que pode armazenar um int de 32 bits ou uma matriz de 5 caracteres.

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

Uma variável cujo tipo é union int_or_chars pode conter um int ou um array de 5 caracteres em qualquer momento específico (mas não ambos ao mesmo tempo):

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;

Uma união como union int_or_chars tem à sua disposição um pedaço de memória grande o suficiente para armazenar o maior de seus membros. Aqui está um esquema que mostra como isso funciona:

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

O que ajuda a explicar por que imprimir quux.num resultou em "lixo" depois que armazenamos uma matriz de caracteres no quux: não era lixo, era a string "abcd" sendo interpretada como um número inteiro. (Na minha máquina, quux.num é impresso em hexadecimal como 64636261. O caractere 'a' tem um valor ASCII de 0x61, 'b' tem um valor de 0x62, 'c' é 0x63 e 'd' é 0x64. O a ordem é invertida porque meu processador é little-endian.)

Como observação final sobre sindicatos, você pode se surpreender com o tamanho relatado por sizeof:

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

Na minha máquina, o tipo union int_or_chars tem um tamanho de 8 bytes, e não 5 como esperávamos. Algum preenchimento foi adicionado devido aos requisitos de alinhamento estipulados pela arquitetura do meu processador.

Voltar para árvores binárias

Agora estamos prontos para continuar traduzindo o tipo de árvore binária de Haskell para C. Já definimos um enum para representar o tipo da variante. Agora precisamos de uma união para armazenar seus dados:

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

onde struct inner_data é uma struct contendo os filhos esquerdo e direito de uma variante "interna":

struct inner_data {
        struct tree *left;
        struct tree *right;
};

Observe que a variante "interna" mantém ponteiros para seus filhos esquerdo e direito. A indireção é necessária porque, caso contrário, a árvore de estrutura não teria um tamanho fixo.

Com essas peças no lugar, estamos prontos para definir nosso tipo de árvore:

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

Brincando com árvores

Vamos escrever algumas funções para construir árvores:

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

e imprima-os:

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

Isso nos permite traduzir a expressão Haskell:

Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)

em C como:

inner(inner(leaf(1), leaf(2)), leaf(3));

Por exemplo:

struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)

Como um exemplo um pouco mais interessante, vamos traduzir esta função de pesquisa em profundidade:

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

Usando nosso tipo de árvore:

// 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)
                );
        }
}

É certamente mais detalhado, mas o processo de tradução é direto (na medida em que um compilador poderia presumivelmente fazer esse tipo de coisa para nós...).

Compensações

Terminamos com uma pequena digressão sobre as compensações envolvidas em uma representação alternativa. Especificamente, suponha que em vez de:

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

usamos:

union tree_data {
        int leaf;
        struct inner_data *inner;
        //                ^ The difference.
};

No primeiro caso, a união contém uma estrutura inner_data, enquanto no segundo ela armazena um ponteiro para esta estrutura. Como resultado, a primeira união é um pouco maior, com 16 bytes, contra 8 para a versão do ponteiro na minha máquina. Infelizmente, não são apenas os nós internos que são afetados: os nós folha usam essa mesma união de 16 bytes, mas armazenam apenas um único int (4 bytes). Isso parece um pouco desperdiçador.

No entanto, essa não é toda a história. Pagaremos pela indireção extra toda vez que acessarmos os filhos esquerdo e direito de um nó interno: as leituras não são necessariamente baratas, principalmente se a memória apontada não estiver armazenada em cache.

Suspeito que a abordagem principal apresentada aqui é um ponto de partida melhor na maioria dos casos, e que tentar reduzir alguns bytes (branco incorrendo em leituras adicionais) simplesmente não vale a pena até que valha a pena.