كيف يمكن للمرء أن يعلن عن نوع حاوية بيانات مجردة في هاسكل؟

Question

قرأت وليام كوك "على تجريد البيانات ، إعادة النظر" ، وإعادة قراءة "تعبير Lemma" من Ralf Laemmel لمحاولة فهم كيفية تطبيق أفكار الورقة السابقة في Haskell. لذا ، أحاول أن أفهم كيف يمكنك التنفيذ ، على سبيل المثال ، وظيفة نقابة محددة ، في هاسكل دون تحديد الأنواع؟

Answer 1

هناك طرق متعددة ، اعتمادًا على إصدار "أنواع البيانات المجردة" التي تتبعها.

• أنواع ملموسة ولكن غير شفافة: لقد مر بعض الوقت منذ أن قرأت ورقة كوك الجميلة ، لكنني ألقي نظرة خاطفة على ذلك ، أعتقد أن هذا الأقرب إلى ما يتحدث عنه كـ ADTS. الطريقة القياسية للقيام بذلك في Haskell هي تصدير نوع بدون منشئاته ؛ ماذا يعني هذا في هاسكل:

  • لا يوجد نمط مطابق على قيم النوع المستخلص

  • لا توجد قيم بناء من النوع ، باستثناء استخدام الوظائف التي تم تصديرها من الوحدة النمطية

  كيف يرتبط هذا بورق كوك:

  • استقلال التمثيل: من الخارج ، لا يمكن الوصول إلى التمثيل.

  • فحص تمثيلات متعددة: داخل وحدة ADT ، يمكن فحص التمثيل بحرية.

  • تطبيقات/وحدات فريدة: يمكن توفير تطبيقات مختلفة بواسطة وحدات مختلفة ، ولكن لا يمكن أن تتداخل الأنواع إلا بالوسائل العادية. لا يمكنك استخدام Data.IntMap.null لمعرفة ما إذا كان أ Data.Map.Map Int a فارغ.

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

  import qualified Data.Set as S
  

  على الرغم من أن هذا ربما لا يكون وسيلة قوية للتجريد كما يمكن أن يكون بلغة ذات نظام وحدة تعبير أكثر.

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

  foo :: (a, a -> Bool) -> Bool
  

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

  data FooADT = forall a. FooADT a (a -> Bool)
  
  foo :: FooADT -> Bool
  

  الآن ، في أي وقت لدينا قيمة من النوع FooADT, ، كل ما نعرفه هو ذلك هناك بعض الانواع a بحيث يمكننا التقديم FooADTحجة ثانية إلى الأولى.

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

  الآن ، ماذا يعني هذا من حيث ورقة كوك؟

  • استقلال التمثيل لا يزال ينطبق.

  • العزلة الكلية: على عكس ما قبل ، يتم فقدان المعرفة بالنوع الكمي الوجودي إلى الأبد. لا شيء يمكن أن يفقد التمثيل باستثناء الواجهة التي يوفرها نفسها.

  • التطبيقات التعسفية: ليس فقط التطبيقات ليست بالضرورة فريدة من نوعها ، فلا توجد طريقة للحد منها على الإطلاق! أي شيء يمكن أن يوفر الواجهة نفسها يمكن أن يختتم داخل وجودي ويكون لا يمكن تمييزه عن القيم الأخرى.

  باختصار ، يشبه هذا وصف كوك للكائنات. لمعرفة المزيد عن ADTs الوجودية ، الورقة تتكشف أنواع البيانات التجريدية ليس مكانًا سيئًا للبدء ؛ لكن ضع في اعتبارك أن ما يناقشه هو في الأساس ليس ما يطلق عليه Cook ADT.

---

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

Answer 2

يمكنك إما أن تتطلب تقديم وظيفة مقارنة أو تتطلب أن تكون الأنواع مثيلات Eq. نرى nub و nubBy للحصول على أمثلة على هذه التقنية:

nub :: (Eq a) => [a] -> [a]
nubBy :: (a -> a -> Bool) -> [a] -> [a]