यह तुरंत स्पष्ट नहीं है कि इस हास्केल प्रकार को C में कैसे व्यक्त किया जाए:

data Tree = Leaf Int | Inner Tree Tree

हास्केल और रस्ट जैसी भाषाओं के विपरीत, सी में अंतर्निहित समर्थन का अभाव है
विघटित संघ। हालाँकि, यदि हम थोड़ी अतिरिक्त टाइपिंग करने के इच्छुक हैं, तो यह उन्हें प्रस्तुत करने के लिए आवश्यक सभी सामग्रियां प्रदान करता है।

पहली बात जो समझने वाली है वह यह है कि एक असंयुक्त संघ में शामिल हैं:

• कई अलग-अलग वेरिएंट
• जिनमें से प्रत्येक के साथ कुछ डेटा जुड़ा हुआ है।

हमारे बाइनरी ट्री उदाहरण में, हमारे पास दो प्रकार हैं: "पत्ती" और "आंतरिक"। पत्ती संस्करण एक पूर्णांक (इसका डेटा) संग्रहीत करता है, और आंतरिक संस्करण दो पेड़ों को संग्रहीत करता है (इसके बाएं और दाएं बच्चों का प्रतिनिधित्व करता है)।

हम दो क्षेत्रों के साथ एक संरचना का उपयोग करके सी में ऐसे जानवर का प्रतिनिधित्व कर सकते हैं:

1. एक "प्रकार टैग", आम तौर पर एक पूर्णांक, जो दर्शाता है कि किस प्रकार का प्रतिनिधित्व किया जा रहा है।
2. एक डेटा फ़ील्ड जो वैरिएंट से जुड़े डेटा को संग्रहीत करता है।

एनम का उपयोग करके विभिन्न प्रकार के टैग को परिभाषित करना सुविधाजनक है:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

डेटा संग्रहीत करने के बारे में क्या? यह उस प्रकार की समस्या है जिसे हल करने के लिए यूनियन्स मौजूद हैं।

यूनियन

एक यूनियन मेमोरी का एक हिस्सा मात्र है जो कई प्रकार के डेटा को संग्रहीत करने में सक्षम है। उदाहरण के लिए, यहां एक यूनियन है जो 32-बिट इंट या 5 वर्णों की एक सरणी संग्रहीत कर सकता है।

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

एक वेरिएबल जिसका प्रकार यूनियन int_or_chars है, किसी विशेष समय में या तो एक int या 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 में वर्णों की एक श्रृंखला संग्रहीत करने के बाद quux.num को प्रिंट करने पर "कचरा" क्यों निकला: यह कचरा नहीं था, यह स्ट्रिंग "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 नहीं जैसा कि हमने उम्मीद की थी। मेरे प्रोसेसर के आर्किटेक्चर द्वारा निर्धारित संरेखण आवश्यकताओं के कारण कुछ पैडिंग जोड़ी गई है।

बाइनरी ट्रीज़ को लौटें

अब हम हास्केल से सी तक बाइनरी ट्री प्रकार का अनुवाद जारी रखने के लिए तैयार हैं। हमने वेरिएंट के प्रकार का प्रतिनिधित्व करने के लिए पहले से ही एक एनम को परिभाषित किया है। अब हमें अपना डेटा संग्रहीत करने के लिए एक संघ की आवश्यकता है:

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

जहां स्ट्रक्चर इनर_डेटा एक संरचना है जिसमें "आंतरिक" संस्करण के बाएं और दाएं बच्चे शामिल हैं:

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

यह हमें हास्केल अभिव्यक्ति का अनुवाद करने की अनुमति देता है:

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

सी में इस प्रकार:

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

पहले मामले में, यूनियन में एक स्ट्रक्चर इनर_डेटा होता है, जबकि दूसरे में यह इस स्ट्रक्चर में एक पॉइंटर स्टोर करता है। परिणामस्वरूप, पहला यूनियन 16 बाइट्स पर थोड़ा बड़ा है, जबकि मेरी मशीन पर पॉइंटर संस्करण के लिए 8 है। दुर्भाग्य से यह केवल आंतरिक नोड्स ही प्रभावित नहीं हैं: लीफ नोड्स इसी 16-बाइट यूनियन का उपयोग करते हैं लेकिन केवल एक (4-बाइट) इंट को संग्रहीत करते हैं। यह थोड़ा बेकार लगता है।

हालाँकि, यह पूरी कहानी नहीं है। जब भी हम किसी आंतरिक नोड के बाएँ और दाएँ बच्चों तक पहुँचते हैं तो हम अतिरिक्त संकेत के लिए भुगतान करने जा रहे हैं: पढ़ना आवश्यक रूप से सस्ता नहीं है, खासकर यदि इंगित की गई मेमोरी कैश्ड नहीं है।

मुझे संदेह है कि यहां प्रस्तुत मुख्य दृष्टिकोण ज्यादातर मामलों में एक बेहतर शुरुआती बिंदु है, और कुछ बाइट्स (अतिरिक्त पढ़ने के लिए सफेद) को शेव करने की कोशिश करना इसके लायक नहीं है जब तक कि यह न हो जाए।