أنواع البيانات الجبرية لهاسكل

Question

أحاول أن أفهم تمامًا جميع مفاهيم هاسكل.

ما هي الطرق التي تشبه بها أنواع البيانات الجبرية الأنواع العامة، على سبيل المثال، في C# وJava؟وكيف هم مختلفون؟ما هو الجبري عنهم على أي حال؟

أنا على دراية بالجبر الشامل وحلقاته وحقوله، ولكن ليس لدي سوى فكرة غامضة عن كيفية عمل أنواع هاسكل.

Answer 1

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

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

يعادل (قدر الإمكان، وتجاهل التقييم غير الصارم، وما إلى ذلك) ل

 class List<a> {
     class Cons : List<a> {
         a head;
         List<a> tail;
     }
     class Nil : List<a> {}
 }

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

[يحرر:شكرًا لكريس كونواي على الإشارة إلى خطأي الأحمق، ADT هي بالطبع أنواع مجموعية، فالمنشئون يقدمون المنتج/مجموعة الحقول]

Answer 2

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

• + يمثل أنواع المجموع (الاتحادات المنفصلة، ​​على سبيل المثال. Either).
• • يمثل أنواع المنتجات (على سبيل المثال.الهياكل أو الصفوف)
• X للنوع المفرد (على سبيل المثال. data X a = X a)
• 1 لنوع الوحدة ()
• و μ لأقل نقطة ثابتة (على سبيل المثال.أنواع العودية)، وعادة ما تكون ضمنية.

مع بعض التدوين الإضافي:

• X² ل X•X

في الواقع، قد تقول (متبعًا برنت يورجي) إن نوع بيانات هاسكل يكون منتظمًا إذا كان من الممكن التعبير عنه بدلالة 1, X, +, •, ، والنقطة الأقل ثباتًا.

باستخدام هذا الترميز، يمكننا أن نصف بإيجاز العديد من هياكل البيانات العادية:

• الوحدات: data () = ()

  1

• خيارات: data Maybe a = Nothing | Just a

  1 + X

• القوائم: data [a] = [] | a : [a]

  L = 1+X•L

• الأشجار الثنائية: data BTree a = Empty | Node a (BTree a) (BTree a)

  B = 1 + X•B²

هناك عمليات أخرى (مأخوذة من ورقة برنت يورجي، المدرجة في المراجع):

• توسع:يمكن أن يكون الكشف عن نقطة الإصلاح مفيدًا للتفكير في القوائم. L = 1 + X + X² + X³ + ... (أي أن القوائم إما أن تكون فارغة، أو تحتوي على عنصر واحد، أو عنصرين، أو ثلاثة، أو ...)

