التعاودية المشتركة

في علوم الكمبيوتر، يُعد '''للتكرار'''**المشترك (Corecursion)** نوعًا من العمليات التي تُعتبر **مزدوجة للتكرار (recursion)**. فبينما يعمل التكرار بشكل تحليلي، يبدأ من البيانات الأبعد عن الحالة الأساسية ويُقسّمها إلى بيانات أصغر ويُكرّرها حتى الوصول إلى الحالة الأساسية، تعمل **التكرارية (corecursion)** بشكل اصطناعي، فتبدأ من الحالة الأساسية وتبني عليها، مُنتجةً بيانات متكررة أبعد عن الحالة الأساسية.ببساطة، تستخدم الخوارزميات التكرارية البيانات التي تُنتجها بنفسها، شيئًا فشيئًا، عندما تُصبح متاحة ومطلوبة، لإنتاج المزيد من البيانات. يُشير المفهوم المماثل ولكن المتميز إلى *[[عودية (علم الحاسوب)|*'التكرار التوليدي**]]***(generative recursion)*'، والذي قد يفتقر إلى "اتجاه" محدد متأصل في التكرار المشترك والتكرار المتكرر.

بينما تسمح **التكرارية (recursion)** للبرامج بالعمل على بيانات معقدة بشكل تعسفي، شريطة أن يمكن اختزالها إلى بيانات بسيطة (حالات أساسية)، فإن **التكرارية الأساسية (corecursion)** تتيح للبرامج إنتاج هياكل بيانات معقدة بشكل تعسفي وربما لا نهائية، مثل '''التدفقات'''**(streams)**. هذا ممكن طالما يمكن إنتاج هذه الهياكل من بيانات بسيطة (حالات أساسية) في تسلسل من الخطوات المحدودة.في حين أن التكرار قد لا ينتهي أبدًا، ولا يصل إلى حالة أساسية، يبدأ التكرار المشترك من حالة أساسية، وبالتالي يُنتج خطوات لاحقة بشكل حتمي، على الرغم من أنه قد يستمر إلى أجل غير مسمى (وبالتالي لا ينتهي في ظل التقييم الصارم)، أو قد يستهلك أكثر مما يُنتج فيصبح غير منتج. يمكن تفسير العديد من الوظائف التي تُحلل تقليديًا على أنها متكررة، بطريقة بديلة وربما أكثر طبيعية، على أنها وظائف متكررة مشتركة تنتهي في مرحلة معينة، مثل علاقات التكرار كـ **العامل (factorial)**.

يمكن **للتكرار المشترك (Corecursion)** إنتاج هياكل بيانات محدودة وغير محدودة كنتائج، وقد يستخدم هياكل بيانات مرجعية ذاتية غالبًا ما يُستخدم التكرار المشترك جنبًا إلى جنب مع '''التقييم الكسول''' **(lazy evaluation)**، وذلك لإنتاج مجموعة فرعية محدودة فقط من بنية لا نهائية محتملة (بدلاً من محاولة إنتاج بنية لا نهائية بالكامل مرة واحدة). يُعد التكرار المشترك مفهومًا مهمًا بشكل خاص في **[[برمجة وظيفية|البرمجة الوظيفية]] (functional programming)**، حيث تسمح التكرارية الأساسية والبيانات المشتركة للغات الكلية بالعمل مع هياكل بيانات لا نهائية.

## أمثلة
يمكن فهم **التكرار المشترك (Corecursion)** من خلال مقارنته بـ**التكرار (Recursion)**، وهو أمر أكثر شيوعًا. على الرغم من أن التكرار المشترك يهم في المقام الأول البرمجة الوظيفية، إلا أنه يمكن توضيحه باستخدام **ا<nowiki/>[[برمجة أمرية|البرمجة الإلزامية]] (imperative programming)**، وهو ما يتم أدناه باستخدام مرفق '''المولد'''**(generator)** في لغة بايثون.

في هذه الأمثلة، تُستخدم **المتغيرات المحلية (local variables)**، ويُحدد تعيين القيم بشكل حتمي (بشكل مدمر)، على الرغم من أن هذا ليس ضروريًا في التكرار المشترك في البرمجة الوظيفية البحتة. في البرمجة الوظيفية البحتة، بدلاً من التعيين إلى متغيرات محلية، تُشكل هذه القيم المحسوبة تسلسلًا ثابتًا، ويتم الوصول إلى القيم السابقة عن طريق **المرجع الذاتي (self-reference)** (القيم اللاحقة في التسلسل تُشير إلى القيم السابقة في التسلسل الذي سيتم حسابه). تُعبر الواجبات عن هذا ببساطة في النموذج الأمري وتُحدد صراحةً مكان حدوث العمليات الحسابية، وهو ما يساعد على توضيح العرض.

### عاملي
أحد الأمثلة الكلاسيكية للتكرار هو حساب العامل ،الذي يتم تعريفه بشكل متكرر بواسطة *0! := 1* و*n! := n × (n - 1)!* .

لحساب نتيجتها بشكل متكرر على إدخال معين، تستدعي **الدالة المتكررة (recursive function)** (نسخة من) نفسها باستخدام إدخال مختلف (أصغر بطريقة ما) وتستخدم نتيجة هذه الدعوة لإنشاء نتيجتها. تُؤدي المكالمة المتكررة نفس الشيء، ما لم يتم الوصول إلى **الحالة الأساسية (base case)**. وبالتالي تتطور مجموعة النداءات في هذه العملية.

على سبيل المثال، لحساب `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`. في هذا المثال، تُرجع الدالة قيمة واحدة.

يمكن تفسير عملية فك هذه المكدسة، من خلال تعريف العامل بشكل متكرر، كـ**مكرر (iterator)**، حيث يبدأ المرء بحالة:1=:0!

ثم من هذه القيمة الأولية يتم إنشاء قيم العوامل للأعداد المتزايدة 1، 2، 3... كما هو الحال في التعريف المتكرر أعلاه مع "سهم الوقت" معكوسًا، أي عن طريق قراءته للخلف كما يلي:

تنتج خوارزمية التكرار المحددة بهذا الشكل سلسلة من جميع العوامل. يمكن تنفيذ ذلك بشكل ملموس كمولد **(generator)**. رمزيًا، مع ملاحظة أن حساب القيمة العاملية التالية يتطلب متابعة كل من n و f (قيمة عاملية سابقة)، يمكن تمثيل ذلك على النحو التالي:

: n, f = (0, 1) : (n + 1, f \times (n+1))

أو في هاسكل ،
```python
def factorial(n: int) -> int:
    """Recursive factorial function."""
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
```
المعنى "بدءًا من" n, f = 0, 1. في كل خطوة، تُحسب القيم التالية على النحو التالي: n+1, f \times (n+1). هذا يعادل رياضيًا ويكاد يكون مطابقًا للتعريف المتكرر، ولكن +1 يؤكد أن القيم العاملية تُبنى، بالانتقال إلى الأمام من الحالة الأولية، بدلاً من حسابها بعد الرجوع أولاً إلى الوراء، وصولًا إلى الحالة الأساسية، باستخدام -1 التناقص. لا يحتوي الناتج المباشر للدالة التكرارية المشتركة على قيم العامل n! فحسب، بل تتضمن أيضًا لكل قيمة البيانات المساعدة لمؤشرها n في التسلسل، بحيث يمكن تحديد أي نتيجة محددة من بينها جميعًا، حسب الحاجة.

هناك ارتباط مع  **(denotational semantics)**، حيث تُبنى دلالات البرامج التكرارية بشكل متكرر بهذه الطريقة.

في لغه بايثون، يمكن تعريف دالة العامل التكرارية على النحو التالي:
```haskell
def factorial(n: int) -> int:
    """Recursive factorial function."""
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)
```
يمكن استدعاء هذه الدالة، على سبيل المثال، على النحو `factorial(5)` لحساب قيمة 5!.

يمكن تعريف **المولد التكراري المقابل** على النحو التالي:
```haskell
def factorials():
    """Corecursive generator."""
    n, f = 0, 1
    while True:
        yield f
        n, f = n + 1, f * (n + 1)
```
يؤدي إلى توليد تيار لانهائي من العوامل بالترتيب؛ ويمكن إنتاج جزء محدود منه عن طريق:
```python
def n_factorials(n: int):
    k, f = 0, 1
    while k <= n:
        yield f
        k, f = k + 1, f * (k + 1)
```
يمكن بعد ذلك استدعاء هذا لإنتاج العوامل حتى *5!*عبر:
```python
for f in n_factorials(5):
    print(f)
```
إذا كنا مهتمين فقط بعامل معين، فيمكن أخذ القيمة الأخيرة فقط، أو نستطيع ان نقوم ب دمج الإنتاج والوصول في دالة واحدة،
```pycon
def nth_factorial(n: int):
    k, f = 0, 1
    while k < n:
        k, f = k + 1, f * (k + 1)
    return f
```
كما يتضح هنا بسهولة، هذا يعادل عمليًا (فقط عن طريق استبدال `return` بـ `yield` الوحيدة هناك) لتقنية **وسيطة التراكم (accumulator passing style)** في **التكرار الذيلي (tail recursion)**، والتي فُكت في حلقة صريحة. وبالتالي، يمكن القول إن مفهوم **التكرار المشترك (corecursion)** هو شرح لتجسيد عمليات الحساب التكرارية من خلال التعريفات التكرارية، حيثما كان ذلك مناسبًا.

### متوالية فيبوناتشي
وبنفس الطريقة، يمكن تمثيل تسلسل فيبوناتشي على النحو التالي:

: a, b = (0, 1) : (b, a+b)

لأن تسلسل فيبوناتشي عبارة عن علاقة تكرارية من الدرجة 2، فيجب أن تتبع العلاقة التكرارية المشتركة حدين متتاليين، مع ((b, -)) المقابلة للتحول للأمام بخطوة واحدة، و (-, a+b) المقابلة لحساب المصطلح التالي.حيث يمكن تنفيذ ذلك (باستخدام التعيين الموازي) :
```python
def fibonacci_sequence():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b
```
 تُقدم المناقشة أدناه العديد من الأمثلة في **Haskell** التي تُظهر مفهوم **التكرار المشترك (Corecursion)**. وإذا أُردنا تقريبًا نقل هذه التعريفات إلى فئة المجموعات، فإنها ستبقى متزامنة. يتوافق هذا الاستخدام غير الرسمي مع ما هو موجود في الكتب المدرسية حول Haskell. وتجدر الإشارة إلى أن الأمثلة المُستخدمة في هذه المقالة تسبق المحاولات الرسمية لتعريف التكرار المشترك وشرح ماهيته.
```haskell
map fst ( (\(a,b) -> (b,a+b)) `iterate` (0,1) )
```


### عبور الشجرة
يُعد '''عبور الشجرة''' **بنهج [[البحث المتعمق الأول|العمق أولاً]] (depth-first traversal)** مثالًا كلاسيكيًا على **التكرار (recursion)**. في المقابل، من الممكن تنفيذ عملية **الانتقال [[البحث المتسع الاول|بعرض أول]] (breadth-first traversal)** بشكل طبيعي جدًا من خلال **التكرار المشترك (corecursion)**.

بشكل تكراري، يمكن للمرء أن يتنقل عبر شجرة عن طريق وضع عقدة الجذر الخاصة بها في بنية بيانات. بعد ذلك، تُكرر العملية مع بنية البيانات تلك طالما أنها ليست فارغة. في كل خطوة، تُزال العقدة الأولى منها وتُوضع عقد الأطفال الخاصة بالعقدة التي أُزيلت مرة أخرى في بنية البيانات تلك. إذا كانت بنية البيانات عبارة عن '''مكدس''' **(stack)** (LIFO - آخر ما يدخل، أول ما يخرج)، فإن هذا يؤدي إلى **عبور العمق أولاً (depth-first traversal)**. أما إذا كانت بنية البيانات عبارة عن '''قائمة انتظار''' **(queue)** (FIFO - أول ما يدخل، أول ما يخرج)، فإن هذا يؤدي إلى **عبور العرض أولاً (breadth-first traversal)**.

: \text{trav}_\text{nn}(t) = \text{aux}_\text{nn}([t])

: \text{aux}_\text{df}([t,\ ...ts]) = \text{val}(t) ;\ \text{aux}_\text{df}([\ ...\text{children}(t),\ ...ts\ ])

: \text{aux}_\text{bf}([t,\ ...ts]) = \text{val}(t) ;\ \text{aux}_\text{bf}([\ ...ts,\ ...\text{children}(t)\ ])

باستخدام التكرار، يتم تنفيذ عبور العمق أولاً لشجرة ببساطة عن طريق عبور كل عقدة فرعية للعقدة الجذرية بشكل متكرر. وبالتالي، لن تتم معالجة الشجرة الفرعية الثانية إلا بعد الانتهاء من الشجرة الفرعية الأولى.تُعالج قيمة العقدة الجذرية بشكل منفصل، سواء قبل عبور الطفل الأول (مما يؤدي إلى **عبور الترتيب المسبق - pre-order traversal**)، أو

بعد انتهاء الأول وقبل الثاني (بالترتيب - **in-order traversal**)، أو بعد انتهاء العقدة الطفل الثانية (الترتيب اللاحق - **post-order traversal**) — بافتراض أن الشجرة ثنائية، من أجل تبسيط العرض. تتوافق مجموعة النداءات (لاستدعاءات وظيفة التنقل المتكرر) مع المجموعة التي سيتم تكرارها باستخدام معالجة هيكل LIFO الصريحة المذكورة أعلاه.

: v, ts = ([], [\text{FullTree}]) : (\text{RootValues}(ts), \text{ChildTrees}(ts))

: p, s = (0, [2..]) : (hd(s), sieve(hd(s),tl(s)))

: \text{df}_\text{post}(t) = [\ ...\text{df}_\text{post}(\text{left}(t)),\ ...\text{df}_\text{post}(\text{right}(t)),\ \text{val}(t)\ ]

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

يمكن أيضًا تنفيذ عملية **عبور العرض أولاً (breadth-first traversal)** التي تنشئ ناتجها بالترتيب من أعلى إلى أسفل، بشكل متكرر، من خلال البدء في العقدة الجذرية، وإخراج قيمتها.ثم تُعبر الأشجار الفرعية أولاً بالعرض — أي تمرير القائمة الكاملة للأشجار الفرعية إلى الخطوة التالية (وليس شجرة فرعية واحدة، كما في النهج التكراري) — وفي الخطوة التالية تُخرج قيم جميع عقد الجذور الخاصة بها، ثم تمرير الأشجار الفرعية التابعة لها، وهكذا دواليك. في هذه الحالة، تعمل دالة المولد، بل وتسلسل الإخراج نفسه، **كطابور (queue)**.كما هو الحال في المثال العاملي أعلاه، حيث دُفعت المعلومات المساعدة للمؤشر (التي كانت الخطوة الأولى عندها، `n`) إلى الأمام، بالإضافة إلى الإخراج الفعلي لـ `n!`. في هذه الحالة، تُدفع المعلومات المساعدة للأشجار الفرعية المتبقية إلى الأمام، بالإضافة إلى الإخراج الفعلي.

: v, ts = ([], [\text{FullTree}]) : (\text{RootValues}(ts), \text{ChildTrees}(ts))

وهذا يعني أنه في كل خطوة، تُخرج **قائمة القيم** في عقد هذا المستوى، ثم يتم الانتقال إلى عقد المستوى التالي. يتطلب إنشاء قيم العقدة فقط من هذا التسلسل ببساطة **تجاهل بيانات شجرة الطفل المساعدة**، ثم **تسوية قائمة القوائم** (إذ تُجمع القيم في البداية حسب المستوى/العمق؛ ويؤدي التسوية/إلغاء التجميع إلى الحصول على قائمة خطية مسطحة). وهذا يعادل امتداديًا مواصفات auxbf أعلاه.
```haskell
concatMap fst ( (\(v, ts) -> (rootValues ts, childTrees ts)) `iterate` ([], [fullTree]) )
```
من الجدير بالملاحظة أنه في حالة وجود **شجرة لا نهائية**، فإن عملية **العبور المشترك بالعرض أولاً** ستمر عبر جميع العقد، تمامًا كما هو الحال في الشجرة المحدودة. بينما، ستمر عملية **العبور المتكرر بالعمق أولاً** عبر فرع واحد ولن تتمكن من المرور عبر جميع العقد؛ وفي الواقع، إذا كان العبور بعد الترتيب، كما في هذا المثال (أو بالترتيب)، فلن يزور أي عقد على الإطلاق، لأنه لا يصل إلى ورقة أبدًا.

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

في لغة بايثون، يمكن تنفيذ عملية العبور المعتادة ذات العمق الأول (Depth-First Traversal) بترتيب ما بعد العقدة (Post-Order) على النحو التالي:
```prolog
def df(node):
    """Post-order depth-first traversal."""
    if node is not None:
        df(node.left)
        df(node.right)
        print(node.value)
```
يمكن بعد ذلك استدعاء ذلك بواسطة `df(t)` (أو `post_order_traversal(t)` بناءً على المثال المقدم سابقًا) لطباعة قيم عقد الشجرة حسب ترتيب العمق أولاً.

يمكن تعريف المولد التكراري العرضي الأول كما يلي : 
```haskell
def bf(tree):
    """Breadth-first corecursive generator."""
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list
```
حيث يمكن بعد ذلك استدعاء هذا لطباعة قيم عقد الشجرة حسب الترتيب العرضي أولاً :
```prolog
for i in bf(t):
    print(i)
```


## تعريف

يمكن تعريف **أنواع البيانات الأولية (initial data types)** بأنها **أقل نقطة ثابتة (least fixed point)** (حتى التماثل الشكلي أو isomorphism) لبعض أنواع المعادلات. ثم يُعطى التماثل بواسطة **الجبر الأولي (initial algebra)**.

على النقيض من ذلك، يمكن تعريف  **(final data types)** (أو الطرفية) بأنها **أعظم نقطة تثبيت (greatest fixed point)** لمعادلة النوع. ثم يُعطى التماثل بواسطة جبر الفحم **النهائي (final coalgebra)**.

إذا كان **مجال الخطاب (domain of discourse)** هو فئة المجموعات والوظائف الكلية **(total functions)**، فإن **أنواع البيانات النهائية (final data types)** قد تحتوي على قيم غير محدودة وغير مبنية على أسس متينة، بينما **الأنواع الأولية (initial types)** لا تحتوي على قيم غير محدودة.من ناحية أخرى، إذا كان مجال الخطاب هو فئة **الأوامر الجزئية الكاملة (complete partial orders - CPOs)** و**الوظائف المستمرة (continuous functions)**، والتي تتوافق تقريبًا مع لغة برمجة **Haskell**، فإن **الأنواع النهائية تتطابق مع الأنواع الأولية**، ويُشكل **الجبر النهائي (final coalgebra)** المقابل و**الجبر الأولي (initial algebra)** **تماثلًا شكليًا (isomorphism)**.

'''التكرار'''**الأساسي (Corecursion)** هو تقنية لتعريف الدوال بشكل متكرر، حيث يكون **نطاقها (أو مجالها المشترك)** عبارة عن **نوع بيانات نهائي (final data type)**. ويُعد هذا الأسلوب مزدوجًا للطريقة التي يُحدد بها التكرار العادي الدوال بشكل متكرر، والتي يكون نطاقها نوع بيانات أولي.

تُقدم المناقشة أدناه العديد من الأمثلة في **Haskell** التي تُظهر مفهوم **التكرار المشترك (Corecursion)**. وإذا أردنا تقريبًا نقل هذه التعريفات إلى فئة المجموعات، فإنها ستبقى متزامنة. يتوافق هذا الاستخدام غير الرسمي مع ما هو موجود في الكتب المدرسية حول Haskell. وتجدر الإشارة إلى أن الأمثلة المُستخدمة في هذه المقالة تسبق المحاولات الرسمية لتعريف التكرار المشترك وشرح ماهيته.

## مناقشة

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

وبالتالي، فإن **التكرار المشترك (Corecursion)** ينشئ بيانات تكميلية (ربما لا نهائية)، في حين يقوم **التكرار العادي (Recursion)** بتحليل البيانات (المحدودة بالضرورة). قد لا تكون التكرارات العادية قابلة للتطبيق على البيانات المشفرة لأنها قد لا تنتهي. على العكس من ذلك، فإن التكرار المشترك ليس ضروريًا تمامًا إذا كان نوع النتيجة هو البيانات، لأن البيانات يجب أن تكون محدودة.

في ورقة بحثية بعنوان "البرمجة باستخدام التدفقات في Coq: دراسة حالة: غربال إراتوستينس"، نجد استعراضًا تفصيليًا لكيفية تطبيق مفهوم التدفقات في بيئة Coq الإثباتية لحل مشكلة غربال إراتوستينس، وهي طريقة شائعة لتوليد الأعداد الأولية. يهدف هذا العمل إلى إظهار قدرات Coq في التعامل مع الحسابات ذات التدفقات اللانهائية والتحقق منها رياضيًا. 
```haskell
hd (conc a s) = a               
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))
```

```haskell
hd (conc a s) = a               
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))
```
حيث يتم "الحصول على الأعداد الأولية عن طريق تطبيق عملية الأعداد الأولية على التيار (Enu 2)".باتباع الترميز، يمكن تمثيل تسلسل الأعداد الأولية (مع إضافة 0 إليها) وتدفقات الأعداد التي يتم غربلتها تدريجيًا كمت هو موضح في م يلي :

: p, s = (0, [2..]) : (hd(s), sieve(hd(s),tl(s)))

أو في هاسكل،
```haskell
(\(p, s@(h:t)) -> (h, sieve h t)) `iterate` (0, [2..])
```
يناقش المؤلفون كيف أن تعريف **sieve** ليس مضمونًا دائمًا ليكون منتِجًا، ويمكن أن يتعطل على سبيل المثالحيث اذا تم استدعاؤه بـ `[5,10..]` باعتباره التدفق الأولي.

وهنا مثال آخر في Haskell.التعريف ينتج قائمة أرقام فيبوناتشي في الزمن الخطي كما هو موضح في التعريف التالي :
```haskell
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
```
تعتمد هذه القائمة اللانهائية على **التقييم الكسول (lazy evaluation)**؛ حيث تُحسب العناصر حسب الحاجة فقط، وتُعرض البادئات المحدودة بشكل صريح في الذاكرة. تسمح هذه الميزة بإنهاء الخوارزميات على أجزاء من البيانات المشفرة؛ وتُعتبر مثل هذه التقنيات جزءًا مهمًا من برمجة **Haskell**.

يمكن القيام بذلك في بايثون أيضًا كما هو موضح في ما يلي : 
```pycon
>>> from itertools import tee, chain, islice
>>> def fibonacci():
...     def deferred_output():
...         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)
...     return result
>>> print(*islice(fibonacci(), 20), sep=', ')
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181
```
يمكن تضمين تعريف `zipWith` مما يؤدي إلى ما يلي:
```haskell
fibs = 0 : 1 : next fibs
  where
    next (a: t@(b:_)) = (a+b):next tfibs = 0 : 1 : next fibs
  where
    next (a: t@(b:_)) = (a+b):next t
```
يستخدم هذا المثال بنية بيانات مرجعية ذاتية. بينما يستخدم التكرار العادي وظائف مرجعية ذاتية، فإنه لا يستوعب البيانات المرجعية الذاتية. ومع ذلك، هذا ليس ضروريًا لمثال فيبوناتشي، حيث يمكن إعادة كتابته على النحو التالي:
```haskell
fibs = fibgen (0,1)
fibgen (x,y) = x : fibgen (y,x+y)
```
 يستخدم هذا الأسلوب وظيفة مرجعية ذاتية فقط لبناء النتيجة. إذا تم استخدامه مع منشئ قائمة **صارمة (strict list constructor)**، فسيكون ذلك مثالاً على **التكرار الجامح (chaotic recursion)**. ومع ذلك، عند استخدامه مع منشئ قائمة **غير صارمة (non-strict list constructor)**، ينتج هذا التكرار المحمي تدريجياً قائمة محددة إلى ما لا نهاية.

لا يلزم أن ينتج **التكرار المشترك (Corecursion)** كائنًا لا نهائيًا؛ فطابور التكرار المشترك مثال جيد بشكل خاص على هذه الظاهرة. يؤدي التعريف التالي إلى إنتاج عبور أولي للشجرة الثنائية من أعلى إلى أسفل، في وقت خطي (يتضمن بالفعل التسوية المذكورة أعلاه):
```haskell
data Tree a b = Leaf a
              | Branch b (Tree a b) (Tree a b)

bftrav :: Tree a b -> [Tree a b]
bftrav tree = tree : ts
  where
  ts = gen 1 (tree : ts)

  gen  0   p                 =         []           
  gen len (Leaf   _     : p) =         gen (len-1) p
  gen len (Branch _ l r : p) = l : r : gen (len+1) p
  --       ----read----        ----write-ahead---

-- bfvalues tree = [v | (Branch v _ _) <- bftrav tree]
```
 يقوم هذا التعريف بأخذ شجرة وإنتاج قائمة بأشجارها الفرعية (العُقد والأوراق). تخدم هذه القائمة غرضًا مزدوجًا: كقائمة إدخال ونتيجة. ينتج `gen len p` درجات `len` للإخراج الخاصة به قبل مؤشر الإدخال الخلفي الخاص به، `p`، على طول القائمة. يكون هذا منتهيًا إذا وفقط إذا كانت الشجرة الأولية منتهية. يجب تتبع طول قائمة الانتظار بشكل صريح لضمان الإنهاء.

يستخدم كود Haskell هذا بنية بيانات مرجعية ذاتية، لكنه لا يعتمد بشكل أساسي على التقييم الكسول(lazy evaluation). يمكن ترجمتها بسهولة إلى لغة Prolog، على سبيل المثال،الأمر الأساسي هو القدرة على بناء قائمة (تُستخدم كقائمة انتظار) بطريقة من أعلى إلى أسفل (top-down). ولتحقيق هذه الغاية، يتمتع Prolog بتكرار الذيل modulo cons (أي (أي القوائم المفتوحة).وهو قابل للمحاكاة أيضًا في Scheme وسي وما إلى ذلك باستخدام القوائم المرتبطة مع مؤشر ذيل قابل للتغيير كما هو موضح :
```prolog
bftrav( Tree,  [Tree|TS]) :- bfgen( 1, [Tree|TS],   TS).

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).
%%         ----read-----      --write-ahead--
```
 يقدم مثال خاص آخر حلًا لمشكلة وضع العلامات على أساس **العرض أولاً** تقوم وظيفة ليبل بزيارة كل عقدة في شجرة ثنائية بطريقة العرض أولاً، واستبدال كل تسمية برقم صحيح، وكل رقم صحيح لاحق يكون أكبر من الرقم السابق بمقدار 1.ويمكن أن تكون الشجرة الثنائية محدودة أو غير محدودة. 
```haskell
label :: Tree a b -> Tree Int Int 
label t = tn
  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
       (ln, b) = go l a
       (rn, c) = go r b
```
أو في Prolog، للمقارنة،
```prolog
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]) :-
  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]) :-
  label( L, A,   Ln, B),  
  label( R, B,   Rn, C).
```
  **(Catamorphism)**، مثل التكشف (unfolding)، هو شكل من أشكال **التكرار المشترك (Corecursion)**، بنفس الطريقة التي يكون بها  **(Anamorphism)**، مثل الطي (folding)، شكلًا من أشكال **التكرار (Recursion)**.

يدعم مساعد الإثبات **Coq** التكرار المشترك والاستقراء باستخدام أمر `CoFixpoint`.

## تاريخ
مع **بيرد ()**، الذي يُرجع الفضل في تطويرها إلى **جون هيوز (John Hughes)** و**فيليب وادلر (Philip Wadler)**. وقد تم تطوير أشكال أكثر عمومية في عام 1989 بواسطة **أليسون ()**.

شملت الدوافع الأصلية وراء تطوير هذه التقنية:

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

## انظر أيضا

* المحاكاة الثنائية
* الاستحثاث المشترك
* التكرار
* التشوه الشكلي

## مراجع

تصنيف:عودية
تصنيف:نظرية الفئة
تصنيف:برمجة وظيفية
تصنيف:الإشارة إلى الذات
تصنيف:علم الحاسوب النظري
تصنيف:صفحات بترجمات غير مراجعة