Foldl مقابل سلوك Foldr مع قوائم لا حصر لها

Question

رمز وظيفة Myany في هذا السؤال يستخدم Foldr. يتوقف عن معالجة قائمة لا حصر لها عندما يتم استيفاء المسند.

أعيد كتابته باستخدام foldl:

myAny :: (a -> Bool) -> [a] -> Bool
myAny p list = foldl step False list
   where
      step acc item = p item || acc

(لاحظ أن الوسائط إلى وظيفة الخطوة يتم عكسها بشكل صحيح.)

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

حاولت تتبع تنفيذ الوظيفة كما في إجابة Apocalisp:

myAny even [1..]
foldl step False [1..]
step (foldl step False [2..]) 1
even 1 || (foldl step False [2..])
False  || (foldl step False [2..])
foldl step False [2..]
step (foldl step False [3..]) 2
even 2 || (foldl step False [3..])
True   || (foldl step False [3..])
True

ومع ذلك ، ليست هذه هي الطريقة التي تتصرف بها الوظيفة. كيف يكون هذا الخطأ؟

Answer 1

كيف foldيبدو أن S تختلف مصدرًا متكررًا للارتباك ، لذا إليك نظرة عامة أكثر عمومية:

النظر في طي قائمة القيم n [x1, x2, x3, x4 ... xn ] مع بعض الوظائف f والبذور z.

foldl هو:

• اليسار الترابطية: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• ذيل العودية: يتكرر من خلال القائمة ، وإنتاج القيمة بعد ذلك
• كسول: لا يتم تقييم أي شيء حتى يلزم النتيجة
• للخلف: foldl (flip (:)) [] يعكس قائمة.

foldr هو:

• الحق في الترابط: f x1 (f x2 (f x3 (f x4 ... (f xn z) ... )))
• عودية في حجة: ينطبق كل تكرار f إلى القيمة التالية ونتيجة طي بقية القائمة.
• كسول: لا يتم تقييم أي شيء حتى يلزم النتيجة
• إلى الأمام: foldr (:) [] إرجاع قائمة دون تغيير.

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

من الواضح أن هذا بعيدة كل البعد عن إعادة ذيل الذيل الفعال الذي يعرفه معظم المبرمجين الوظيفيين والحب!

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

من ناحية أخرى ، فكر foldr. إنه كسول أيضًا ، ولكن لأنه يعمل إلى الأمام, ، كل تطبيق f يضاف إلى داخل من النتيجة. لذلك ، لحساب النتيجة ، يقوم Haskell بنيات أ غير مرتبطة تطبيق الوظيفة ، الوسيطة الثانية منها هي بقية القائمة المطوية. إذا f هو كسول في وسيطتها الثانية-مُنشئ بيانات ، على سبيل المثال-ستكون النتيجة كسول بشكل متزايد, ، مع كل خطوة من الطية المحسوبة فقط عندما يتم تقييم جزء من النتيجة التي تحتاج إلى تقييمها.

لذلك يمكننا أن نرى لماذا foldr يعمل أحيانًا على قوائم لا حصر لها متى foldl لا: يمكن للأولى تحويل قائمة لا حصر لها إلى بنية بيانات لا حصر لها كسول ، في حين يجب على الأخير فحص القائمة بأكملها لإنشاء أي جزء من النتيجة. من ناحية أخرى، foldr مع وظيفة تحتاج إلى كلا الوسيطين على الفور ، مثل (+), ، يعمل (أو بالأحرى ، لا يعمل) مثل foldl, ، بناء تعبير ضخم قبل تقييمه.

لذا فإن النقطتين المهمينتين يجب ملاحظتهما هاتان:

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

ربما لاحظت أنه يبدو foldr يمكن أن تفعل كل شيء foldl يمكن ، بالإضافة إلى المزيد. هذا صحيح! في الواقع، Foldl لا طائل منه تقريبًا!

ولكن ماذا لو كنا نريد أن ننتج نتيجة غير بسيطة عن طريق طي فوق قائمة كبيرة (ولكن ليست غير محدودة)؟ لهذا ، نريد أ طية صارمة, ، أيّ المكتبات القياسية التي توفرها:

foldl' هو:

• اليسار الترابطية: f ( ... (f (f (f (f z x1) x2) x3) x4) ...) xn
• ذيل العودية: يتكرر من خلال القائمة ، وإنتاج القيمة بعد ذلك
• حازم: يتم تقييم كل تطبيق وظيفة على طول الطريق
• للخلف: foldl' (flip (:)) [] يعكس قائمة.

لان foldl' هو حازم, ، لحساب النتيجة سوف هاسكل تقييم f في كل خطوة ، بدلاً من ترك الوسيطة اليسرى تتراكم تعبيرًا ضخمًا غير مقيد. هذا يعطينا عودة الذيل المعتادة والفعالة التي نريدها! بعبارات أخرى:

• foldl' يمكن طي القوائم الكبيرة بكفاءة.
• foldl' سيتم تعليقه في حلقة لا حصر لها (لا تسبب في تدفق مكدس) في قائمة لا حصر لها.

هاسكل ويكي صفحة تناقش هذا, ، كذلك.

Answer 2

myAny even [1..]
foldl step False [1..]
foldl step (step False 1) [2..]
foldl step (step (step False 1) 2) [3..]
foldl step (step (step (step False 1) 2) 3) [4..]

إلخ.

حدسي، foldl دائمًا ما يكون على "الخارج" أو على "اليسار" حتى يتم توسيعه أولاً. لا نهاية.

Answer 3

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

Answer 4

لا أعرف هاسكل ، لكن في المخطط ، fold-right سوف "يتصرف" دائمًا على العنصر الأخير من القائمة أولاً. وبالتالي ، لن يعمل مع القائمة الدورية (وهو نفس القائمة اللانهائية).

لست متأكدًا إذا fold-right يمكن كتابة ذيل ، ولكن بالنسبة لأي قائمة دورية ، يجب أن تحصل على فائض مكدس. fold-left يتم تنفيذ OTOH عادةً مع عودة الذيل ، وسوف يتعثر في حلقة لا حصر لها ، إن لم تكن تنهيها مبكرًا.