الطي (دالة من الرتبة العليا)

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة

في البرمجة الوظيفية ، تُعدّ عملية الطي (Fold) دالةً من الرتبة العليا تُحلّل بنية بيانات تكرارية ، وتُعيد، من خلال استخدام عملية دمج مُحدّدة، تجميع نتائج معالجة أجزائها المُكوّنة بشكل تكراري ، لتكوين قيمة مُعادة. تُعرف عملية الطي أيضًا باسم الاختزال (reduce )، أو التجميع (accumulate )، أو التجميع (aggregate) ، أو الضغط (compress )، أو الحقن (inject) . عادةً ما تُقدّم عملية الطي مع دالة دمج، وعقدة عليا في بنية البيانات ، وربما بعض القيم الافتراضية التي تُستخدم في ظروف مُحدّدة. ثمّ تُباشر عملية الطي بدمج عناصر التسلسل الهرمي لبنية البيانات ، باستخدام الدالة بطريقة مُنظّمة.

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

كتحولات هيكلية

يمكن اعتبار الطي بمثابة استبدالٍ ثابتٍ للمكونات الهيكلية لبنية البيانات بالدوال والقيم. على سبيل المثال، تُبنى القوائم في العديد من لغات البرمجة الوظيفية من عنصرين أساسيين: إما أن تكون أي قائمة فارغة، تُسمى عادةً nil ( [])، أو تُنشأ بإضافة عنصر قبل قائمة أخرى، مما يُنشئ ما يُسمى عقدة cons ( )، الناتجة عن تطبيق دالة (تُكتب على شكل نقطتين رأسيتين في لغة Haskell ). يمكن النظر إلى الطي على القوائم على أنه استبدال قيمة nil في نهاية القائمة بقيمة محددة، واستبدال كل عقدة cons بدالة محددة. يمكن تمثيل هذه الاستبدالات بيانيًا.  Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) cons(:)

هناك طريقة أخرى لإجراء التحويل الهيكلي بطريقة متسقة، حيث يتم عكس ترتيب الرابطين لكل عقدة عند إدخالهما في دالة الدمج:

توضح هذه الصور طي القائمة من اليمين واليسار بصريًا. كما تُبرز حقيقة أن foldr (:) []هي دالة التطابق على القوائم ( نسخة سطحية في لغة ليسب )، حيث أن استبدال cons بـ consو nil بـ nilلن يُغير النتيجة. يُشير مخطط الطي الأيسر إلى طريقة سهلة لعكس القائمة، foldl (flip (:)) []. لاحظ أنه يجب عكس معاملات cons، لأن العنصر المراد إضافته هو الآن المعامل الأيمن لدالة الدمج. نتيجة أخرى سهلة الملاحظة من هذه الزاوية هي كتابة دالة الخريطة ذات الرتبة الأعلى بدلالة foldr، وذلك بتركيب الدالة التي تعمل على العناصر باستخدام cons، كما يلي:

map f = foldr (( : ) . f ) []

حيث أن النقطة (.) هي عامل يدل على تركيب الدوال .

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

في القوائم

ينتج عن طي القائمة [1,2,3,4,5]باستخدام عامل الجمع العدد 15، وهو مجموع عناصر القائمة [1,2,3,4,5]. ويمكن، بتقريبٍ تقريبي، اعتبار هذا الطي بمثابة استبدال الفواصل في القائمة بعملية الجمع (+)، مما يعطي 1 + 2 + 3 + 4 + 5. [ 1 ]

