التعاودية المشتركة
المحتويات
- -- ----read---- ----write-ahead---
- (ln, b) = go l a
- k, f = 0, 1
- yield a
- ... yield from output
- a, b = 0, 1
- تاريخ
- yield tree.value
- where
- ... return result
- عاملي
- return 1
- n, f = 0, 1
- متوالية فيبوناتشي
- new_tree_list = []
- تعريف
- tl (conc a s) = s
- tl (conc a s) = s
- gen 0 p = []
- where
- where
- عبور الشجرة
- where
- yield f
- label( L, A, Ln, B),
- مناقشة
- label( L, A, Ln, B),
- yield f
- tree_list = [tree]
- return 1
- k, f = 0, 1
- أمثلة
بدايةً، في علوم الكمبيوتر، يُعد للتكرارالمشترك (Corecursion) نوعًا من العمليات التي تُعتبر مزدوجة للتكرار (recursion). فبينما يعمل التكرار بشكل تحليلي، يبدأ من البيانات الأبعد عن الحالة الأساسية ويُقسّمها إلى بيانات أصغر ويُكرّرها حتى الوصول إلى الحالة الأساسية، تعمل التكرارية (corecursion) بشكل اصطناعي، فتبدأ من الحالة الأساسية وتبني عليها، مُنتجةً بيانات متكررة أبعد عن الحالة الأساسية.ببساطة، تستعمل الخوارزميات التكرارية البيانات التي تُنتجها بنفسها، شيئًا فشيئًا، عندما تُصبح متاحة ومطلوبة، لإنتاج المزيد من البيانات. يُشير المفهوم المماثل ولكن المتميز إلى التكرار التوليدي(generative recursion)، والذي قد يفتقر إلى "اتجاه" محدد متأصل في التكرار المشترك والتكرار المتكرر. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
كذلك، بينما تسمح التكرارية (recursion) للبرامج بالعمل على بيانات معقدة بشكل تعسفي، شريطة أن يمكن اختزالها إلى بيانات بسيطة (حالات أساسية)، فإن التكرارية الأساسية (corecursion) تتيح للبرامج إنتاج هياكل بيانات معقدة بشكل تعسفي وربما لا نهائية، مثل التدفقات(streams). هذا ممكن طالما يمكن إنتاج هذه الهياكل من بيانات بسيطة (حالات أساسية) في تسلسل من الخطوات المحدودة.في حين أن التكرار قد لا ينتهي أبدًا، ولا يصل إلى حالة أساسية، يبدأ التكرار المشترك من حالة أساسية، وبالتالي يُنتج خطوات لاحقة بشكل حتمي، على الرغم من أنه قد يستمر إلى أجل غير مسمى (وبالتالي لا ينتهي في ظل التقييم الصارم)، أو قد يستهلك أكثر مما يُنتج فيصبح غير منتج. يمكن تفسير الكثير من الوظائف التي تُحلل تقليديًا على أنها متكررة، بطريقة بديلة وربما أكثر طبيعية، على أنها وظائف متكررة مشتركة تنتهي في مرحلة معينة، مثل علاقات التكرار كـ العامل (factorial).
في هذا الإطار، يمكن للتكرار المشترك (Corecursion) إنتاج هياكل بيانات محدودة وغير محدودة كنتائج، وقد يستعمل هياكل بيانات مرجعية ذاتية غالبًا ما يُستعمل التكرار المشترك جنبًا إلى جنب مع التقييم الكسول (lazy evaluation)، وذلك لإنتاج مجموعة فرعية محدودة فقط من بنية لا نهائية محتملة (بدلاً من محاولة إنتاج بنية لا نهائية بالكامل مرة واحدة). يُعد التكرار المشترك مفهومًا مهمًا بشكل خاص في البرمجة الوظيفية (functional programming)، حيث تسمح التكرارية الأساسية والبيانات المشتركة للغات الكلية بالعمل مع هياكل بيانات لا نهائية.
-- ----read---- ----write-ahead---
من جهة ثانية، %% ----read----- --write-ahead-- يقدم مثال خاص آخر حلًا لمشكلة وضع العلامات على أساس العرض أولاً تقوم وظيفة ليبل بزيارة كل عقدة في شجرة ثنائية بطريقة العرض أولاً، واستبدال كل تسمية برقم صحيح، وكل رقم صحيح لاحق يكون أكبر من الرقم السابق بمقدار 1.ويمكن أن تكون الشجرة الثنائية محدودة أو غير محدودة. label :: Tree a b -> Tree Int Int
label t = tn
- bfgen( 0, _, []) :- !. % 0 entries in the queue -- stop and close the list
- bfgen( N, [leaf(_) |P], TS ) :- N2 is N-1, bfgen( N2, P, TS).
- bfgen( N, [branch(_,L,R)|P], [L,R|TS]) :- N2 is N+1, bfgen( N2, P, TS).
ومن جهة أخرى، يستعمل كود Haskell هذا بنية بيانات مرجعية ذاتية، لكنه لا يعتمد بشكل أساسي على التقييم الكسول(lazy evaluation). يمكن ترجمتها بسهولة إلى لغة Prolog، مثلًا،الأمر الأساسي هو القدرة على بناء قائمة (تُستعمل كقائمة انتظار) بطريقة من أعلى إلى أسفل (top-down). ولتحقيق هذه الغاية، يتمتع Prolog بتكرار الذيل modulo cons (أي (أي القوائم المفتوحة).وهو قابل للمحاكاة كذلك في Scheme وسي وما إلى ذلك باستخدام القوائم المرتبطة مع مؤشر ذيل قابل للتغيير كما هو موضح :bftrav( Tree, [Tree|TS]) :- bfgen( 1, [Tree|TS], TS).
وعلى صعيد آخر، -- bfvalues tree = [v | (Branch v _ _) <- bftrav tree] يقوم هذا التعريف بأخذ شجرة وإنتاج قائمة بأشجارها الفرعية (العُقد والأوراق). تخدم هذه القائمة غرضًا مزدوجًا: كقائمة إدخال ونتيجة. ينتج gen len p درجات len للإخراج الخاصة به قبل مؤشر الإدخال الخلفي الخاص به، p، على طول القائمة. يكون هذا منتهيًا إذا وفقط إذا كانت الشجرة الأولية منتهية. يجب تتبع طول قائمة الانتظار بشكل صريح لضمان الإنهاء.
(ln, b) = go l a
label( branch(_,L,R),[I|A], branch(I,Ln,Rn),[I+1|C]) :-
label( leaf(_), [I|A], leaf( I), [I+1|A]).
k, f = 0, 1
k, f = k + 1, f * (k + 1)
وعلى صعيد آخر، return fكما يتضح هنا بسهولة، هذا يعادل عمليًا (فقط عن طريق استبدال return بـ yield الوحيدة هناك) لتقنية وسيطة التراكم (accumulator passing style) في التكرار الذيلي (tail recursion)، والتي فُكت في حلقة صريحة. وبالتالي، يمكن القول إن مفهوم التكرار المشترك (corecursion) هو شرح لتجسيد عمليات الحساب التكرارية من خلال التعريفات التكرارية، حيثما كان ذلك مناسبًا.
while k < n:
yield a
من جهة ثانية، a, b = b, a + b تُقدم المناقشة أدناه الكثير من الأمثلة في Haskell التي تُظهر مفهوم التكرار المشترك (Corecursion). وإذا أُردنا على وجه التقريب نقل هذه التعريفات إلى فئة المجموعات، فإنها ستبقى متزامنة. يتوافق هذا الاستخدام غير الرسمي مع ما هو موجود في الكتب المدرسية حول Haskell. وتجدر الإشارة إلى أن الأمثلة المُستعملة في هذه المقالة تسبق المحاولات الرسمية لتعريف التكرار المشترك وشرح ماهيته.map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )
... yield from output
- ...
- ... result, c1, c2 = tee(deferred_output, 3)
- ... paired = (x + y for x, y in zip(c1, islice(c2, 1, None)))
- ... output = chain([0, 1], paired)
a, b = 0, 1
while True:
تاريخ
وعلى صعيد آخر، إنتاج خوارزميات أكثر كفاءة، مما يسمح في بعض الحالات بتمرير واحد على البيانات بدلاً من الحاجة إلى تمريرات متعددة.
- انظر كذلك
- المحاكاة الثنائية
- الاستحثاث المشترك
- التكرار
- التشوه الشكلي
ومن جهة أخرى، تنفيذ هياكل البيانات الكلاسيكية، مثل القوائم المرتبطة المزدوجة والطوابير، في اللغات الوظيفية.
شملت الدوافع الأصلية وراء تطوير هذه التقنية:
إضافةً إلى ذلك، مع بيرد ، الذي يُرجع الفضل في تطويرها إلى جون هيوز (John Hughes) وفيليب وادلر (Philip Wadler). وقد تم تطوير أشكال أكثر عمومية في عام 1989 بواسطة أليسون .
yield tree.value
new_tree_list.append(tree.right)
علاوةً على ذلك، tree_list = new_tree_listحيث يمكن لاحقًا استدعاء هذا لطباعة قيم عقد الشجرة حسب الترتيب العرضي أولاً :for i in bf(t):
new_tree_list.append(tree.left)
print(i)
where
next (a: t@(b:_)) = (a+b):next tfibs = 0 : 1 : next fibs
... return result
وعلى صعيد آخر، 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181 يمكن تضمين تعريف zipWith مما يؤدي إلى ما يلي:fibs = 0 : 1 : next fibs
>>> print(*islice(fibonacci, 20), sep=', ')
عاملي
من جهة ثانية، مثلًا، لحساب fac(3) (العامل لـ 3)، يتم استدعاء fac(2) و fac(1) و fac(0) بشكل متكرر ("لف" المكدس أو stack winding). عند هذه النقطة، تنتهي التكرارية بـ fac(0) = 1، ثم يتم فك المكدس (stack unwinding) بترتيب عكسي وتُحسب النتائج في طريق العودة على طول مكدس النداء إلى إطار النداء الأولي fac(3) الذي يستعمل نتيجة fac(2) = 2 لحساب النتيجة النهائية على النحو التالي 3 × 2 = 3 × fac(2) =: fac(3) وأخيرًا يُرجع fac(3) = 6. في هذا المثال، تُرجع الدالة قيمة واحدة.
وفي هذا الصدد، لحساب نتيجتها بشكل متكرر على إدخال معين، تستدعي الدالة المتكررة (recursive function) (نسخة من) نفسها باستخدام إدخال مختلف (أصغر بطريقة ما) وتستعمل نتيجة هذه الدعوة لإنشاء نتيجتها. تُؤدي المكالمة المتكررة نفس الشيء، ما لم يتم الوصول إلى الحالة الأساسية (base case). وبالتالي تتطور مجموعة النداءات في هذه العملية.
كذلك، ثم من هذه القيمة الأولية يتم إنشاء قيم العوامل للأعداد المتزايدة 1، 2، 3... كما هو الحال في التعريف المتكرر أعلاه مع "سهم الوقت" معكوسًا، أي عن طريق قراءته للخلف كما يلي:
من جانب آخر، تنتج خوارزمية التكرار المحددة بهذا الشكل سلسلة من جميع العوامل. يمكن تنفيذ ذلك بشكل ملموس كمولد (generator). رمزيًا، مع ملاحظة أن حساب القيمة العاملية التالية يتطلب متابعة كل من n و f (قيمة عاملية سابقة)، يمكن تمثيل ذلك على النحو التالي:
- أو في هاسكل ،def factorial(n: int) -> int:
- """Recursive factorial function."""
- if n == 0:
علاوةً على ذلك، يمكن تفسير عملية فك هذه المكدسة، من خلال تعريف العامل بشكل متكرر، كـمكرر (iterator)، حيث يبدأ المرء بحالة:1=:0!
وفي هذا السياق، أحد الأمثلة الكلاسيكية للتكرار هو حساب العامل ،الذي يتم تعريفه بشكل متكرر بواسطة 0! := 1 وn! := n × (n - 1)! .
return 1
if n == 0:
من جهة ثانية، في لغه بايثون، يمكن تعريف دالة العامل التكرارية على النحو التالي: def factorial(n: int) -> int:
من جهة ثانية، return n * factorial(n - 1)المعنى "بدءًا من" . في كل خطوة، تُحسب القيم التالية على النحو التالي: . هذا يعادل رياضيًا ويكاد يكون مطابقًا للتعريف المتكرر، ولكن +1 يؤكد أن القيم العاملية تُبنى، بالانتقال إلى الأمام من الحالة الأولية، بدلاً من حسابها بعد الرجوع أولاً إلى الوراء، وصولًا إلى الحالة الأساسية، باستخدام التناقص. لا يحتوي الناتج المباشر للدالة التكرارية المشتركة على قيم العامل فحسب، بل تتضمن كذلك لكل قيمة البيانات المساعدة لمؤشرها n في التسلسل، بحيث يمكن تحديد أي نتيجة محددة من بينها جميعًا، حسب الحاجة.
else:
"""Recursive factorial function."""
ومن ناحية أخرى، هناك ارتباط مع الدلالات الإشارية (denotational semantics)، حيث تُبنى دلالات البرامج التكرارية بشكل متكرر بهذه الطريقة.
n, f = 0, 1
while True:
متوالية فيبوناتشي
وعلى صعيد آخر، لأن تسلسل فيبوناتشي عبارة عن علاقة تكرارية من الدرجة 2، فيجب أن تتبع العلاقة التكرارية المشتركة حدين متتاليين، مع المقابلة للتحول للأمام بخطوة واحدة، و المقابلة لحساب المصطلح التالي.حيث يمكن تنفيذ ذلك (باستخدام التعيين الموازي) :def fibonacci_sequence:
وبنفس الطريقة، يمكن تمثيل تسلسل فيبوناتشي على النحو التالي:
new_tree_list = []
if tree is not None:
for tree in tree_list:
تعريف
وفي هذا السياق، يمكن تعريف أنواع البيانات الأولية (initial data types) بأنها أقل نقطة ثابتة (least fixed point) (حتى التماثل الشكلي أو isomorphism) لبعض أنواع المعادلات. ثم يُعطى التماثل بواسطة الجبر الأولي (initial algebra).
وفي هذا الصدد، إذا كان مجال الخطاب (domain of discourse) هو فئة المجموعات والوظائف الكلية (total functions)، فإن أنواع البيانات النهائية (final data types) قد تحتوي على قيم غير محدودة وغير مبنية على أسس متينة، بينما الأنواع الأولية (initial types) لا تحتوي على قيم غير محدودة. من ناحية أخرى، إذا كان مجال الخطاب هو فئة الأوامر الجزئية الكاملة (complete partial orders - CPOs) والوظائف المستمرة (continuous functions)، والتي تتوافق على وجه التقريب مع لغة برمجة Haskell، فإن الأنواع النهائية تتطابق مع الأنواع الأولية، ويُشكل الجبر النهائي (final coalgebra) المقابل والجبر الأولي (initial algebra) تماثلًا شكليًا (isomorphism).
ومن جهة أخرى، على النقيض من ذلك، يمكن تعريف أنواع البيانات الأولية (final data types) (أو الطرفية) بأنها أعظم نقطة تثبيت (greatest fixed point) لمعادلة النوع. ثم يُعطى التماثل بواسطة جبر الفحم النهائي (final coalgebra).
وعلى صعيد آخر، التكرارالأساسي (Corecursion) هو تقنية لتعريف الدوال بشكل متكرر، حيث يكون نطاقها (أو مجالها المشترك) عبارة عن نوع بيانات نهائي (final data type). ويُعد هذا الأسلوب مزدوجًا للطريقة التي يُحدد بها التكرار العادي الدوال بشكل متكرر، والتي يكون نطاقها نوع بيانات أولي.
وفي السياق ذاته، تُقدم المناقشة أدناه الكثير من الأمثلة في Haskell التي تُظهر مفهوم التكرار المشترك (Corecursion). وإذا أردنا على وجه التقريب نقل هذه التعريفات إلى فئة المجموعات، فإنها ستبقى متزامنة. يتوافق هذا الاستخدام غير الرسمي مع ما هو موجود في الكتب المدرسية حول Haskell. وتجدر الإشارة إلى أن الأمثلة المُستعملة في هذه المقالة تسبق المحاولات الرسمية لتعريف التكرار المشترك وشرح ماهيته.
tl (conc a s) = s
وفي السياق ذاته، tl (primes s) = primes (sieve (hd s) (tl s))حيث يتم "الحصول على الأعداد الأولية عن طريق تطبيق عملية الأعداد الأولية على التيار (Enu 2)".باتباع الترميز، يمكن تمثيل تسلسل الأعداد الأولية (مع إضافة 0 إليها) وتدفقات الأعداد التي يتم غربلتها تدريجيًا كمت هو موضح في م يلي :
- (sieve p s) = if div p (hd s) then sieve p (tl s)
- else conc (hd s) (sieve p (tl s))
- hd (primes s) = (hd s)
... def deferred_output:
>>> def fibonacci:
وفي هذا الصدد، أو في هاسكل،(\(p, s@(h:t)) -> (h, sieve h t)) `iterate` (0, [2..]) يناقش المؤلفون كيف أن تعريف sieve ليس مضمونًا دائمًا ليكون منتِجًا، ويمكن أن يتعطل على سبيل المثالحيث اذا تم استدعاؤه بـ [5,10..] باعتباره التدفق الأولي.
من جهة ثانية، وهنا مثال آخر في Haskell.التعريف ينتج قائمة أرقام فيبوناتشي في الزمن الخطي كما هو موضح في التعريف التالي :fibs = 0 : 1 : zipWith (+) fibs (tail fibs) تعتمد هذه القائمة اللانهائية على التقييم الكسول (lazy evaluation)؛ حيث تُحسب العناصر حسب الحاجة فقط، وتُعرض البادئات المحدودة بشكل صريح في الذاكرة. تسمح هذه الميزة بإنهاء الخوارزميات على أجزاء من البيانات المشفرة؛ وتُعتبر مثل هذه التقنيات جزءًا مهمًا من برمجة Haskell.
ومن جهة أخرى، يمكن القيام بذلك في بايثون كذلك كما هو موضح في ما يلي : >>> from itertools import tee, chain, islice
tl (conc a s) = s
- (sieve p s) = if div p (hd s) then sieve p (tl s)
- else conc (hd s) (sieve p (tl s))
- hd (primes s) = (hd s)
- tl (primes s) = primes (sieve (hd s) (tl s))hd (conc a s) = a
gen 0 p = []
gen len (Branch _ l r : p) = l : r : gen (len+1) p
gen len (Leaf _ : p) = gen (len-1) p
where
ومن جهة أخرى، next (a: t@(b:_)) = (a+b):next tيستعمل هذا المثال بنية بيانات مرجعية ذاتية. بينما يستعمل التكرار العادي وظائف مرجعية ذاتية، فإنه لا يستوعب البيانات المرجعية الذاتية. ومع ذلك، هذا ليس ضروريًا لمثال فيبوناتشي، حيث يمكن إعادة كتابته على النحو التالي:fibs = fibgen (0,1)
كذلك، fibgen (x,y) = x : fibgen (y,x+y) يستعمل هذا الأسلوب وظيفة مرجعية ذاتية فقط لبناء النتيجة. إذا تم استخدامه مع منشئ قائمة صارمة (strict list constructor)، فسيكون ذلك مثالاً على التكرار الجامح (chaotic recursion). ومع ذلك، عند استخدامه مع منشئ قائمة غير صارمة (non-strict list constructor)، ينتج هذا التكرار المحمي تدريجياً قائمة محددة إلى ما لا نهاية.
bftrav :: Tree a b -> [Tree a b]
bftrav tree = tree : ts
من جانب آخر، لا يلزم أن ينتج التكرار المشترك (Corecursion) كائنًا لا نهائيًا؛ فطابور التكرار المشترك مثال جيد بشكل خاص على هذه الظاهرة. يؤدي التعريف التالي إلى إنتاج عبور أولي للشجرة الثنائية من أعلى إلى أسفل، في وقت خطي (يتضمن بالفعل التسوية المذكورة أعلاه):data Tree a b = Leaf a
where
- (tn, ns) = go t (1:ns)
- go :: Tree a b -> [Int] -> (Tree Int Int, [Int])
- go (Leaf _ ) (i:a) = (Leaf i , i+1:a)
- go (Branch _ l r) (i:a) = (Branch i ln rn, i+1:c)
- where
عبور الشجرة
في هذا الإطار، بعد انتهاء الأول وقبل الثاني (بالترتيب - in-order traversal)، أو بعد انتهاء العقدة الطفل الثانية (الترتيب اللاحق - post-order traversal) — بافتراض أن الشجرة ثنائية، من أجل تبسيط العرض. تتوافق مجموعة النداءات (لاستدعاءات وظيفة التنقل المتكرر) مع المجموعة التي سيتم تكرارها باستخدام معالجة هيكل LIFO الصريحة المذكورة أعلاه.
"""Breadth-first corecursive generator."""
إضافةً إلى ذلك، وهذا يعني أنه في كل خطوة، تُخرج قائمة القيم في عقد هذا المستوى، ثم يتم الانتقال إلى عقد المستوى التالي. يتطلب إنشاء قيم العقدة فقط من هذا التسلسل ببساطة تجاهل بيانات شجرة الطفل المساعدة، ثم تسوية قائمة القوائم (إذ تُجمع القيم في البداية حسب المستوى/العمق؛ ويؤدي التسوية/إلغاء التجميع إلى الحصول على قائمة خطية مسطحة). وهذا يعادل امتداديًا مواصفات auxbf أعلاه.concatMap fst ( (\(v, ts) -> (rootValues ts, childTrees ts)) `iterate` ([], [fullTree]) )من الجدير بالملاحظة أنه في حالة وجود شجرة لا نهائية، فإن عملية العبور المشترك بالعرض أولاً ستمر عبر جميع العقد، تمامًا كما هو الحال في الشجرة المحدودة. بينما، ستمر عملية العبور المتكرر بالعمق أولاً عبر فرع واحد ولن تتمكن من المرور عبر جميع العقد؛ وفي الواقع، إذا كان العبور بعد الترتيب، كما في هذا المثال (أو بالترتيب)، فلن يزور أي عقد على الإطلاق، لأنه لا يصل إلى ورقة أبدًا.
إضافةً إلى ذلك، يمكن كذلك تنفيذ عملية عبور العرض أولاً (breadth-first traversal) التي تنشئ ناتجها بالترتيب من أعلى إلى أسفل، بشكل متكرر، من خلال البدء في العقدة الجذرية، وإخراج قيمتها.ثم تُعبر الأشجار الفرعية أولاً بالعرض — أي تمرير القائمة الكاملة للأشجار الفرعية إلى الخطوة التالية (وليس شجرة فرعية واحدة، كما في النهج التكراري) — وفي الخطوة التالية تُخرج قيم جميع عقد الجذور الخاصة بها، ثم تمرير الأشجار الفرعية التابعة لها، وهكذا دواليك. في هذه الحالة، تعمل دالة المولد، بل وتسلسل الإخراج نفسه، كطابور (queue).كما هو الحال في المثال العاملي أعلاه، حيث دُفعت المعلومات المساعدة للمؤشر (التي كانت الخطوة الأولى عندها، n) إلى الأمام، فضلًا عن الإخراج الفعلي لـ n!. في هذه الحالة، تُدفع المعلومات المساعدة للأشجار الفرعية المتبقية إلى الأمام، إلى جانب الإخراج الفعلي.
في هذا الإطار، لكلمة "التكرار (recursion)" هنا معنيان. أولاً، تشير إلى الاستدعاءات المتكررة لوظائف عبور الشجرة، مثل dfxyz. والأهم من ذلك، أننا نحتاج إلى التعامل مع كيفية بناء القائمة الناتجة من القيم في هذه العملية. سيؤدي إنشاء مخرجات متكررة من الأسفل إلى الأعلى إلى الانتقال عبر الشجرة من اليمين إلى اليسار. ولتنفيذه فعليًا بالترتيب المقصود من اليسار إلى اليمين، يجب فرض التسلسل من خلال بعض الوسائل الخارجية، أو سيتم تحقيقه تلقائيًا إذا تم بناء الإخراج بطريقة من أعلى إلى أسفل، أي بشكل متكرر.
كذلك، بشكل تكراري، يمكن للمرء أن يتنقل عبر شجرة عن طريق وضع عقدة الجذر الخاصة بها في بنية بيانات. لاحقًا، تُكرر العملية مع بنية البيانات تلك طالما أنها ليست فارغة. في كل خطوة، تُزال العقدة الأولى منها وتُوضع عقد الأطفال الخاصة بالعقدة التي أُزيلت مرة أخرى في بنية البيانات تلك. إذا كانت بنية البيانات عبارة عن مكدس (stack) (LIFO - آخر ما يدخل، أول ما يخرج)، فإن هذا يؤدي إلى عبور العمق أولاً (depth-first traversal). أما إذا كانت بنية البيانات عبارة عن قائمة انتظار (queue) (FIFO - أول ما يدخل، أول ما يخرج)، فإن هذا يؤدي إلى عبور العرض أولاً (breadth-first traversal).
كذلك، في لغة بايثون، يمكن تنفيذ عملية العبور المعتادة ذات العمق الأول (Depth-First Traversal) بترتيب ما بعد العقدة (Post-Order) على النحو التالي:def df(node):
وفي هذا الصدد، print(node.value)يمكن فيما بعد استدعاء ذلك بواسطة df(t) (أو post_order_traversal(t) بناءً على المثال المقدم سابقًا) لطباعة قيم عقد الشجرة حسب ترتيب العمق أولاً.
كذلك، يُعد عبور الشجرة بنهج العمق أولاً (depth-first traversal) مثالًا كلاسيكيًا على التكرار (recursion). في المقابل، من الممكن تنفيذ عملية الانتقال بعرض أول (breadth-first traversal) بشكل طبيعي جدًا من خلال التكرار المشترك (corecursion).
من جانب آخر، يمكن تعريف المولد التكراري العرضي الأول كما يلي : def bf(tree):
- """Post-order depth-first traversal."""
- if node is not None:
- df(node.left)
- df(node.right)
وفي السياق ذاته، يوضح هذا فائدة التكرار المشترك بدلاً من التكرار للتعامل مع هياكل البيانات اللانهائية. ومع ذلك، لا يزال هناك تحذير واحد بالنسبة للأشجار ذات عامل التفرع اللانهائي، والتي تحتاج إلى تشابك (interleaving) أكثر انتباهًا لاستكشاف المساحة بشكل أفضل. انظر التداخل.
وفي هذا السياق، باستخدام التكرار، يتم تنفيذ عبور العمق أولاً لشجرة ببساطة عن طريق عبور كل عقدة فرعية للعقدة الجذرية بشكل متكرر. وبالتالي، لن تتم معالجة الشجرة الفرعية الثانية إلا بعد الانتهاء من الشجرة الفرعية الأولى.تُعالج قيمة العقدة الجذرية بشكل منفصل، سواء قبل عبور الطفل الأول (مما يؤدي إلى عبور الترتيب المسبق - pre-order traversal)، أو
where
ts = gen 1 (tree : ts)
yield f
وفي السياق ذاته، k, f = k + 1, f * (k + 1)يمكن لاحقًا استدعاء هذا لإنتاج العوامل حتى 5!عبر:for f in n_factorials(5):
إضافةً إلى ذلك، print(f)إذا كنا مهتمين فقط بعامل معين، فيمكن أخذ القيمة الأخيرة فقط، أو نستطيع ان نقوم ب دمج الإنتاج والوصول في دالة واحدة،def nth_factorial(n: int):
label( L, A, Ln, B),
- label( R, B, Rn, C).label( Tree, Tn) :- label( Tree, [1|Ns], Tn, Ns).
- label( leaf(_), [I|A], leaf( I), [I+1|A]).
- label( branch(_,L,R),[I|A], branch(I,Ln,Rn),[I+1|C]) :-
مناقشة
من جهة ثانية، وبالتالي، فإن التكرار المشترك (Corecursion) ينشئ بيانات تكميلية (ربما لا نهائية)، في حين يقوم التكرار العادي (Recursion) بتحليل البيانات (المحدودة بالضرورة). قد لا تكون التكرارات العادية قابلة للتطبيق على البيانات المشفرة لأنها قد لا تنتهي. على العكس من ذلك، فإن التكرار المشترك ليس ضروريًا تمامًا إذا كان نوع النتيجة هو البيانات، لأن البيانات يجب أن تكون محدودة.
إضافةً إلى ذلك، في ورقة بحثية بعنوان "البرمجة باستخدام التدفقات في Coq: دراسة حالة: غربال إراتوستينس"، نجد استعراضًا تفصيليًا لكيفية تطبيق مفهوم التدفقات في بيئة Coq الإثباتية لحل مشكلة غربال إراتوستينس، وهي طريقة شائعة لتوليد الأعداد الأولية. يهدف هذا العمل إلى إظهار قدرات Coq في التعامل مع الحسابات ذات التدفقات اللانهائية والتحقق منها رياضيًا.hd (conc a s) = a
ومن ناحية أخرى، تُمثل القاعدة الخاصة بالتكرار المشترك (Corecursion) على البيانات المشفرة القاعدة المزدوجة للتكرار البدائي على البيانات. فبدلاً من "النزول" على الحجة عن طريق مطابقة النمط على المنشئين (الذين استُدعوا سابقًا، في مكان ما، حتى نتلقى بيانات جاهزة ونصل إلى الأجزاء الفرعية المكونة لها، أي "الحقول")، فإننا "نصعد" على النتيجة عن طريق ملء "مدمريها" (أو "المراقبين"، الذين سيُستدعون لاحقًا، في مكان ما — لذلك نحن في الواقع نستدعي منشئًا، وننشئ جزءًا آخر من النتيجة ليتم ملاحظته لاحقًا).
label( L, A, Ln, B),
وفي هذا السياق، يدعم مساعد الإثبات Coq التكرار المشترك والاستقراء باستخدام أمر CoFixpoint.
علاوةً على ذلك، label( R, B, Rn, C). التماثل الشكلي (Catamorphism)، مثل التكشف (unfolding)، هو شكل من أشكال التكرار المشترك (Corecursion)، بنفس الطريقة التي يكون بها التماثل الشكلي (Anamorphism)، مثل الطي (folding)، شكلًا من أشكال التكرار (Recursion).
yield f
ومن ناحية أخرى، n, f = n + 1, f * (n + 1)يؤدي إلى توليد تيار لانهائي من العوامل بالترتيب؛ ويمكن إنتاج جزء محدود منه عن طريق:def n_factorials(n: int):
tree_list = [tree]
while tree_list:
return 1
من جهة ثانية، return n * factorial(n - 1) يمكن استدعاء هذه الدالة، مثلًا، على النحو factorial(5) لحساب قيمة 5!.
else:
إضافةً إلى ذلك، يمكن تعريف المولد التكراري المقابل على النحو التالي:def factorials:
"""Corecursive generator."""
k, f = 0, 1
while k <= n:
أمثلة
من جهة ثانية، يمكن فهم التكرار المشترك (Corecursion) من خلال مقارنته بـالتكرار (Recursion)، وهو أمر أكثر شيوعًا. على الرغم من أن التكرار المشترك يهم في المقام الأول البرمجة الوظيفية، إلا أنه يمكن توضيحه باستخدام االبرمجة الإلزامية (imperative programming)، وهو ما يتم أدناه باستخدام مرفق المولد(generator) في لغة بايثون.
من جهة ثانية، في هذه الأمثلة، تُستعمل المتغيرات المحلية (local variables)، ويُحدد تعيين القيم بشكل حتمي (بشكل مدمر)، على الرغم من أن هذا ليس ضروريًا في التكرار المشترك في البرمجة الوظيفية البحتة. في البرمجة الوظيفية البحتة، بدلاً من التعيين إلى متغيرات محلية، تُشكل هذه القيم المحسوبة تسلسلًا ثابتًا، ويتم الوصول إلى القيم السابقة عن طريق المرجع الذاتي (self-reference) (القيم اللاحقة في التسلسل تُشير إلى القيم السابقة في التسلسل الذي سيتم حسابه). تُعبر الواجبات عن هذا ببساطة في النموذج الأمري وتُحدد صراحةً مكان حدوث العمليات الحسابية، وهو ما يساعد على توضيح العرض.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