هل أستخدم التفكير المعادن الصوتي حول تعريف المرشح من حيث FoldR؟

Question

حسنًا ، هذا هو تعريف وظيفة المرشح باستخدام Foldr:

myFilter p xs = foldr step [] xs
    where step x ys | p x       = x : ys
                    | otherwise = ys

لذلك على سبيل المثال ، دعنا نقول أن لدي هذه الوظيفة:

myFilter odd [1,2,3,4]

لذلك سيكون:

foldr step [] [1,2,3,4]

وسيكون هذا

step 1 (foldr step [] [2,3,4])

وسيكون هذا

step 1 (step 2 (foldr step [] [3,4]))

وسيكون هذا

step 1 (step 2 (step 3 (foldr step [] [4])))

وسيكون هذا

step 1 (step 2 (step 3 (step 4 (foldr step [] []))))

و foldr step [] [] هو [] لذا:

step 1 (step 2 (step 3 (step 4 [])))

الآن سنصل بالفعل إلى step وظيفة.
هنا هو تعريف step داخل myFilter الوظيفة ، من الأعلى:

step x ys | p x       = x : ys
          | otherwise = ys

أيضا ، أذكرك بذلك p هو في الواقع odd وظيفة في مثالنا.

حسنًا ، مرة أخرى ، نحن هنا:

step 1 (step 2 (step 3 (step 4 [])))

و

x = 4 في الأكثر داخلية step, ، و 4 ليس غريبًا ، لذلك نعود ys, ، الذي []

حتى الآن نحصل على هذا:

step 1 (step 2 (step 3 []))

الآن ، في الأكثر داخلية step, x = 3, ، و 3 غريب ، لذلك نعود x:ys, ، الذي 3 : [], ، الذي [3], والآن نحصل على:

step 1 (step 2 [3])

والآن ، في الداخلية step, x = 2, ، و 2 ليس غريبًا ، لذلك نعود ys, ، الذي [3], ، والآن سنحصل على:

step 1 [3]

و الأن، x = 1, ، و 1 غريب ، لذلك نعود x : ys, ، الذي 1 : [3], ، الذي [1,3].

النهاية :-).

هل أنا على حق في كل حركاتي؟
شكر كثيرا :-).

ملاحظة myFilter من الكتاب العالم الحقيقي هاسكل, ، في الفصل 4.

Answer 1

هذا يبدو صحيحا بالنسبة لي في القراءة الأولى.

الشيء المهم الذي يجب تذكره هو أنه من أجل تحقيق التقييم الكسول ، سوف ينظر Haskell بالفعل إلى الأشياء في الاتجاه الآخر. بمعنى آخر ، يكون التسلسل الحقيقي أشبه

step 1 (step 2 (step 3 (step 4 [])))

يصبح

step 1 <block1>

الذي يصبح

[1, <block1>]

ثم إذا حاولت سحب العنصر التالي من تلك القائمة ، فسيتم تقييمه

[1, step 2 <block2>]

الذي يصبح

[1, <block2>]

ثم محاولة التقييم

[1, step 3 (step 4 [])]

تحول الى

[1, step 3 <block3>]

الذي يصبح

[1, 3, <block3>]

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

Answer 2

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

إذا كانت نتيجة الدعوة إلى myFilter يستخدم (على سبيل المثال مطبوع) ، سيتم تقييم الوظيفة بالترتيب التالي:

myFilter odd [1,2,3,4]

لأول مرة myFilter يتم تقييم الوظيفة:

foldr step [] [1,2,3,4]

حاليا foldr هل الوظيفة الخارجية ويتم تقييمها:

step 1 (foldr step [] [2,3,4])

حاليا step يتم تقييم إنتاج أ 1, ، حيث 1 أمر غريب:

1 : foldr step [] [2,3,4]

الآن يتوفر العنصر الأول من قائمة النتائج ويمكن استخدامه بواسطة وظيفة الاتصال. إذا كانت وظيفة الاتصال تستخدم أيضًا ، فستستمر تقييم العناصر التالية مع foldr:

1 : step 2 (foldr step [] [3,4])

تقييم step الآن لا ينتج أي عناصر جديدة ، لأن 2 حتى:

1 : foldr step [] [3,4]

لذا foldr تكرارا:

1 : step 3 (foldr step [] [4])

التقييم الآن step ينتج عنه 3:

1 : 3 : foldr step [] [4]

التقييم foldr;

1 : 3 : step 4 (foldr step [] [])

و step مرة أخرى:

1 : 3 : foldr step [] []

أخيراً foldr يقيم في قائمة فارغة:

1 : 3 : []

Answer 3

للوهلة الأولى ، تبدو الخطوات التي اتخذتها في مثالك المحدد صحيحة بشكل فردي. ومع ذلك ، أود أن أشير إلى أن كلاهما filter و foldr يمكن تطبيقها بشكل مفيد قوائم لا حصر لها-والتي يجب أن تشير إلى أن ترتيب خطواتك غير صحيح بقدر ما يتعلق الأمر Haskell.