في المثال أعلاه، تُعدّ عملية الجمع (+) عملية تجميعية ، لذا ستكون النتيجة النهائية واحدة بغض النظر عن استخدام الأقواس، على الرغم من اختلاف طريقة حسابها. في الحالة العامة للدوال الثنائية غير التجميعية، قد يؤثر ترتيب دمج العناصر على قيمة النتيجة النهائية. في القوائم، توجد طريقتان واضحتان لتنفيذ ذلك: إما بدمج العنصر الأول مع نتيجة دمج باقي العناصر بشكل متكرر (وتُسمى الطي الأيمن )، أو بدمج نتيجة دمج جميع العناصر باستثناء العنصر الأخير بشكل متكرر مع العنصر الأخير (وتُسمى الطي الأيسر ). يتوافق هذا مع كون المعامل الثنائي إما تجميعيًا من اليمين أو تجميعيًا من اليسار، وفقًا لمصطلحات لغتي هاسكل وبرولوج . في حالة الطي الأيمن، يُكتب المجموع بين قوسين على النحو التالي 1 + (2 + (3 + (4 + 5))): ، بينما في حالة الطي الأيسر، يُكتب بين قوسين على النحو التالي (((1 + 2) + 3) + 4) + 5: .

من الناحية العملية، من الملائم والطبيعي تحديد قيمة ابتدائية، تُستخدم في حالة الطي الأيمن عند الوصول إلى نهاية القائمة، وفي حالة الطي الأيسر، تُستخدم القيمة التي تُدمج مبدئيًا مع العنصر الأول من القائمة. في المثال أعلاه، تُختار القيمة 0 ( العنصر المحايد للجمع1 + (2 + (3 + (4 + (5 + 0)))) ) كقيمة ابتدائية، مما يُعطي نتيجة الطي الأيمن، ((((0 + 1) + 2) + 3) + 4) + 5ونتيجة الطي الأيسر. أما في عملية الضرب، فإن اختيار القيمة 0 كقيمة ابتدائية غير مناسب: لأن 0 * 1 * 2 * 3 * 4 * 5 = 0العنصر المحايد للضرب هو 1. وهذا يُعطينا النتيجة 1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!.

الطيات الخطية مقابل الطيات الشبيهة بالشجرة

يُعدّ استخدام قيمة ابتدائية ضروريًا عندما تكون دالة الدمج f غير متناظرة في أنواعها (مثلًا a → b → b)، أي عندما يختلف نوع نتيجتها عن نوع عناصر القائمة. في هذه الحالة، يجب استخدام قيمة ابتدائية من نفس نوع نتيجة f ، لكي يكون من الممكن تنفيذ سلسلة خطية من التطبيقات. يتحدد اتجاه القيمة الابتدائية، يسارًا أو يمينًا، بناءً على أنواع الوسائط المتوقعة من دالة الدمج. إذا كان الوسيط الثاني هو الذي يجب أن يكون من نفس نوع النتيجة، فيمكن اعتبار f عملية ثنائية تجمع العناصر على اليمين ، والعكس صحيح.

عندما تكون الدالة من نوع " ماغما " ، أي متناظرة في أنواعها a → a → a، ويكون نوع النتيجة هو نفسه نوع عناصر القائمة، يمكن وضع الأقواس بشكل عشوائي، مما يُنشئ شجرة ثنائية من التعبيرات الفرعية المتداخلة، على سبيل المثال ((1 + 2) + (3 + 4)) + 5. إذا كانت العملية الثنائية f تجميعية، فستكون هذه القيمة مُحددة جيدًا، أي أنها ستكون نفسها لأي استخدام للأقواس، على الرغم من اختلاف تفاصيل حسابها. قد يؤثر هذا بشكل كبير على الكفاءة إذا كانت f غير صارمة .

بينما تكون الطيات الخطية موجهة نحو العقد وتعمل بطريقة متسقة لكل عقدة من القائمة ، فإن الطيات الشبيهة بالشجرة موجهة نحو القائمة بأكملها وتعمل بطريقة متسقة عبر مجموعات العقد.

طيات خاصة للقوائم غير الفارغة

كثيرًا ما نرغب في اختيار العنصر المحايد للعملية f كقيمة ابتدائية z . عندما لا تبدو أي قيمة ابتدائية مناسبة، على سبيل المثال، عند الرغبة في طي الدالة التي تحسب أكبر عنصر من بين مُعامليها على قائمة غير فارغة للحصول على أكبر عنصر في القائمة، توجد صيغ بديلة foldrتستخدم foldlالعنصر الأخير والأول من القائمة على التوالي كقيمة ابتدائية. في لغة هاسكل والعديد من اللغات الأخرى، تُسمى هذه الصيغ foldr1بـ `f` و foldl1`f`، حيث يشير الرقم 1 إلى التوفير التلقائي لعنصر ابتدائي، وإلى حقيقة أن القوائم التي تُطبق عليها يجب أن تحتوي على عنصر واحد على الأقل.

