ليس من الواضح على الفور كيفية التعبير عن نوع هاسكل هذا في لغة C:

data Tree = Leaf Int | Inner Tree Tree

بخلاف لغات مثل Haskell وRust، تفتقر لغة C إلى الدعم المدمج لـ
نقابات مفككة. ومع ذلك، فهو يوفر جميع المكونات التي نحتاجها لتمثيلهم، إذا كنا على استعداد للقيام ببعض الكتابة الإضافية.

أول شيء يجب إدراكه هو أن الاتحاد المفكك يتكون من:

• عدد من المتغيرات المختلفة
• كل منها لديه بعض البيانات المرتبطة به.

في مثال الشجرة الثنائية لدينا، لدينا متغيران: "leaf" و"inner". يخزن متغير الورقة عددًا صحيحًا واحدًا (بياناته)، ويخزن المتغير الداخلي شجرتين (تمثلان فرعيه الأيسر والأيمن).

يمكننا تمثيل مثل هذا الحيوان في لغة C باستخدام بنية تحتوي على حقلين:

1. "علامة النوع"، عادةً ما تكون عددًا صحيحًا، تشير إلى المتغير الذي يتم تمثيله.
2. حقل بيانات الذي يقوم بتخزين البيانات المرتبطة بالمتغير.

من الملائم تحديد علامات الأنواع المختلفة باستخدام التعداد:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

ماذا عن تخزين البيانات؟ هذا هو نوع المشكلة التي توجد النقابات لحلها.

النقابات

الاتحاد هو مجرد جزء من الذاكرة قادر على تخزين عدد من أنواع البيانات المختلفة. على سبيل المثال، هذا اتحاد يمكنه تخزين عدد صحيح 32 بت أو مصفوفة مكونة من 5 أحرف.

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

يمكن للمتغير الذي نوعه union 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;

لدى اتحاد مثل union int_or_chars تحت تصرفه قطعة كبيرة من الذاكرة كبيرة بما يكفي لاستيعاب أكبر عدد من أعضائها. فيما يلي رسم تخطيطي يوضح كيفية عمل ذلك:

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

مما يساعد في تفسير سبب ظهور طباعة quux.num في "قمامة" بعد أن قمنا بتخزين مجموعة من الأحرف في quux: لم تكن قمامة، بل كانت السلسلة "abcd" يتم تفسيرها على أنها عدد صحيح. (على جهازي، تتم طباعة quux.num بالصيغة الست عشرية كـ 64636261. الحرف "a" له قيمة ASCII تبلغ 0x61، و"b" له قيمة 0x62، و"c" هو 0x63، و"d" هو 0x64. تم عكس الترتيب نظرًا لأن المعالج الخاص بي صغير الحجم.)

كملاحظة أخيرة بشأن النقابات، قد تتفاجأ بالحجم المذكور حسب sizeof:

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

على جهازي، يبلغ حجم نوع union int_or_chars 8 بايت، وليس 5 كما توقعنا. تمت إضافة بعض المساحة المتروكة بسبب متطلبات المحاذاة المنصوص عليها في بنية المعالج الخاص بي.

العودة إلى الأشجار الثنائية

نحن الآن جاهزون لمواصلة ترجمة نوع الشجرة الثنائية من Haskell إلى C. لقد قمنا بالفعل بتعريف التعداد لتمثيل نوع المتغير. الآن نحتاج إلى اتحاد لتخزين بياناته:

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

حيث البنية الداخلية هي بنية تحتوي على العناصر الفرعية اليمنى واليسرى للمتغير "الداخلي":

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

لاحظ أن المتغير "الداخلي" يحتفظ بمؤشرات على أطفاله الأيسر والأيمن. يعد الاتجاه غير المباشر ضروريًا لأنه بخلاف ذلك لن يكون لشجرة البنية حجم ثابت.

مع وضع هذه القطع في مكانها، نحن جاهزون لتحديد نوع شجرتنا:

نوع الشجرة التعدادية { شجرة_ورقة، TREE_INNER، }; شجرة الهيكل هيكل البيانات الداخلية { شجرة الهيكل * يسار؛ شجرة الهيكل *يمين؛ }; بيانات شجرة الاتحاد { ورقة كثافة العمليات. هيكل البيانات الداخلية الداخلية؛ }; // تمثيل شجرة ثنائية. شجرة البناء { نوع شجرة التعداد؛ بيانات شجرة الاتحاد؛ };

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

