Es ist nicht sofort klar, wie dieser Haskell-Typ in C ausgedrückt werden soll:

data Tree = Leaf Int | Inner Tree Tree

Im Gegensatz zu Sprachen wie Haskell und Rust fehlt in C die integrierte Unterstützung für
disjunkte Gewerkschaften. Es liefert jedoch alle Zutaten, die wir für ihre Darstellung benötigen, wenn wir bereit sind, etwas mehr zu tippen.

Das erste, was man erkennen muss, ist, dass eine disjunkte Vereinigung besteht aus:

• Eine Reihe verschiedener Varianten
• Jedem davon sind einige Daten zugeordnet.

In unserem Binärbaum-Beispiel haben wir zwei Varianten: „Blatt“ und „inner“. Die Blattvariante speichert eine einzelne Ganzzahl (ihre Daten) und die innere Variante speichert zwei Bäume (die ihre linken und rechten Kinder darstellen).

Wir können ein solches Tier in C darstellen, indem wir eine Struktur mit zwei Feldern verwenden:

1. Ein „Typ-Tag“, normalerweise eine ganze Zahl, der angibt, welche Variante dargestellt wird.
2. Ein Datenfeld, das die mit der Variante verknüpften Daten speichert.

Es ist praktisch, die verschiedenen Variantentyp-Tags mithilfe einer Aufzählung zu definieren:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

Was ist mit der Speicherung der Daten? Dies ist die Art von Problem, zu dessen Lösung Gewerkschaften existieren.

Gewerkschaften

Eine Union ist nur ein Teil des Speichers, der eine Reihe verschiedener Datentypen speichern kann. Hier ist zum Beispiel eine Union, die entweder einen 32-Bit-Int oder ein Array mit 5 Zeichen speichern kann.

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

Eine Variable vom Typ Union int_or_chars kann zu einem bestimmten Zeitpunkt entweder ein int oder ein Array mit 5 Zeichen enthalten (nur nicht beide gleichzeitig):

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;

Eine Union wie Union int_or_chars verfügt über einen Speicherblock, der groß genug ist, um das größte seiner Mitglieder aufzunehmen. Hier ist ein Schema, das zeigt, wie das funktioniert:

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

Das hilft zu erklären, warum das Drucken von quux.num zu „Müll“ führte, nachdem wir ein Array von Zeichen in quux gespeichert hatten: Es war kein Müll, sondern die Zeichenfolge „abcd“, die als Ganzzahl interpretiert wurde. (Auf meinem Computer wird quux.num im Hexadezimalformat als 64636261 gedruckt. Das Zeichen „a“ hat einen ASCII-Wert von 0x61, „b“ hat einen Wert von 0x62, „c“ ist 0x63 und „d“ ist 0x64. Das Die Reihenfolge ist umgekehrt, da mein Prozessor Little-Endian ist.)

Als letzte Anmerkung zu Gewerkschaften: Sie könnten von der Größe überrascht sein, die von sizeof:
gemeldet wird.

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

Auf meinem Computer hat die Typunion int_or_chars eine Größe von 8 Bytes, nicht 5, wie wir vielleicht erwartet hätten. Aufgrund der Ausrichtungsanforderungen, die die Architektur meines Prozessors vorgibt, wurde etwas Auffüllung hinzugefügt.

Zurück zu Binärbäumen

Wir sind jetzt bereit, mit der Übersetzung des binären Baumtyps von Haskell nach C fortzufahren. Wir haben bereits eine Aufzählung definiert, um den Typ der Variante darzustellen. Jetzt brauchen wir eine Union, um ihre Daten zu speichern:

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

wobei struct inner_data eine Struktur ist, die die linken und rechten Kinder einer „inneren“ Variante enthält:

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

Beachten Sie, dass die „innere“ Variante Zeiger auf ihre linken und rechten untergeordneten Elemente beibehält. Die Indirektion ist notwendig, da der Strukturbaum sonst keine feste Größe hätte.

Sobald diese Teile vorhanden sind, können wir unseren Baumtyp definieren:

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

Mit Bäumen spielen

Lassen Sie uns einige Funktionen schreiben, um Bäume zu erstellen:

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

und drucken Sie sie aus:

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

Damit können wir den Haskell-Ausdruck übersetzen:

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

in C als:

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

Zum Beispiel:

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

Als etwas interessanteres Beispiel übersetzen wir diese Tiefensuchfunktion:

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

Verwendung unseres Baumtyps:

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

Es ist sicherlich ausführlicher, aber der Übersetzungsprozess ist unkompliziert (so weit, dass ein Compiler vermutlich so etwas für uns erledigen könnte ...).

Kompromisse

Wir schließen mit einem kleinen Exkurs über die Kompromisse, die eine alternative Darstellung mit sich bringt. Angenommen, anstelle von:

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

wir haben verwendet:

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

Im ersten Fall enthält die Union eine Struktur inner_data, während sie im zweiten Fall einen Zeiger auf diese Struktur speichert. Dadurch ist die erste Union mit 16 Bytes etwas größer, im Vergleich zu 8 Bytes bei der Zeigerversion auf meinem Rechner. Leider sind nicht nur innere Knoten betroffen: Blattknoten verwenden dieselbe 16-Byte-Vereinigung, speichern aber nur einen einzelnen (4-Byte-)Int. Das fühlt sich etwas verschwenderisch an.

Das ist jedoch nicht die ganze Geschichte. Wir zahlen für die zusätzliche Indirektion jedes Mal, wenn wir auf die linken und rechten Kinder eines inneren Knotens zugreifen: Lesevorgänge sind nicht unbedingt billig, insbesondere wenn der Speicher, auf den verwiesen wird, nicht zwischengespeichert ist.

Ich vermute, dass der hier vorgestellte Hauptansatz in den meisten Fällen ein besserer Ausgangspunkt ist und dass sich der Versuch, ein paar Bytes zu sparen (weiß, was zusätzliche Lesevorgänge verursacht), einfach nicht lohnt, bis es soweit ist.