تستخدم هذه العمليات الثنائية المتناظرة النوع: يجب أن تكون أنواع كل من وسيطاتها ونتيجتها متطابقة. يقترح ريتشارد بيرد في كتابه الصادر عام 2010 [ 2 ] "دالة طي عامة على القوائم غير الفارغة" foldrnالتي تحوّل العنصر الأخير، بتطبيق دالة وسيط إضافية عليه، إلى قيمة من نوع النتيجة قبل بدء عملية الطي نفسها، وبالتالي فهي قادرة على استخدام عملية ثنائية غير متناظرة النوع مثل العملية العادية foldrلإنتاج نتيجة من نوع مختلف عن نوع عناصر القائمة.

تطبيق

طيات خطية

باستخدام لغة هاسكل كمثال، foldlويمكن foldrصياغتها في بضع معادلات.

foldl :: ( b -> a -> b ) -> b -> [ a ] ​​-> b foldl f z [] = z foldl f z ( x : xs ) = foldl f ( f z x ) xs

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

foldr :: ( a -> b -> b ) -> b -> [ a ] ​​-> b foldr f z [] = z foldr f z ( x : xs ) = f x ( foldr f z xs )

إذا كانت القائمة فارغة، فإن النتيجة هي القيمة الأولية z. وإذا لم تكن كذلك، فقم بتطبيق f على العنصر الأول ونتيجة طي الباقي.

طيات تشبه طيات الأشجار

يمكن طي القوائم بطريقة تشبه الشجرة، سواء للقوائم المحدودة أو للقوائم غير المحددة:

foldt f z [] = z foldt f z [ x ] = f x z foldt f z xs = foldt f z ( pairs f xs ) foldi f z [] = z foldi f z ( x : xs ) = f x ( foldi f z ( pairs f xs )) pairs f ( x : y : t ) = f x y : pairs f t pairs _ t = t

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

طي القوائم غير الفارغة

foldl1 f [ x ] = x foldl1 f ( x : y : xs ) = foldl1 f ( f x y : xs )foldr1 f [ x ] = x foldr1 f ( x : xs ) = f x ( foldr1 f xs )foldt1 f [ x ] = x foldt1 f ( x : y : xs ) = foldt1 f ( fx y : pairs f xs ) foldi1 f [ x ] = x foldi1 f ( x : xs ) = fx ( foldi1 f ( pairs f xs ) )​

اعتبارات ترتيب التقييم

في حالة التقييم الكسول ، أو غير الصارمfoldr ، ستُعيد الدالة f تطبيقها على رأس القائمة مباشرةً، بالإضافة إلى حالة التكرار التي تُطبق على باقي القائمة. بالتالي، إذا تمكنت f من إنتاج جزء من نتيجتها دون الرجوع إلى حالة التكرار في وسيطها الثاني ، ولم يُطلب باقي النتيجة، فسيتوقف التكرار (على سبيل المثال، ). هذا يسمح بتطبيق عمليات الطي من اليمين على القوائم اللانهائية. في المقابل، ستستدعي الدالة f نفسها مباشرةً بمعاملات جديدة حتى تصل إلى نهاية القائمة. يمكن ترجمة هذا التكرار الذيل بكفاءة كحلقة، لكنه لا يستطيع التعامل مع القوائم اللانهائية على الإطلاق، إذ سيستمر في التكرار إلى ما لا نهاية في حلقة لا نهائية .head==foldr(\ab->a)(error"empty list")foldl

