On ne sait pas immédiatement comment exprimer ce type Haskell en C :

data Tree = Leaf Int | Inner Tree Tree

Contrairement à des langages comme Haskell et Rust, C ne dispose pas d'un support intégré pour
syndicats disjoints. Cependant, il fournit tous les ingrédients dont nous avons besoin pour les représenter, si nous sommes prêts à taper un peu plus.

La première chose à comprendre est qu'une union disjointe consiste en :

• Un certain nombre de variantes différentes
• Chacun d'entre eux est associé à des données.

Dans notre exemple d'arbre binaire, nous avons deux variantes : "leaf" et "inner". La variante feuille stocke un seul entier (ses données) et la variante interne stocke deux arbres (représentant ses enfants gauche et droit).

Nous pouvons représenter un tel animal en C en utilisant une structure à deux champs :

1. Une "balise de type", généralement un nombre entier, indiquant quelle variante est représentée.
2. Un champ data qui stocke les données associées à la variante.

Il est pratique de définir les différentes balises de type variant à l'aide d'une énumération :

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

Qu'en est-il du stockage des données ? C’est le type de problème que les syndicats existent pour résoudre.

Les syndicats

Une union n'est qu'un morceau de mémoire capable de stocker un certain nombre de types de données différents. Par exemple, voici une union qui peut stocker soit un entier 32 bits, soit un tableau de 5 caractères.

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

Une variable dont le type est union int_or_chars peut contenir soit un int, soit un tableau de 5 caractères à un moment donné (mais pas les deux en même temps) :

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;

Une union comme union int_or_chars a à sa disposition une quantité de mémoire suffisamment grande pour contenir le plus grand de ses membres. Voici un schéma montrant comment cela fonctionne :

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

Ce qui aide à expliquer pourquoi l'impression de quux.num a entraîné une "poubelle" après avoir stocké un tableau de caractères dans quux : ce n'était pas une poubelle, c'était la chaîne "abcd" interprétée comme un entier. (Sur ma machine, quux.num est imprimé en hexadécimal sous la forme 64636261. Le caractère « a » a une valeur ASCII de 0x61, « b » a une valeur de 0x62, « c » est 0x63 et « d » est 0x64. Le l'ordre est inversé puisque mon processeur est petit-boutiste.)

Pour conclure sur les syndicats, vous pourriez être surpris par la taille indiquée par sizeof :

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

Sur ma machine, le type union int_or_chars a une taille de 8 octets, et non de 5 comme on aurait pu s'y attendre. Un peu de remplissage a été ajouté en raison des exigences d'alignement stipulées par l'architecture de mon processeur.

Retour aux arbres binaires

Nous sommes maintenant prêts à continuer la traduction du type d'arbre binaire de Haskell vers C. Nous avons déjà défini une énumération pour représenter le type de la variante. Nous avons maintenant besoin d'un syndicat pour stocker ses données :

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

où struct inner_data est une structure contenant les enfants gauche et droit d'une variante "interne":

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

Remarquez que la variante "intérieure" conserve des pointeurs vers ses enfants gauche et droit. L'indirection est nécessaire car sinon l'arbre de structure n'aurait pas de taille fixe.

Une fois ces éléments en place, nous sommes prêts à définir notre type d'arbre :

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

Jouer avec les arbres

Écrivons quelques fonctions pour construire des arbres :

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

et imprimez-les :

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

Cela nous permet de traduire l'expression Haskell :

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

en C comme :

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

Par exemple:

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

À titre d'exemple légèrement plus intéressant, traduisons cette fonction de recherche en profondeur :

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

Utilisation de notre type d'arbre :

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

C'est certainement plus verbeux, mais le processus de traduction est simple (dans la mesure où un compilateur pourrait vraisemblablement faire ce genre de chose pour nous...).

Compromis

Nous terminons par une petite digression sur les compromis impliqués dans une représentation alternative. Plus précisément, supposons au lieu de :

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

nous avons utilisé :

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

Dans le premier cas, l'union contient une structure inner_data, alors que dans le second elle stocke un pointeur vers cette structure. En conséquence, la première union est un peu plus grande à 16 octets, contre 8 pour la version pointeur sur ma machine. Malheureusement, ce ne sont pas seulement les nœuds internes qui sont affectés : les nœuds feuilles utilisent cette même union de 16 octets mais ne stockent qu'un seul int (4 octets). Cela semble un peu inutile.

Cependant, ce n'est pas toute l'histoire. Nous allons payer pour l'indirection supplémentaire chaque fois que nous accédons aux enfants gauche et droit d'un nœud interne : les lectures ne sont pas nécessairement bon marché, surtout si la mémoire pointée n'est pas mise en cache.

Je soupçonne que l'approche principale présentée ici est un meilleur point de départ dans la plupart des cas, et qu'essayer de raser quelques octets (le blanc entraînant des lectures supplémentaires) n'en vaut tout simplement pas la peine jusqu'à ce que ce soit le cas.