يبدو أن نوع الاستدلال يكتشف حلقة لا حصر لها، ولكن ما يحدث حقا؟

Question

في أندرو كوينيج حكاية حول استنتاج النوع ML, ، يستخدم المؤلف تنفيذ دمج فرز كممارسة تعليمية لملف ML ويسر للعثور على استنتاج "غير صحيح".

الكثير لدهشتي، أبلغ المترجم عن نوع من

'a list -> int list

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

هذا مستحيل. يجب أن يكون الإخراج مبناه بالإدخال؛ كيف يمكن أن يكون لديك نوع مختلف؟ سيجد القارئ بالتأكيد أول دافع مطلع لي: تساءلت عما إذا كنت قد كشفت عن خطأ في المحول البرمجي!

بعد التفكير في الأمر أكثر من ذلك، أدركت أن هناك طريقة أخرى يمكن أن تتجاهل الوظيفة حجتها: ربما لم يعد في بعض الأحيان على الإطلاق. في الواقع، عندما جربت ذلك، هذا هو بالضبط ما حدث: sort(nil) هل عاد nil, ، ولكن فرز أي قائمة غير فارغة ستذهب إلى حلقة recursion لانهائية.

عند ترجمتها إلى Haskell

split [] = ([], [])
split [x] = ([x], [])
split (x:y:xs) = (x:s1, y:s2)
  where (s1,s2) = split xs

merge xs [] = xs
merge [] ys = ys
merge xx@(x:xs) yy@(y:ys)
  | x < y     = x : merge xs yy
  | otherwise = y : merge xx ys

mergesort [] = []
mergesort xs = merge (mergesort p) (mergesort q)
  where (p,q) = split xs

GHC اندلع نوع مماثل:

*Main> :t mergesort
mergesort :: (Ord a) => [t] -> [a]

كيف يمكن لل خوارزمية داماس هندلي ميلنر استنتاج هذا النوع؟

Answer 1

هذا هو في الواقع مثال رائع؛ حلقة لانهائية يتم الكشف عنها، أساسا، في وقت الترجمةفي لا يوجد شيء خاص حول استنتاج هندلي ميلنر في هذا المثال؛ انها مجرد عائدات كالمعتاد.

لاحظ أن GHC يحصل على أنواع split و merge بشكل صحيح:

*Main> :t split
split :: [a] -> ([a], [a])
*Main> :t merge
merge :: (Ord t) => [t] -> [t] -> [t]

الآن عندما يتعلق الأمر mergesort, ، هو، بشكل عام، وظيفة ر₁→ T.₂ لبعض أنواع ر₁ و ت₂. وبعد ثم يرى السطر الأول:

mergesort [] = []

ويدرك أن ر₁ و ت₂ يجب أن تكون أنواع قائمة، قل ر₁= [T.₃] و ت₂= [T.₄]. لذلك يجب أن تكون الاندماج وظيفة [ر₃] → [ر₄]. السطر التالي

mergesort xs = merge (mergesort p) (mergesort q) 
  where (p,q) = split xs

يروي ذلك:

• يجب أن تكون XS مدخلات للانقسام، أي من النوع [A] لبعض A (الذي هو بالفعل، ل = T₃).
• وبالتالي p و q أيضا من النوع [ر₃]، حيث split هو [A] → ([A]، [A])
• mergesort p, لذلك، (أذكر أن الاندماج يعتقد أنه من النوع [ر₃] → [ر₄]) هو من النوع [ر₄].
• mergesort q هو من النوع [ر₄] بالضبط نفس السبب.
• كما merge لديه نوع (Ord t) => [t] -> [t] -> [t], والمدخلات في التعبير merge (mergesort p) (mergesort q) كلاهما من النوع [₄]، النوع t₄ يجب أن يكون في Ord.
• أخيرا، نوع merge (mergesort p) (mergesort q) هو نفسه كل من مدخلاته، أي [ر₄]. هذا يناسب مع النوع المعروف سابقا [ر₃] → [ر₄] بالنسبة mergesort, ، لذلك لا توجد المزيد من الاستنتاجات التي يتعين القيام بها و "توحيد" جزء من خوارزمية هندلي ميلنر كاملة. mergesort هو من النوع [ر₃] → [ر₄] مع T.₄ في Ord.

لهذا السبب تحصل عليه:

*Main> :t mergesort 
mergesort :: (Ord a) => [t] -> [a]

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

Answer 2

يمكن استنتاج هذا النوع لأنه يرى أنك تمر نتيجة mergesort ل merge, ، والتي بدورها يقارن رؤساء القوائم <, ، وهو جزء من ARD Typeclass. لذلك يمكن أن يؤدي الاستدلال من النوع إلى أنه يجب عليه إرجاع قائمة مثيل ORD. بالطبع، نظرا لأنها تسير في الواقع بلا حدود، لا يمكننا استنتاج أي شيء آخر حول النوع الذي لا يعود فيه بالفعل.