كيف يمكنك أن تعرف متى تستخدم أضعاف اليسار إلى حظيرة الحق ؟

Question

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

لذا ما أريد أن أعرفه هو:

• ما هي بعض القواعد الأساسية لتحديد ما إذا كان أضعاف اليسار أو أضعاف صحيح ؟
• كيف يمكن بسرعة تحديد نوع أضعاف لاستخدام بالنظر إلى المشكلة التي تواجه أنا ؟

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

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

Answer 1

يمكنك نقل الطية إلى علامة عامل التشغيل infix (الكتابة بينهما):

أضعاف هذا المثال باستخدام وظيفة المجمع x

fold x [A, B, C, D]

وبالتالي يساوي

A x B x C x D

الآن عليك فقط أن تفكر في ارتباط المشغل الخاص بك (عن طريق وضع قوسين!).

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

((A x B) x C) x D

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

foldl (-) [1, 2, 3] == (1 - 2) - 3 == 1 - 2 - 3 // - is left-associative

إذا كان عامل التشغيل الخاص بك مرتبطًا باليمين (الطية اليمنى)، سيتم تعيين الأقواس على النحو التالي:

A x (B x (C x D))

مثال:سلبيات المشغل

foldr (:) [] [1, 2, 3] == 1 : (2 : (3 : [])) == 1 : 2 : 3 : [] == [1, 2, 3]

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

Answer 2

أولين الرعشات متباينة منهم من يقول "foldl الأساسية قائمة مكرر" و "foldr الأساسية قائمة العودية المشغل". إذا نظرتم كيف foldl يعمل:

((1 + 2) + 3) + 4

يمكنك أن ترى المجمع (كما في ذيل العودية التكرار) التي يجري بناؤها.في المقابل ، foldr العائدات:

1 + (2 + (3 + 4))

حيث يمكنك أن ترى اجتياز أن حالة قاعدة 4 وبناء على النتيجة من هناك.

لذا يفترض سيادة الإبهام:إذا كان يبدو وكأنه قائمة التكرار, واحدة من شأنها أن تكون بسيطة إلى كتابة في كتابة-متكررة شكل foldl هو الطريق للذهاب.

ولكن حقا هذا سيكون على الأرجح الأكثر وضوحا من ترابطيات من المشغلين تستخدمه.إذا كانت اليسار النقابي ، استخدام foldl.إذا كانوا على حق-النقابي ، استخدام foldr.

Answer 3

أعطت الملصقات الأخرى إجابات جيدة ولن أكرر ما قالوه بالفعل.بما أنك قدمت مثال Scala في سؤالك، سأقدم مثالًا محددًا لـ Scala.مثل الخدع سبق أن قال، أ foldRight يحتاج للحفاظ n-1 إطارات المكدس، حيث n هو طول قائمتك وهذا يمكن أن يؤدي بسهولة إلى تجاوز سعة المكدس - ولا حتى التكرار الخلفي يمكن أن ينقذك من هذا.

أ List(1,2,3).foldRight(0)(_ + _) من شأنه أن يقلل إلى:

1 + List(2,3).foldRight(0)(_ + _)        // first stack frame
    2 + List(3).foldRight(0)(_ + _)      // second stack frame
        3 + 0                            // third stack frame 
// (I don't remember if the JVM allocates space 
// on the stack for the third frame as well)

بينما List(1,2,3).foldLeft(0)(_ + _) من شأنه أن يقلل إلى:

(((0 + 1) + 2) + 3)

والتي يمكن حسابها بشكل متكرر، كما هو الحال في بداية شئ List.

في لغة يتم تقييمها بدقة مثل Scala، أ foldRight يمكن بسهولة تفجير المكدس للقوائم الكبيرة، بينما أ foldLeft متعود.

مثال:

scala> List.range(1, 10000).foldLeft(0)(_ + _)
res1: Int = 49995000

scala> List.range(1, 10000).foldRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRight(List.scala:1081)
        at scala.List.foldRig...

لذلك فإن قاعدتي الأساسية هي - بالنسبة للمشغلين الذين ليس لديهم ارتباط محدد، استخدم دائمًا foldLeft, على الأقل في سكالا.بخلاف ذلك، اتبع النصائح الأخرى الواردة في الإجابات؛).

Answer 4

من الجدير بالذكر أيضًا (وأنا أدرك أن هذا يوضح ما هو واضح قليلاً)، في حالة العامل التبادلي، يكون الاثنان متكافئين إلى حد كبير.في هذه الحالة قد يكون Foldl هو الخيار الأفضل:

طي:(((1 + 2) + 3) + 4) يمكن حساب كل عملية وتحمل القيمة المتراكمة للأمام

مجلد:(1 + (2 + (3 + 4))) يحتاج إلى إطار مكدس ليتم فتحه 1 + ? و 2 + ? قبل الحساب 3 + 4, ، فإنه يحتاج إلى العودة وإجراء الحساب لكل منها.

أنا لست خبيرًا كافيًا في اللغات الوظيفية أو تحسينات المترجم لأقول ما إذا كان هذا سيحدث فرقًا بالفعل ولكن من المؤكد أنه يبدو من الأنظف استخدام Foldl مع عوامل التشغيل التبادلية.