• تعبير، ◦, ، أنواع معينة F و G, ، التكوين F ◦ G هو النوع الذي يبني "هياكل F مصنوعة من هياكل G" (على سبيل المثال. R = X • (L ◦ R) ،أين L هي قوائم، هي شجرة ورد.

• التمايز، مشتق نوع البيانات D (يُعطى كـ D') هو نوع الهياكل D ذات "ثقب" واحد، أي موقع مميز لا يحتوي على أي بيانات.وهذا يفي بشكل مثير للدهشة بنفس القواعد المتبعة في التفاضل في حساب التفاضل والتكامل:

  1′ = 0

  X′ = 1

  (F + G)′ = F' + G′

  (F • G)′ = F • G′ + F′ • G

  (F ◦ G)′ = (F′ ◦ G) • G′

---

مراجع:

• الأنواع والوظائف والأنواع, يا إلهي! برنت أ.يورجي، هاسكل 10، 30 سبتمبر 2010، بالتيمور، ميريلاند، الولايات المتحدة الأمريكية
• المهرجون على يساري، والمهرجون على اليمين (تشريح هياكل البيانات), ، كونور ماكبرايد بوبل 2008

Answer 3

في الجبر العالمي ان الجبر يتكون من بعض مجموعات العناصر (فكر في كل مجموعة كمجموعة من القيم من النوع) وبعض العمليات ، والتي تعرض عناصر العناصر.

على سبيل المثال ، افترض أن لديك نوعًا من "عناصر القائمة" ونوع "القوائم".كعمليات ، لديك "القائمة الفارغة" ، وهي دالة 0-argument التي تُرجع "قائمة" ، و "دالة" سلبيات تأخذ وسيطتين ، و "عنصر قائمة" و "قائمة" ، وإنتاج "قائمة ".

في هذه المرحلة ، هناك العديد من الجبر الذي يتناسب مع الوصف ، حيث قد يحدث شيئان غير مرغوب فيهما:

• يمكن أن تكون هناك عناصر في مجموعة "القائمة" التي لا يمكن بناؤها من "القائمة الفارغة" و "عملية السلبيات" ، ما يسمى "Junk".يمكن أن يكون هذا قوائم تبدأ من عنصر ما سقط من السماء ، أو حلقات دون بداية ، أو قوائم لا حصر لها.

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

يسمى الجبر الذي لا يحتوي على أي من هذه الخصائص غير المرغوب فيهاأولي, وهذا هو المعنى المقصود لنوع البيانات المجردة.

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

يصبح الأمر أكثر تعقيدًا بالنسبة للأنواع متعددة الأشكال ...

Answer 4

سبب بسيط وراء تسميتها بالجبرية؛هناك كلا النوعين المجموع (الانفصال المنطقي) والمنتج (الاقتران المنطقي).نوع المجموع هو اتحاد تمييزي، على سبيل المثال:

data Bool = False | True

نوع المنتج هو نوع يحتوي على معلمات متعددة:

data Pair a b = Pair a b

في O'Caml، أصبح "المنتج" أكثر وضوحًا:

type 'a 'b pair = Pair of 'a * 'b

Answer 5

تسمى أنواع بيانات هاسكل "جبرية" بسبب ارتباطها بـ الجبر الأولي القاطع.ولكن بهذه الطريقة يكمن الجنون.

@olliej:ADTs هي في الواقع أنواع "مجموع".Tuples هي منتجات.

Answer 6

@تيمبو:

أنت على حق في كونها نوعًا ما مثل فئة Tree مجردة مع ثلاث فئات مشتقة (Empty، Leaf، وNode)، ولكنك ستحتاج أيضًا إلى فرض ضمان بأن شخصًا ما يستخدم فئة Tree الخاصة بك لا يمكنه أبدًا إضافة أي فئات مشتقة جديدة ، نظرًا لأن إستراتيجية استخدام نوع بيانات الشجرة هي كتابة تعليمات برمجية يتم تبديلها في وقت التشغيل بناءً على نوع كل عنصر في الشجرة (وإضافة أنواع مشتقة جديدة ستؤدي إلى كسر التعليمات البرمجية الموجودة).يمكنك أن تتخيل أن هذا الأمر يصبح سيئًا في C# أو C++، ولكن في Haskell وML وOCaml، يعد هذا أمرًا أساسيًا لتصميم اللغة وبناء الجملة، لذا يدعمها أسلوب البرمجة بطريقة أكثر ملاءمة، عبر مطابقة الأنماط.

ADT (أنواع المجموع) تشبه أيضًا نوعًا ما النقابات الموسومة أو أنواع مختلفة في C أو C++.

Answer 7

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

Answer 8

بالنسبة لي، كان مفهوم أنواع البيانات الجبرية في هاسكل يبدو دائمًا مثل تعدد الأشكال في لغات OO مثل C#.

انظر إلى المثال من http://en.wikipedia.org/wiki/Algebraic_data_types:

data Tree = Empty 
          | Leaf Int 
          | Node Tree Tree

يمكن تنفيذ ذلك في C# كفئة أساسية TreeNode، مع فئة Leaf مشتقة وفئة TreeNodeWithChildren مشتقة، وإذا كنت تريد حتى فئة EmptyNode مشتقة.

(حسنًا، أعلم أنه لن يقوم أحد بذلك على الإطلاق، ولكن على الأقل يمكنك القيام بذلك.)