عند الوصول إلى نهاية القائمة، يتم بناء تعبير فعليًا من خلال تطبيقات foldlمتداخلة من اليسار f، ثم يُعرض هذا التعبير على الدالة المُستدعية لتقييمه. إذا fأشارت الدالة إلى وسيطها الثاني أولًا هنا، وتمكنت من إنتاج جزء من نتيجتها دون الرجوع إلى حالة التكرار (هنا، على يسارها ، أي في وسيطها الأول )، فسيتوقف التكرار. هذا يعني أنه بينما foldrيتكرر التعبير على اليمين ، فإنه يسمح لدالة الدمج الكسولة بفحص عناصر القائمة من اليسار؛ وعلى العكس، بينما foldlيتكرر التعبير على اليسار ، فإنه يسمح لدالة الدمج الكسولة بفحص عناصر القائمة من اليمين، إذا رغبت في ذلك (على سبيل المثال، ).last==foldl(\ab->b)(error"empty list")

يُعدّ عكس القائمة عمليةً تكراريةً ذيليةً أيضًا (يمكن تنفيذها باستخدام ). في القوائم المحدودة ، يعني هذا أنه يمكن دمج دالتي left-fold و reverse لتنفيذ عملية right-fold بطريقة تكرارية ذيلية (انظر )، مع تعديل الدالة بحيث تعكس ترتيب وسائطها (أي، )، مما يؤدي إلى بناء تمثيل للتعبير بشكل تكراري ذيلي، وهو التمثيل الذي ستبنيه right-fold. يمكن التخلص من بنية القائمة الوسيطة الزائدة باستخدام أسلوب تمرير الاستمرارية ، ؛ وبالمثل، ( لا حاجة إلى إلا في لغات مثل Haskell مع ترتيب وسائطها المعكوس لدالة الدمج الخاصة بـ ، على عكس مثلاً في Scheme حيث يُستخدم نفس ترتيب الوسائط لدوال الدمج لكل من و ).rev=foldl(\ysx->x:ys)[]1+>(2+>(3+>0))==((0<+3)<+2)<+1ffoldrfz==foldl(flipf)z.foldl(flip(:))[]foldrfzxs==foldl(\kx->k.fx)idxszfoldlfzxs==foldr(\xk->k.flipfx)idxszflipfoldlfoldlfoldr

من النقاط التقنية الأخرى أنه في حالة الطي الأيسر باستخدام التقييم الكسول، لا يتم تقييم المعامل الأولي الجديد قبل إجراء الاستدعاء التكراري. قد يؤدي هذا إلى تجاوز سعة المكدس عند الوصول إلى نهاية القائمة ومحاولة تقييم التعبير الناتج الذي قد يكون ضخمًا. لهذا السبب، غالبًا ما توفر هذه اللغات صيغة أكثر صرامة للطي الأيسر تُجبر على تقييم المعامل الأولي قبل إجراء الاستدعاء التكراري. في لغة هاسكل، هذه هي الدالة `prime` foldl'(لاحظ الفاصلة العليا، تُنطق "برايم") في Data.Listالمكتبة (مع العلم أن فرض قيمة مُنشأة باستخدام مُنشئ بيانات كسول لن يُجبر مكوناتها تلقائيًا). عند دمجها مع الاستدعاء التكراري النهائي، تقترب هذه الطيات من كفاءة الحلقات، مما يضمن تشغيلًا بمساحة ثابتة، عندما يكون التقييم الكسول للنتيجة النهائية مستحيلًا أو غير مرغوب فيه.

أمثلة

باستخدام مترجم لغة هاسكل ، يمكن توضيح التحويلات الهيكلية التي تقوم بها دوال الطي من خلال إنشاء سلسلة نصية:

λ > foldr ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0))))))))))))" λ > foldl ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)" λ > foldt ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ > foldi ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"

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

primes = 2 : _Y (( 3 : ) . minus [ 5 , 7 .. ] . foldi ( \ ( x : xs ) ys -> x : union xs ys ) [] . map ( \ p -> [ p * p , p * p + 2 * p .. ])) _Y g = g ( _Y g ) -- = g . g . g . g . ...

