لماذا أنواع البيانات الاستقرائي تمنع أنواع مثل 'البيانات سيئة أ = ج (سيئة أ - > أ)' حيث يحدث نوع العودية أمام ->?

Question

دليل أغدا على أنواع البيانات الاستقرائية ومطابقة الأنماط الدول:

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

data Bad : Set where
  bad : (Bad → Bad) → Bad

لأن هناك حدوث سلبي من سيئة في الحجة إلى المنشئ.

لماذا هذا الشرط ضروري لأنواع البيانات الاستقرائي?

Answer 1

نوع البيانات الذي أعطيته هو خاص في أنه هو تضمين من غير مكتوب حساب لامدا.

data Bad : Set where
  bad : (Bad → Bad) → Bad

unbad : Bad → (Bad → Bad)
unbad (bad f) = f

دعونا نرى كيف.تذكر أن حساب لامدا غير المكتوب له هذه المصطلحات:

 e := x | \x. e | e e'

يمكننا تحديد الترجمة [[e]] من مصطلحات حساب لامدا غير المكتوبة إلى مصطلحات أجدا من النوع Bad (وإن لم يكن في أغدا):

[[x]]     = x
[[\x. e]] = bad (\x -> [[e]])
[[e e']]  = unbad [[e]] [[e']]

يمكنك الآن استخدام مصطلح لامدا غير المنتهي المفضل لديك لإنتاج مصطلح غير منتهي من النوع Bad.على سبيل المثال ، يمكننا ترجمة (\x. x x) (\x. x x) إلى التعبير غير المنتهي عن النوع Bad أدناه:

unbad (bad (\x -> unbad x x)) (bad (\x -> unbad x x))

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

Answer 2

مثال على كيف يسمح لنا نوع البيانات هذا بالسكن في أي نوع معطى في تيرنر ، دي إيه.(2004-07-28), مجموع البرمجة الوظيفية, ، طائفة.3.1, صفحة 758 في المادة 2:يجب أن يكون نوع العودية متغاير."

---

دعونا نجعل مثالا أكثر تفصيلا باستخدام هاسكل.سنبدأ مع" سيئة " نوع البيانات العودية

data Bad a = C (Bad a -> a)

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

ال ص كومبيناتور في حساب لامدا غير المكتوب يعرف بأنه

Y = λf.(λx.f (x x)) (λx.f (x x))

مفتاح ذلك هو أننا نطبق x لنفسها في x x.في اللغات المكتوبة ، هذا غير ممكن بشكل مباشر ، لأنه لا يوجد نوع صالح x يمكن أن يكون.ولكن لدينا Bad نوع البيانات يسمح هذا مودولو إضافة / إزالة منشئ:

selfApp :: Bad a -> a
selfApp (x@(C x')) = x' x

أخذ x :: Bad a, ، يمكننا فك منشئها وتطبيق الوظيفة من الداخل إلى x نفسها.بمجرد أن نعرف كيفية القيام بذلك ، فإنه من السهل لبناء كومبيناتور ص:

yc :: (a -> a) -> a
yc f =  let fxx = C (\x -> f (selfApp x))  -- this is the λx.f (x x) part of Y
        in selfApp fxx

لاحظ أن لا selfApp ولا yc هي العودية ، لا يوجد استدعاء العودية من وظيفة لنفسها. يظهر العودية فقط في نوع البيانات العودية لدينا.

يمكننا التحقق من أن كومبيناتور شيدت في الواقع يفعل ما ينبغي.يمكننا أن نجعل حلقة لا نهائية:

loop :: a
loop = yc id

أو حساب دعنا نقول غد:

gcd' :: Int -> Int -> Int
gcd' = yc gcd0
  where
    gcd0  :: (Int -> Int -> Int) -> (Int -> Int -> Int)
    gcd0 rec a b  | c == 0     = b
                  | otherwise  = rec b c
      where c = a `mod` b