الجبر الابتدائي

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

وبالمثل ، فإن الجبر المشترك النهائي هو كائن نهائي في فئة الجبر المشترك F. وتوفر هذه النهائية إطارًا عامًا للاستقراء المشترك والتكرار المشترك .

على سبيل المثال، باستخدام نفس الدالة 1 + (−) كما في السابق، تُعرَّف الجبر المشترك على أنه مجموعة X مع دالة f  : X → (1 + X ) . تعريف هذه الدالة يُعادل تعريف دالة جزئية f' : X ⇸ X التي يتكون مجالها من تلك${\displaystyle x\in X}$حيث لا تنتمي f ( x ) إلى 1. بوجود مثل هذا الهيكل، يمكننا تعريف سلسلة من المجموعات: X₀ وهي مجموعة جزئية من _X لا تُعرَّف عليها f ′ _{، و} X₁ التي تُسقط عناصرها على X₀ بواسطة f ′ ، وX₂ _التي تُسقط عناصرها على _X₁ بواسطة f ′ ، وهكذا، و Xω التي تحتوي على العناصر المتبقية من X. بناءً على ذلك ، _فإن المجموعة${\displaystyle \mathbf {N} \cup \{\أوميغا \}}$، التي تتكون من مجموعة الأعداد الطبيعية الموسعة بعنصر جديد ω ، هي حاملة الجبر المشترك النهائي، حيث${\displaystyle f'}$هي دالة السلف (معكوس دالة الخلف) على الأعداد الطبيعية الموجبة، ولكنها تعمل كدالة محايدة على العنصر الجديد ω : f ( n + 1) = n ، f ( ω ) = ω . هذه المجموعة${\displaystyle \mathbf {N} \cup \{\أوميغا \}}$يُعرف حامل الجبر المشترك النهائي لـ 1 + (−) باسم مجموعة الأعداد الطبيعية المشتركة.

كمثال ثانٍ، لننظر إلى نفس الدالة 1 + N × (−) كما في السابق. في هذه الحالة، يتكون حامل الجبر المشترك النهائي من جميع قوائم الأعداد الطبيعية، سواء كانت منتهية أو غير منتهية . العمليات هي دالة اختبار تتحقق مما إذا كانت القائمة فارغة، ودالة تفكيك معرفة على القوائم غير الفارغة تُرجع زوجًا يتكون من رأس وذيل قائمة الإدخال.

• الجبر الأولي يكون بسيطًا (أي أنه لا يحتوي على جبر فرعي مناسب).
• الجبر المشترك النهائي بسيط (أي ليس له نواتج قسمة صحيحة).

يمكن الحصول على العديد من هياكل البيانات المحدودة المستخدمة في البرمجة ، مثل القوائم والأشجار ، كجبر ابتدائي لوظائف داخلية محددة. ورغم وجود عدة جبر ابتدائي لوظيفة داخلية معينة، إلا أنها فريدة حتى التماثل ، مما يعني ببساطة أن الخصائص " القابلة للملاحظة" لهيكل البيانات يمكن تمثيلها بدقة من خلال تعريفها كجبر ابتدائي.

للحصول على نوع List( A ) من القوائم التي تكون عناصرها أعضاء في المجموعة A ، ضع في اعتبارك أن عمليات تكوين القوائم هي:

• ${\displaystyle \mathrm {nil} \colon 1\to \mathrm {List} (A)}$
• ${\displaystyle \mathrm {cons} \colon A\times \mathrm {List} (A)\to \mathrm {List} (A)}$

وعند دمجها في دالة واحدة، فإنها تعطي:

• ${\displaystyle [\mathrm {nil} ,\mathrm {cons} ]\colon (1+A\times \mathrm {List} (A))\to \mathrm {List} (A)،}$

وهذا ما يجعل هذا جبرًا من النوع F للدالة الداخلية F التي تُرسل X إلى 1 + ( A × X ) . وهو في الواقع جبر F الابتدائي . وتُحدد الابتدائيية بواسطة الدالة المعروفة باسم foldr في لغات البرمجة الوظيفية مثل Haskell و ML .

وبالمثل، يمكن الحصول على الأشجار الثنائية التي تحتوي على عناصر في الأوراق كجبر أولي

• ${\displaystyle [\mathrm {tip} ,\mathrm {join} ]\colon A+(\mathrm {Tree} (A)\times \mathrm {Tree} (A))\to \mathrm {Tree} (A).}$

تُعرف الأنواع التي يتم الحصول عليها بهذه الطريقة باسم أنواع البيانات الجبرية .

يمكن اعتبار الأنواع المعرفة باستخدام بنية النقطة الثابتة الصغرى مع الدالة F بمثابة جبر F أولي ، بشرط أن تتحقق خاصية المعلمات للنوع. ^{[ 1 ]}

توجد علاقة مماثلة، من جانبين، بين مفهومي النقطة الثابتة العظمى والجبر المشترك النهائي F ، مع تطبيقات على الأنواع الاستقرائية المشتركة . يمكن استخدام هذه الأنواع للسماح بوجود كائنات لا نهائية محتملة مع الحفاظ على خاصية التطبيع القوي . ^{[ 1 ]} في لغة برمجة Charity ذات التطبيع القوي (حيث ينتهي كل برنامج)، يمكن استخدام أنواع البيانات الاستقرائية المشتركة لتحقيق نتائج مذهلة، مثل تعريف بنيات البحث لتنفيذ دوال "قوية" كدالة أكرمان . ^{[ 2 ]}

• نوع البيانات الجبرية
• التحول الكارثي
• التشوه البصري

• البرمجة الفئوية مع الأنواع الاستقرائية والاستقرائية المشتركة بقلم فارمو فيني
• أنواع البيانات المتكررة مجاناً! بقلم فيليب وادلر، جامعة غلاسكو، 1990-2014.
• دلالات الجبر الابتدائي والجبر المشترك النهائي للتزامن، بقلم جيه جيه إم إم روتن ودي. توري
• البداية والنهاية من كليكي
• مترجمون نهائيون بدون علامات مكتوبة، بقلم أوليغ كيسليوف