حيث تعمل الدالة unionعلى القوائم المرتبة بطريقة محلية لإنتاج اتحاد المجموعات وفرق المجموعات minusبكفاءة .

يمكن تعريف البادئة المحدودة للأعداد الأولية بإيجاز على أنها عملية طي لعملية فرق المجموعات على قوائم مضاعفات الأعداد الصحيحة المعدودة، كما يلي:

primesTo n = foldl1 minus [[ 2 * x , 3 * x .. n ] | x <- [ 1 .. n ]]

بالنسبة للقوائم المحدودة، على سبيل المثال، يمكن تعريف فرز الدمج (ونوعه الذي يزيل التكرارات ) بسهولة باستخدام الطي الشبيه بالشجرة كما يلي:nubsort

mergesort xs = foldt merge [] [[ x ] | x <- xs ] nubsort xs = foldt union [] [[ x ] | x <- xs ]

مع الدالة merge، وهي نسخة تحافظ على التكرارات من union.

headويمكن lastتعريف الدوال من خلال الطي على النحو التالي:

head = foldr ( \ x r -> x ) ( error "head: Empty list" ) last = foldl ( \ a x -> x ) ( error "last: Empty list" )

بلغات مختلفة

لغةالطي الأيسرالطي الأيمنطيّة يسارية بدون قيمة ابتدائيةطي لليمين بدون قيمة ابتدائيةانفتحملحوظات
APLfunc⍨/⌽initval,vectorfunc/vector,initvalfunc⍨/⌽vectorfunc/vector
سي شارب 3.0ienum.Aggregate(initval, func)ienum.Reverse().Aggregate(initval, func)ienum.Aggregate(func)ienum.Reverse().Aggregate(func)Aggregateهي طريقة امتداد،ienum وهي IEnumerable<T>كذلك في جميع لغات .NET
لغة سي++std::accumulate(begin, end, initval, func)std::accumulate(rbegin, rend, initval, func)في رأس الملف <numeric>begin، يمكن أن تكون المؤشرات عبارة عن مؤشر دالة أو كائن دالةend .rbeginrendfunc
C++17(initvalop ... oppack)(packop ... opinitval)(... oppack)(packop ...)تعبير الطي (فقط للقوالب المتغيرة ): opهو عامل ثنائي ( opيجب أن يكون كلا s متماثلين، على سبيل المثال، ) هو حزمة معلمات غير موسعة.(std::cout<<...<<args)pack
C++23std::ranges::fold_left(range, initval, func)std::ranges::fold_right(range, initval, func)std::ranges::fold_left_first(range, func)std::ranges::fold_right_last(range, func)كلاهما std::ranges::fold_left_firstيعودان مع الأخذ في std::ranges::fold_right_lastالاعتبار std::optionalفراغ range.
CFMLobj.reduce(func, initial)obj.reduce(func)حيث funcتستقبل هذه الدالة كمعاملات نتيجة العملية السابقة (أو initialالقيمة في التكرار الأول)؛ والعنصر الحالي؛ وفهرس أو مفتاح العنصر الحالي؛ ومرجع إلىobj
كلوجر(reduce funcinitvallist)(reduce funcinitval (reverse list))(reduce funclist)(reduce func (reverse list))انظر أيضًا clojure.core.reducers/fold
لغة الشفرة الشائعة(reduce funclist :initial-value initval)(reduce funclist :from-end t :initial-value initval)(reduce funclist)(reduce funclist :from-end t)
دreduce!func(initval, list)reduce!func(initval, list.reverse)reduce!func(list)reduce!func(list.reverse)في الوحدة النمطيةstd.algorithm
إكسيرList.foldl(list, acc, fun)List.foldr(list, acc, fun)راجع الوثائق للاطلاع على أمثلة الاستخدام
إلمList.foldl funinitiallistList.foldr funinitiallistانظر أيضًا واجهة برمجة تطبيقات القوائم
إرلانغlists:foldl(Fun, Accumulator, List)lists:foldr(Fun, Accumulator, List)
فا#List.fold funcinitvallistSeq.fold funcinitvalsequenceList.foldBack funclistinitvalList.reduce funclistSeq.reduce funcsequenceList.reduceBack funclistSeq.unfold funcinitval
بريقlist.fold(list, initial, func)yielder.fold(yielder, initial, func)list.fold_right(list, initial, func)list.reduce(list, func)yielder.reduce(yielder, func)yielder.unfold(initial, func)
جوسوIterable.fold(f(agg, e))Iterable.reduce(init, f(agg, e))Iterable.partition(f(e))جميعها عبارة عن دوال إضافية على واجهة جافا Iterable، كما يتم دعم المصفوفات أيضًا
رائعlist.inject(initval, func)list.reverse().inject(initval, func)list.inject(func)list.reverse().inject(func)
هاسكلfoldl funcinitvallistfoldr funcinitvallistfoldl1 funclistfoldr1 funclistunfoldr funcinitvalبالنسبة لـ foldl، تأخذ دالة الطي الوسائط بترتيب معاكس لترتيبها بالنسبة لـ foldr.
هاكسLambda.fold(iterable, func, initval)
جverb~/|.initval,arrayverb/ array,initvalverb~/|.arrayverb/ arrayيُطبّق u/y العلاقة الثنائية u بين عناصر y. "قاموس J: إدراج"
جافا 8+stream.reduce(initval, func)stream.reduce(func)
جافا سكريبت 1.8، إي سي إم إيه سكريبت 5array.reduce(func, initval)[ 3 ]array.reduceRight(func,initVal)array.reduce(func)array.reduceRight(func)الوسائط الرئيسية للمُختزل هي المُجمِّع والقيمة الحالية، ويمكننا استخدام وسائط اختيارية مثل الفهرس والمصفوفة.array.reduceRight((acc,value,idx,array)=>{},initvalue)
جولياfoldl(op, itr; [init])foldr(op, itr; [init])foldl(op, itr)foldr(op, itr)
كوتلينIterable.fold(initval, func)Iterable.foldRight(initval, func)Iterable.reduce(func)Iterable.reduceRight(func)تدعم مجموعات أخرى أيضًا fold[ 4 ] و [ 5 ]reduce . يوجد أيضًا [ 6 ] الذي يُختزل ( سواء كان نجاحًا أو فشلًا) إلى نوع الإرجاع الخاص بـ و .Result.fold(onSuccess, onFailure)Result<T>onSuccessonFailure
LFE(lists:foldl funcaccumlist)(lists:foldr funcaccumlist)
لغة الاتصالfold_left(Closure, Initial, List, Result)fold_right(Closure, Initial, List, Result)البيانات الوصفية التي يوفرها كائن المكتبة القياسية. يمكن أيضًا استخدام metaالاختصارات .foldlfoldr
خشب القيقبfoldl(func, initval, sequence)foldr(func, initval, sequence)foldl(func, sequence)foldr(func, sequence)
ماثيماتيكاFold[func, initval, list]Fold[func, initval, Reverse[list]]Fold[func, list]Fold[func, Reverse[list]]NestWhileList[func,, initval, predicate]Foldيتم دعم خاصية عدم تحديد قيمة ابتدائية في الإصدارات 10.0 وما فوق.
MATLABfold(@func, list, defaultVal)fold(@func, flip(list), defaultVal)fold(@func, list)fold(@func, flip(list))يتطلب Symbolic Math Toolbox، المدعوم من R2016b.
ماكسيماlreduce(func, list, initval)rreduce(func, list, initval)lreduce(func, list)rreduce(func, list)
أوكاميلList.fold_left funcinitvallistArray.fold_left funcinitvalarrayList.fold_right funclistinitvalArray.fold_right funcarrayinitval
أوز{FoldL ListFuncInitVal}{FoldR ListFuncInitVal}
طبيب عام/طبيب عامfold( f, A )
بيرلreduce blockinitval, listreduce blocklistفي List::Utilالوحدة النمطية
PHParray_reduce(array, func, initval)array_reduce(array_reverse(array), func, initval)array_reduce(array, func)array_reduce(array_reverse(array), func)عند initvalعدم تحديد قيمة، يتم استخدام NULL، لذا فهذه ليست دالة foldl1 حقيقية. قبل PHP 5.3، initvalيمكن أن تكون القيمة عددًا صحيحًا فقط. funcهي دالة رد نداء . مؤرشفة بتاريخ 28 نوفمبر 2020 على Wayback Machine . جرب array_reduce عبر الإنترنت.
بايثون 2.xreduce(func, list, initval)reduce(lambdax,y:func(y, x), reversed(list), initval)reduce(func, list)reduce(lambdax,y:func(y, x), reversed(list))
بايثون 3.xfunctools.reduce(func, list, initval)functools.reduce(lambdax,y:func(y, x), reversed(list), initval)functools.reduce(func, list)functools.reduce(lambdax,y:func(y, x), reversed(list))في وحدة functools . [ 7 ]
RReduce(func, list, initval)Reduce(func, list, initval, right=TRUE)Reduce(func, list)Reduce(func, list, right=TRUE)يدعم R الطي من اليمين والطي من اليسار أو اليمين مع أو بدون قيمة أولية من خلال rightوسيطات initالدالة Reduce.
مضرب(foldl func initval list)(foldr func initval list)
روبيenum.inject(initval, &block)enum.reduce(initval, &block)enum.reverse_each.inject(initval, &block)enum.reverse_each.reduce(initval, &block)enum.inject(&block)enum.reduce(&block)enum.reverse_each.inject(&block)enum.reverse_each.reduce(&block)في روبي 1.8.7 والإصدارات الأحدث، يمكن أيضًا تمرير رمز يمثل دالة بدلًا من كتلة. enumوهو عبارة عن تعداد. يرجى ملاحظة أن هذه التطبيقات للطي من اليمين خاطئة بالنسبة للدوال غير التبادلية &block(كما أن القيمة الأولية توضع في الجانب الخطأ).
الصدأiterator.fold(initval, func)iterator.rev().fold(initval, func)iterator.reduce(func)iterator.rev().reduce(func)iterator.rev()يتطلب iteratorأن يكون DoubleEndedIterator. [ 8 ]
سكالاlist.foldLeft(initval)(func)(initval /: list)(func)list.foldRight(initval)(func)(list :\ initval)(func)list.reduceLeft(func)list.reduceRight(func)كان الهدف من بناء جملة الطي الرمزي في لغة سكالا هو محاكاة الشجرة المائلة لليسار أو اليمين، والتي تُستخدم عادةً لشرح عملية الطي، [ 9 ] ولكن أُعيد تفسيرها لاحقًا على أنها رسم توضيحي لقطعة دومينو متساقطة. [ 10 ] تأتي النقطتان الرأسيتان من آلية بناء جملة عامة في سكالا، حيث يتم استدعاء عامل التشغيل الظاهر كطريقة على المعامل الأيسر مع تمرير المعامل الأيمن كوسيط، أو العكس إذا كان الحرف الأخير من عامل التشغيل هو نقطتان رأسيتان، ويتم تطبيق ذلك هنا بشكل متناظر.