اللعب بالأشجار

دعونا نكتب بعض الوظائف لبناء الأشجار:

// إنشاء عقدة ورقية. شجرة الهيكل * ورقة (قيمة كثافة العمليات) { شجرة البنية *t = malloc(sizeof(*t)); t->type = TREE_LEAF; t->data.leaf = value; العودة ر؛ } // إنشاء عقدة داخلية. شجرة الهيكل * الداخلية (شجرة الهيكل * يسار، شجرة هيكل * يمين) { شجرة البنية *t = malloc(sizeof(*t)); t->type = TREE_INNER; t->data.inner.left = left; t->data.inner.right = 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;
};

وطباعتها:

void print_tree(struct Tree *t) { التبديل (t->نوع) { الحالة TREE_LEAF: printf("%d", t->data.leaf); يعود؛ الحالة TREE_INNER: برينتف("("); print_tree(t->data.inner.left); برينتف(""); print_tree(t->data.inner.right); printf(")"); يعود؛ } }

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

يسمح لنا هذا بترجمة تعبير هاسكل:

الداخلية (الداخلية (الورقة 1) (الورقة 2)) (الورقة 3)

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

إلى C كـ:

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

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

على سبيل المثال:

شجرة الهيكل *t = الداخلية(inner(leaf(1), leaf(2))), leaf(3)); print_tree(t); // => ((1 2) 3)

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

كمثال أكثر إثارة للاهتمام، دعونا نترجم وظيفة البحث ذات العمق الأول:

-- تحقق مما إذا كانت القيمة موجودة في شجرة. بحث :: Int -> شجرة -> منطقي بحث v (ورقة w) = v == w بحث v (داخلي l r) = بحث v l || بحث ضد ص

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

استخدام نوع الشجرة لدينا:

// التحقق من وجود قيمة في شجرة. بحث int(قيمة int، شجرة البنية *t) { التبديل (t->نوع) { الحالة TREE_LEAF: إرجاع t->data.leaf == value; الحالة TREE_INNER: يعود ( بحث (القيمة، t->data.inner.left) || البحث (القيمة، t->data.inner.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;
};

إنها بالتأكيد أكثر تفصيلاً، لكن عملية الترجمة واضحة ومباشرة (إلى الحد الذي يمكن للمترجم أن يفعل هذا النوع من الأشياء لنا...).

المقايضات

ننتهي بالقليل من الاستطراد حول المقايضات التي ينطوي عليها التمثيل البديل. على وجه التحديد، لنفترض بدلاً من:

بيانات شجرة الاتحاد { ورقة كثافة العمليات. هيكل البيانات الداخلية الداخلية؛ };

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

استخدمنا:

بيانات شجرة الاتحاد { ورقة كثافة العمليات. البنية الداخلية_البيانات * الداخلية؛ // ^ الفرق. };

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

في الحالة الأولى، يحتوي الاتحاد على بيانات داخلية للبنية، بينما في الحالة الثانية يقوم بتخزين

مؤشر لهذه البنية. ونتيجة لذلك، فإن الاتحاد الأول أكبر قليلاً حيث يبلغ 16 بايت، مقابل 8 بايت لإصدار المؤشر على جهازي. لسوء الحظ، لا تتأثر العقد الداخلية فقط: تستخدم العقد الورقية نفس الاتحاد المكون من 16 بايت ولكنها تخزن فقط عدد صحيح واحد (4 بايت). يبدو هذا إسرافًا بعض الشيء.

ومع ذلك، هذه ليست القصة بأكملها. سندفع مقابل عدم التوجيه الإضافي في كل مرة نصل فيها إلى العناصر الفرعية اليمنى واليسرى للعقدة الداخلية: القراءات ليست بالضرورة رخيصة، خاصة إذا لم يتم تخزين الذاكرة المشار إليها مؤقتًا.

أعتقد أن النهج الرئيسي المقدم هنا هو نقطة بداية أفضل في معظم الحالات، وأن محاولة تقليل عدد قليل من البايتات (اللون الأبيض يؤدي إلى قراءات إضافية) لا يستحق كل هذا العناء حتى يصبح كذلك.