نوع البيانات الجبرية

في برمجة الحاسوب ، وخاصة في البرمجة الوظيفية ونظرية الأنواع ، فإن نوع البيانات الجبري ( ADT ) هو نوع بيانات مركب ، أي نوع يتكون من خلال الجمع بين أنواع أخرى.

يُعرَّف نوع البيانات الجبرية من خلال بنيتين أساسيتين: المجموع والضرب . ويُشار إليهما أحيانًا باسم أنواع "أو" و"و".

نوع المجموع هو اختيار بين عدة احتمالات. يمكن أن تتطابق قيمة نوع المجموع مع أحد المتغيرات المحددة . على سبيل المثال، يمكن أن يكون نوع يمثل حالة إشارة المرور إما صفرًا Redأو Amberصفرًا أو Greenصفرًا. يمكن أن يكون نوع الشكل إما شكلًا هندسيًا Circle(يخزن نصف القطر) أو شكلًا هندسيًا Square(يخزن العرض). تُعرف هذه المتغيرات رسميًا باسم الاتحادات الموسومة أو الاتحادات المنفصلة . لكل متغير اسم، يُسمى المُنشئ ، والذي يمكنه أيضًا حمل البيانات. تُعد الأنواع المُعدّدة شكلًا بسيطًا من أنواع المجموع حيث لا تحمل المُنشئات أي بيانات.

يجمع نوع المنتج بين أنواع مختلفة. تحتوي قيمة نوع المنتج على قيمة لكل نوع من أنواعه المكونة. على سبيل المثال، Pointقد يُعرَّف نوع ما ليحتوي على xإحداثي (عدد صحيح) وإحداثي آخر y(عدد صحيح أيضًا). من الأمثلة الرسمية لأنواع المنتجات: الصفوف والسجلات . مجموعة جميع القيم الممكنة لنوع منتج ما هي حاصل الضرب الديكارتي لمجموعات أنواعه المكونة.

تُعالج قيم أنواع البيانات الجبرية عادةً باستخدام مطابقة الأنماط . تُمكّن هذه الميزة المبرمج من التحقق من المُنشئ الذي تم إنشاء القيمة به واستخراج البيانات التي تحتويها بطريقة ملائمة وآمنة من حيث النوع.

تم تقديم أنواع البيانات الجبرية في Hope ، وهي لغة برمجة وظيفية صغيرة تم تطويرها في السبعينيات في جامعة إدنبرة . ^{[ 1 ]}

تُستخدم أنواع البيانات الجبرية لتمثيل القيم التي يمكن أن تكون من بين عدة أنواع . يرتبط كل نوع من هذه الأنواع بمعرّف يُسمى المُنشئ ، والذي يُمكن اعتباره علامةً لهذا النوع من البيانات. يستطيع كل مُنشئ استيعاب نوع مختلف من البيانات.

على سبيل المثال، بالنظر إلى المثال الثنائي Treeالموضح أعلاه، يمكن أن يحمل المُنشئ لا بيانات (على سبيل المثال، Empty)، أو قطعة واحدة من البيانات (على سبيل المثال، Leafله قيمة عدد صحيح واحدة)، أو قطع متعددة من البيانات (على سبيل المثال، Nodeله قيمة واحدة Intوقيمتين Tree).

لإجراء أي عملية على قيمة من هذا Treeالنوع الجبري من البيانات، يتم تحليلها باستخدام عملية تُسمى مطابقة الأنماط . تتضمن هذه العملية مطابقة البيانات مع سلسلة من الأنماط . تقوم الدالة الموضحة depthأعلاه بمطابقة وسيطها مع ثلاثة أنماط. عند استدعاء الدالة، تجد أول نمط يطابق وسيطها، وتُجري أي عمليات ربط للمتغيرات موجودة في النمط، ثم تُقيّم التعبير المُطابق للنمط.

لكل نمط من الأنماط المذكورة أعلاه شكلٌ يُشابه بنية قيمة مُحتملة من هذا النوع من البيانات. يُطابق النمط الأول قيم المُنشئ Empty. يُطابق النمط الثاني قيم المُنشئ Leaf. الأنماط مُتكررة، لذا تُطابق البيانات المرتبطة بهذا المُنشئ مع النمط "n". في هذه الحالة، يُمثل مُعرّف صغير نمطًا يُطابق أي قيمة، والتي تُربط بعد ذلك بمتغير يحمل نفس الاسم - في هذه الحالة، المتغير " n" مُرتبط بالقيمة العددية المُخزنة في نوع البيانات - لاستخدامها في التعبير المراد تقييمه.

إن التكرار في الأنماط في هذا المثال بسيط، ولكن قد يكون النمط التكراري الأكثر تعقيدًا شيئًا مثل:

Nodei(Nodej(Leaf4)x)(Nodeky(NodeEmptyz))

تُستخدم الأنماط المتكررة ذات الطبقات المتعددة على سبيل المثال في موازنة الأشجار الحمراء والسوداء ، والتي تتضمن حالات تتطلب النظر إلى الألوان ذات الطبقات المتعددة.

المثال أعلاه مكافئ عمليًا للرمز الزائف التالي :

تشغيل ( بيانات.المنشئ ) حالة فارغة : إرجاع 0 حالة ورقة : let n = بيانات.الحقل 1 إرجاع 1 حالة عقدة : let l = بيانات.الحقل 2 let r = بيانات.الحقل 3 إرجاع 1 + max ( عمق l ) ( عمق r )​​​​​​