تتميز لغة سكالا أيضًا بالطيات الشبيهة بالأشجار باستخدام الطريقة list.fold(z)(op). [ 11 ]

المخطط R 6 RS(fold-left funcinitvallist)(vector-fold funcinitvalvector)(fold-right funcinitvallist)(vector-fold-right funcinitvalvector)(reduce-left funcdefaultvallist)(reduce-right funcdefaultvallist)(unfold pfgseed[tail-gen])unfold-right pfgseed[tail](vector-unfold flengthinitial-seed···)(vector-unfold-right flengthinitial-seed···)srfi/1 srfi/43
أحاديث قصيرةaCollection inject: aValue into: aBlockaCollection reduce: aBlockلا يُعرّف معيار ANSI Smalltalk ذلك، #reduce:لكن العديد من التطبيقات تفعل.
لغة الآلة القياسيةfoldl funcinitvallistArray.foldl funcinitvalarrayfoldr funcinitvallistArray.foldr funcinitvalarrayتأخذ الدالة المُقدمة وسائطها في شكل مجموعة. بالنسبة لـ foldl، تأخذ دالة الطي الوسائط بنفس ترتيبها بالنسبة لـ foldr.
سويفتarray.reduce(initval, func)reduce(sequence, initval, func)array.reverse().reduce(initval, func)
XPathfold-left($input,$zero,$action)array:fold-left($input,$zero,$action)fold-right($input,$zero,$action)array:fold-right($input,$zero,$action)توجد دالتان لكل حالة لأن XPath يوفر تسلسلات للبيانات غير المهيكلة ومصفوفات للبيانات المهيكلة.
إكستندiterable.fold(initval,[func])iterable.reduce[func]

