No está claro de inmediato cómo expresar este tipo de Haskell en C:

data Tree = Leaf Int | Inner Tree Tree

A diferencia de lenguajes como Haskell y Rust, C carece de soporte integrado para
uniones disjuntas. Sin embargo, proporciona todos los ingredientes que necesitamos para representarlos, si estamos dispuestos a escribir un poco más.

Lo primero que debemos tener en cuenta es que una unión disjunta consta de:

• Varias variantes diferentes
• Cada uno de los cuales tiene algunos datos asociados.

En nuestro ejemplo de árbol binario, tenemos dos variantes: "hoja" e "interior". La variante hoja almacena un único número entero (sus datos) y la variante interna almacena dos árboles (que representan a sus hijos izquierdo y derecho).

Podemos representar dicho animal en C usando una estructura con dos campos:

1. Una "etiqueta de tipo", normalmente un número entero, que indica qué variante se está representando.
2. Un campo de datos que almacena los datos asociados con la variante.

Es conveniente definir las diferentes etiquetas de tipo de variante usando una enumeración:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

¿Qué pasa con el almacenamiento de datos? Este es el tipo de problema que los sindicatos existen para resolver.

Sindicatos

Una unión es solo un trozo de memoria capaz de almacenar varios tipos diferentes de datos. Por ejemplo, aquí hay una unión que puede almacenar un int de 32 bits o una matriz de 5 caracteres.

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

Una variable cuyo tipo es union int_or_chars puede contener un int o una matriz de 5 caracteres en cualquier momento determinado (pero no ambos al mismo tiempo):

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;

Un sindicato como el int_or_chars tiene a su disposición una porción de memoria lo suficientemente grande como para albergar al mayor de sus miembros. Aquí hay un esquema que muestra cómo funciona esto:

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

Lo que ayuda a explicar por qué la impresión de quux.num resultó en "basura" después de que almacenamos una serie de caracteres en quux: no era basura, era la cadena "abcd" interpretada como un número entero. (En mi máquina, quux.num está impreso en hexadecimal como 64636261. El carácter 'a' tiene un valor ASCII de 0x61, 'b' tiene un valor de 0x62, 'c' es 0x63 y 'd' es 0x64. el orden se invierte ya que mi procesador es little-endian.)

Como nota final sobre los sindicatos, es posible que te sorprenda el tamaño informado por sizeof:

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

En mi máquina, el tipo union int_or_chars tiene un tamaño de 8 bytes, no 5 como podríamos haber esperado. Se agregó algo de relleno debido a los requisitos de alineación estipulados por la arquitectura de mi procesador.

Volver a árboles binarios

Ahora estamos listos para continuar traduciendo el tipo de árbol binario de Haskell a C. Ya hemos definido una enumeración para representar el tipo de variante. Ahora necesitamos un sindicato para almacenar sus datos:

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

donde struct internal_data es una estructura que contiene los hijos izquierdo y derecho de una variante "interna":

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

Observe que la variante "interna" mantiene punteros a sus hijos izquierdo y derecho. La dirección indirecta es necesaria porque de lo contrario el árbol de estructura no tendría un tamaño fijo.

Con estas piezas en su lugar, estamos listos para definir nuestro tipo de árbol:

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

jugando con arboles

Escribamos algunas funciones para construir árboles:

// 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 imprimirlos:

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

Esto nos permite traducir la expresión de Haskell:

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

en C como:

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

Por ejemplo:

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

Como ejemplo un poco más interesante, traduzcamos esta función de búsqueda en profundidad:

-- 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 nuestro tipo de árbol:

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

Ciertamente es más detallado, pero el proceso de traducción es sencillo (hasta el punto de que un compilador presumiblemente podría hacer este tipo de cosas por nosotros...).

Compensaciones

Terminamos con una pequeña digresión sobre las compensaciones involucradas en una representación alternativa. Específicamente, supongamos en lugar de:

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

usamos:

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

En el primer caso, la unión contiene una estructura internal_data, mientras que en el segundo almacena un puntero a esta estructura. Como resultado, la primera unión es un poco más grande con 16 bytes, frente a 8 para la versión de puntero en mi máquina. Desafortunadamente, no son solo los nodos internos los que se ven afectados: los nodos hoja usan esta misma unión de 16 bytes pero solo almacenan un único int (4 bytes). Esto parece un poco derrochador.

Sin embargo, esa no es toda la historia. Pagaremos por la dirección indirecta adicional cada vez que accedamos a los hijos izquierdo y derecho de un nodo interno: las lecturas no son necesariamente baratas, especialmente si la memoria a la que se apunta no está almacenada en caché.

Sospecho que el enfoque principal presentado aquí es un mejor punto de partida en la mayoría de los casos, y que tratar de recortar algunos bytes (sin incurrir en lecturas adicionales) simplemente no vale la pena hasta que lo sea.