يمكن إبراز مزايا أنواع البيانات الجبرية من خلال مقارنة الشفرة الزائفة المذكورة أعلاه مع ما يعادلها من مطابقة الأنماط.

أولاً، هناك أمان النوع . في مثال الشفرة الزائفة أعلاه، يلزم المبرمج توخي الحذر الشديد لتجنب الوصول إلىالحقل 2عندما يكون المُنشئ من نوع ` Leaf.`، سيواجه نظام الأنواع صعوبة في تعيين نوع ثابت بطريقة آمنة لهياكل بيانات السجلات التقليدية . مع ذلك، لا تُواجَه هذه المشاكل في مطابقة الأنماط. يعتمد نوع كل قيمة مُستخرجة على الأنواع المُعلنة بواسطة المُنشئ ذي الصلة. ويُعرف عدد القيم التي يُمكن استخراجها بناءً على المُنشئ.

ثانيًا، في مطابقة الأنماط، يُجري المُصرّف فحصًا شاملًا للتأكد من معالجة جميع الحالات. إذا كانت إحدى حالات دالة العمق المذكورة أعلاه مفقودة، فسيُصدر المُصرّف تحذيرًا. قد يبدو الفحص الشامل سهلًا للأنماط البسيطة، ولكن مع وجود العديد من الأنماط التكرارية المعقدة، سرعان ما تُصبح المهمة صعبة على الإنسان العادي (أو على المُصرّف، إذا كان عليه فحص بنيات if-else المتداخلة). وبالمثل، قد توجد أنماط لا تتطابق أبدًا (أي أنها مُغطاة بالفعل بأنماط سابقة). يمكن للمُصرّف أيضًا فحص هذه الأنماط وإصدار تحذيرات بشأنها، لأنها قد تُشير إلى خطأ في الاستدلال.

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

نوع البيانات الجبرية العامة هو نوع مجموع، قد يكون تكراريًا، لأنواع الضرب . يقوم كل مُنشئ بتمييز نوع الضرب عن غيره، أو إذا كان هناك مُنشئ واحد فقط، فإن نوع البيانات هو نوع ضرب. علاوة على ذلك، فإن أنواع معاملات المُنشئ هي عوامل نوع الضرب. يُقابل المُنشئ بدون معاملات الضرب الفارغ . إذا كان نوع البيانات تكراريًا، فإن مجموع الضرب بالكامل يُغلّف في نوع تكراري ، ويقوم كل مُنشئ أيضًا بتحويل نوع البيانات إلى النوع التكراري.

على سبيل المثال، نوع بيانات هاسكل:

data List a = Nil | Cons a ( List a )

يتم تمثيلها في نظرية الأنواع على النحو التالي: ${\displaystyle \lambda \alpha .\mu \beta .1+\alpha \times \beta }$ مع المُنشئات${\displaystyle \mathrm {nil} _{\alpha }=\mathrm {roll} \ (\mathrm {inl} \ \langle \rangle )}$و${\displaystyle \mathrm {cons} _{\alpha }\ x\ l=\mathrm {roll} \ (\mathrm {inr} \ \langle x,l\rangle )}$.

يمكن أيضًا تمثيل نوع بيانات قائمة هاسكل في نظرية الأنواع بشكل مختلف قليلاً، على النحو التالي: ${\displaystyle \mu \phi .\lambda \alpha .1+\alpha \times \phi \ \alpha }$(لاحظ كيف${\displaystyle \mu }$و${\displaystyle \lambda }$(يتم عكس البنى بالنسبة للأصل.) حددت الصيغة الأصلية دالة نوع يكون جسمها نوعًا تكراريًا. تحدد النسخة المعدلة دالة تكرارية على الأنواع. (متغير النوع${\displaystyle \phi }$يُستخدم للإشارة إلى دالة بدلاً من نوع أساسي مثل${\displaystyle \beta }$، منذ${\displaystyle \phi }$(يشبه حرف f اليوناني .) يجب تطبيق الدالة الآن أيضًا${\displaystyle \phi }$إلى نوع وسيطه${\displaystyle \alpha }$في متن النص.

لأغراض مثال القائمة، لا يختلف هذان الشكلان اختلافًا كبيرًا؛ لكن الشكل الثاني يسمح بالتعبير عن ما يُسمى بأنواع البيانات المتداخلة ، أي تلك التي يختلف فيها النوع التكراري عن النوع الأصلي من حيث المعاملات. (لمزيد من المعلومات حول أنواع البيانات المتداخلة، انظر أعمال ريتشارد بيرد ، ولامبرت ميرتنز ، وروس باترسون).

في نظرية المجموعات، يُعادل نوع المجموع اتحادًا منفصلاً ، وهي مجموعة عناصرها أزواج تتكون من علامة (مكافئة للدالة البانية) وكائن من نوع مطابق لتلك العلامة (مكافئ لوسائط الدالة البانية). ^{[ 2 ]}

تتضمن العديد من لغات البرمجة أنواع البيانات الجبرية كمفهوم أساسي، بما في ذلك:

• اتحاد منفصل
• نوع البيانات الجبرية المعممة
• الجبر الابتدائي
• نوع القسمة
• الاتحاد المصنف
• نظرية الأنواع
• نمط الزائر