عالمية

دالة الطي هي دالة متعددة الأشكال . لأي دالة g لها تعريف

g [ ] = vg ( x : xs ) = fx ( gxs )​​

ويمكن التعبير عن g على النحو التالي [ 12 ]

g = foldr f v

أيضًا، في لغة كسولة ذات قوائم لا نهائية، يمكن تنفيذ مُركِّب النقطة الثابتة عبر الطي، [ 13 ] مما يثبت أنه يمكن تقليل التكرارات إلى عمليات طي:

y f = foldr ( \ _ -> f ) undefined ( repeat undefined )

انظر أيضاً

مراجع

  1. ↑ "وحدة هاسكل 6: دوال الطي من الرتبة العليا | أنطوني ديلر" . www.cantab.net . تم الاطلاع عليه بتاريخ 4 أبريل 2023 .
  2. ↑ ريتشارد بيرد، "درر تصميم الخوارزميات الوظيفية"، مطبعة جامعة كامبريدج 2010، رقم ISBN 978-0-521-51338-8، ص 42
  3. ↑ "Array.prototype.reduce() - JavaScript | MDN" . developer.mozilla.org . 2023-12-11 . تم الاطلاع عليه بتاريخ 2024-01-16 .
  4. ↑ "fold - لغة برمجة Kotlin" . Kotlin . Jetbrains . تم الاطلاع عليه بتاريخ 29 مارس 2019 .
  5. ↑ "reduce - لغة برمجة Kotlin" . Kotlin . Jetbrains . تم الاطلاع عليه بتاريخ 29 مارس 2019 .
  6. ↑ "النتيجة - لغة برمجة كوتلن" . كوتلن . جيت برينز . تم الاطلاع عليه بتاريخ 29 مارس 2019 .
  7. ↑ للمراجعةfunctools.reduce:import functools للمراجعةreduce:from functools import reduce
  8. ↑ "المكرر في core::iter" . Rust . فريق Rust . تم الاسترجاع في 22-06-2021 .
  9. ↑ أوديرسكي، مارتن (5 يناير 2008). "ردًا على: مدونة: رأيي في لغة سكالا" . مجموعة الأخبار : comp.scala.lang . مؤرشف من الأصل في 14 مايو 2015. تم الاطلاع عليه في 14 أكتوبر 2013 . 
  10. ↑ ستيرلينغ، نيكولاس (28 يوليو 2010). "فهم بديهي لعامل /: في لغة سكالا (foldLeft)" . تم الاطلاع عليه بتاريخ 24 يونيو 2016 .
  11. ↑ "Fold API - مكتبة Scala القياسية" . www.scala-lang.org . تم الاطلاع عليه بتاريخ 10 أبريل 2018 .
  12. ↑ هاتون، غراهام (1999). "دليل تعليمي حول شمولية وتعبيرية دالة fold" (ملف PDF) . مجلة البرمجة الوظيفية . 9 (4): 355-372 . doi : 10.1017/S0956796899003500 . تاريخ الاسترجاع: 26 مارس 2009 .
  13. ↑ بوب، بيرني. "الحصول على حل من الجانب الأيمن" (ملف PDF) . مجلة موناد ريدر (6): 5-16 . تم الاطلاع عليه في 1 مايو 2011 .