هل هذه الطريقة الصحيحة لكتابة وظيفة foldr حزقيل؟

Question

وكنت أفعل تدريبات من قسم YAHT في العودية نوع البيانات ، وجدت كتابة وظيفة listFoldr صعبة بعض الشيء (ويرجع ذلك أساسا لم أكن أفهم حقا الفرق بين foldl وfoldr في البداية). عندما أدركت أخيرا بالضبط كيف تعمل وظيفة foldr، قررت أن تبادل بسيط من الحجج وظيفة سيكون كل ما تريد ان تكون بحاجة الى تغيير بلدي وظيفة listFoldl إلى وظيفة listFoldr:

listFoldl f i [] = i
listFoldl f i (x:xs) = listFoldl f (f i x) xs

listFoldr f i [] = i
listFoldr f i (x:xs) = listFoldr f (f x i) xs

ويبدو أن هذا العمل (فعلت المزيد من الاختبارات من هذا):

Main> foldr (-) 4 [1, 2, 3]
-2
Main> listFoldr (-) 4 [1, 2, 3]
-2

ولكن نظرا لممارسة إلى حد مختلفة من الألغام. listFoldl من هو بالضبط نفس الألغام، ولكن ننظر listFoldr بها:

listFoldr f i [] = i
listFoldr f i (x:xs) = f x (listFoldr f i xs)

ما الحل الأفضل، والألغام أو لهم؟ هو واحد منهم غير صحيحة؟ (في بلدي التجارب، وكلاهما في نهاية المطاف مع نفس النتيجة بالضبط ...)

Answer 1

وأعتقد أنك معالجة العناصر في "ترتيب المعاكس"، وهكذا لك هو ليس صحيحا.

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

listfoldr f "" ["a", "b", "c"]

وحيث 'و' هي وظيفة على غرار

f s1 s2 = "now processing f(" @ s1 @ "," @ s2 @ ")\n"

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

و(لاحظ أن هذا لم تظهر في المثال الخاص بك لأن الرياضيات "4-1-2-3" غلة نفس الإجابة ب "4-3-2-1".)

Answer 2

والحل الخاص بك هو غير صحيح بالتأكيد. لقد نفذت مجرد foldl فيه f وظيفة يأخذ الحجج بالترتيب العكسي. على سبيل المثال ما هو الخطأ، ومن المفترض foldr (:) [] أن يكون تحديد وظيفة في القوائم، ولكن عكس الدالة القائمة. هناك الكثير من الأسباب الأخرى لماذا وظيفة ليست foldr، مثل كيفية عمل foldr على قوائم لانهائية ولك لا. بل هو محض صدفة أنها هي نفسها في المثال الخاص بك، لأن 3 - (2 - (1 - 4)) == 1 - (2 - (3 - 4)). أعتقد أن عليك أن تبدأ من نقطة الصفر والنظر في الكيفية التي من المفترض foldr للعمل.

Answer 3

ويتم تقسيم تفضلوا بقبول فائق الاحترام. تحاول ذلك مع شيء لا ينتهي مع نتيجة رقمية واحدة.

eg: listFoldr (++) "a" ["b", "c", "d"]

أنت معالجة في الاتجاه الخاطئ.

Answer 4

في قائمة [x1, x2, ..., xk]، يحسب listFoldr بك

 f xk (... (f x2 (f x1 i)) ...)

وحين foldr يجب حساب

 f x1 (f x2 (... (f xk i) ...))

(وعلى سبيل المقارنة، يحسب foldl

f (... (f (f i x1) x2) ...) xk

وأساسا، listFoldr f = foldl (flip f)).

وأنت حالة اختبار أمر مؤسف، لأن

3 - (2 - (1 - 4)) = 1 - (2  - (3 - 4))

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