السحّابات

9. السحّابات (zippers)

نقدّم في هذا الفصل تقنية عامة لاجتياز بنى المعطيات. لا تعتمد هذه التقنية على ترتيب اجتياز (traversal) محدّد، وتتيح إمكانية إجراء تعديلات موضعية (إدراج، حذف، وما إلى ذلك). وهي تُعرف باسم السحّاب (zipper). نعرضها هنا في سياق القوائم والأشجار، لكن يمكن تكييفها مع العديد من بنى المعطيات الأخرى.

9.1 السحّابات على القوائم

لنفترض أننا نرغب في «التنقّل» داخل قائمة من النمط ’alist، أي الانتقال من عنصر إلى عنصر مع إجراء تعديلات عرضية أحياناً. الصورة التي تتبادر إلى الذهن هنا هي صورة مؤشّر في محرّر نصوص، وفعل مفاتيح لوحة المفاتيح المستخدمة للتحرّك والإدراج والحذف وغير ذلك.

لنأخذ قائمة تحتوي على سبعة عناصر، مع وضع المؤشّر بعد العنصر الثالث، كما هو مبيّن في الشكل 9.1.

الشكل 9.1: مؤشّر على قائمة.

نمثّل هذه الحالة بقائمتين، تحتوي إحداهما على العناصر الواقعة إلى يسار المؤشّر، والأخرى على العناصر الواقعة إلى اليمين. ومن المناسب تمثيل القائمة الأولى بترتيب معكوس، بحيث يصبح العنصر الواقع مباشرة إلى يسار المؤشّر سهل الوصول. يوضّح الشكل 9.2 هذا التمثيل على المثال السابق.

الشكل 9.2: سحّاب على قائمة.

تُسمّى هذه البنية المكوّنة من قائمتين سحّاباً (zipper). ونعرّفها باستخدام النمط التالي:

  type ’a zipper = { left: ’a list; right: ’a list; }

لبناء سحّاب كهذا انطلاقاً من قائمة l، مع وضع المؤشّر في أقصى اليسار، نهيّئ القائمة اليسرى إلى [] والقائمة اليمنى إلى l.

  let of_list l =
    { left = []; right = l }

لننتقل الآن إلى عمليات التنقّل والتعديل في السحّاب.

عمليات التنقّل

تتضمّن عملية التنقّل الأولى تحريك المؤشّر إلى اليمين. وهذا لا يكون ممكناً إلا إذا كانت القائمة اليمنى تحتوي على عنصر واحد على الأقل. في هذه الحالة ننقل العنصر الأول من هذه القائمة إلى رأس القائمة اليسرى.

  let move_right z = match z.right with
    | [] -> invalid_arg "move_right"
    | x :: r -> { left = x :: z.left; right = r }

يُرجع تطبيق الدالة move_right على مثال الشكل 9.2 السحّاب المبيّن في الشكل 9.3.

الشكل 9.3: السحّاب بعد الانتقال إلى اليمين.

وبالمثل نكتب دالة move_left لتحريك المؤشّر إلى اليسار (انظر البرنامج 73، الصفحة التالية).

لتحويل سحّاب z إلى قائمة، يكفي وصل القائمتين z.left و z.right مع عكس الأولى. وهذا بالضبط ما تفعله الدالة List.rev_append.

  let to_list z =
    List.rev_append z.left z.right

وبشكل مكافئ، كان بإمكاننا تحريك المؤشّر إلى أقصى اليسار ثم استرجاع القائمة اليمنى.

عمليات التعديل

لإدراج عنصر عند موضع المؤشّر، يكفي وضع ذلك العنصر في رأس إحدى القائمتين. وإذا أدرجناه في رأس القائمة اليسرى، فسيكون المؤشّر إلى يمين العنصر الجديد (كما في حالة محرّر نصوص).

  let insert z x =
    { z with left = x :: z.left }

أما إذا أردنا بدلاً من ذلك إبقاء المؤشّر إلى يسار العنصر المُدرج، فيكفي استبدال left بـ right في الشيفرة أعلاه.

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

  let delete_left z = match z.left with
    | [] -> invalid_arg "delete_left"
    | _ :: l -> { z with left = l }

وبالمثل يمكننا كتابة عملية delete_right تحذف العنصر الواقع مباشرة إلى يمين المؤشّر.

9.2 السحّابات على الأشجار

تنطبق تقنية السحّاب أيضاً على بنى معطيات أخرى، مثل الأشجار. خُذ مثلاً حالة الأشجار الثنائية متعدّدة الأشكال المعرّفة بالنمط التالي:

  type ’a tree = E | N of ’a tree * ’a * ’a tree

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

خُذ الشجرة في الشكل 9.4، حيث نضع المؤشّر على العقدة التي تحتوي على 5. يحتوي السحّاب على موضع العقدة المعنية والشجرة الجزئية عند ذلك الموضع. ويمثّل الأول المسار من الجذر إلى العقدة، أي متتالية الحركات التي تحدّد عند كل خطوة ما إذا كنا ننزل على طول الشجرة الجزئية اليسرى أو اليمنى. فعلى سبيل المثال، المسار للوصول إلى العقدة 5 هو المتتالية [left; right].

الشكل 9.4: مؤشّر على شجرة.

نُعرّف النمط التالي لتمثيل مثل هذه المسارات. يمثّل الباني Top المسار الفارغ، أي موضع جذر الشجرة. ويدلّ البانيان Left و Right على حركة على طول الشجرتين الجزئيتين اليسرى أو اليمنى على التوالي.

  type ’a path =
    | Top
    | Left of ’a path * ’a * ’a tree
    | Right of ’a tree * ’a * ’a path

نحتفظ عند كل حركة بالشجرة الجزئية التي لم ننزل عبرها. وهذا ضروري كي نتمكّن من الصعود مجدّداً في الشجرة. ويُعرَّف سحّاب الأشجار الثنائية حينئذٍ بالنمط التالي:

  type ’a zipper = { path : ’a path; tree : ’a tree }

يحتوي الحقل tree على الشجرة الجزئية عند المؤشّر. ويحتوي الحقل path على المسار المؤدّي إلى هذه الشجرة الجزئية. وكما في حالة السحّاب على القوائم، حيث اخترنا تمثيل القائمة اليسرى بترتيب معكوس، نختار هنا تخزين مسار العقدة نحو الجذر، بدلاً من من الجذر. ويعطي الشكل 9.5 السحّاب للمثال السابق.

الشكل 9.5: سحّاب على شجرة.

الباني الأول للمسار هو Right لأن المؤشّر يعيّن شجرة جزئية يمنى. والخطوة التالية في المسار هي Left لأن العقدة 3 هي جذر شجرة جزئية يسرى. وأخيراً يبلغ المسار جذر الشجرة، 8.

يُبنى السحّاب مع المؤشّر عند جذر الشجرة باستخدام المسار الفارغ.

  let of_tree t = { path = Top; tree = t }

لنكتب الآن دوال التنقّل. نبدأ بدالة down_left للنزول على طول الشجرة الجزئية اليسرى. ولهذا نفحص شكل الشجرة عند المؤشّر. ونفشل إذا كانت فارغة.

  let down_left z = match z.tree with
    | E -> invalid_arg "down_left"

وإلا نُرجع السحّاب الذي تكون فيه الشجرة الجزئية عند المؤشّر هي الشجرة الجزئية اليسرى، ويمتدّ المسار بالباني Left للدلالة على أننا نزلنا عبر اليسار.

    | N (l, x, r) -> { path = Left (z.path, x, r); tree = l }

تُحفظ العقدة x وشجرتها الجزئية اليمنى r في المسار، كوسيطين للباني Left. وبالمثل نكتب دالة down_right تنزل عبر الشجرة الجزئية اليمنى.

تفحص دالة الصعود في الشجرة المسار الحالي. ونفشل إذا كان المسار فارغاً.

  let up z = match z.path with
    | Top ->
        invalid_arg "up"

وإلا وجب علينا إعادة بناء عقدة الشجرة الواقعة فوق المؤشّر. ولهذا

نستخدم المعلومات الواردة في المسار وكذلك الشجرة الجزئية الموجودة في الحقل tree. فإذا نزلنا عبر الشجرة الجزئية اليسرى، يكون المسار على الشكل Left(p,x,r)، وتكون العقدة المُعاد بناؤها ذات z.tree كشجرة جزئية يسرى لها، وx كجذر لها، وr كشجرة جزئية يمنى لها.

    | Left (p, x, r) ->
        { path = p; tree = N (z.tree, x, r) }

وإذا نزلنا عبر الشجرة الجزئية اليمنى، نتابع بشكل متناظر.

    | Right (l, x, p) ->
        { path = p; tree = N (l, x, z.tree) }

تعيد الدالة التي تعيد بناء الشجرة بأكملها من سحّاب معطى تحريك المؤشّر صعوداً في الشجرة حتى يبلغ القمة. ونتوقف عندما يصبح المسار Top ونُرجع الشجرة الموجودة في الحقل tree.

  let rec to_tree z =
    if z.path = Top then z.tree else to_tree (up z)

تُعطى الشيفرة الكاملة للسحّاب على الأشجار الثنائية في البرنامج 74.

ملاحظة: قد تتساءل عن أوجه الشبه بين السحّابات على القوائم وتلك على الأشجار. ففي الواقع، يبدو السحّاب على القوائم بنية متناظرة تماماً، إذ إن حقليه left و right من النمط نفسه. غير أنك قد تفهمه أيضاً على أنه غير متناظر، إذ يؤدي left الدور نفسه الذي يؤدّيه path، ويؤدّي right دور tree. وبناءً على ذلك، كان بإمكاننا تعريف النمط التالي لتمثيل موضع في قائمة:

  type ’a path = Top | Right of ’a * ’a path

ولأن هذا النمط مطابق بوضوح للنمط ’alist، لم نرَ أنه يجدر بنا تعريف نمط جديد. وهكذا تجسّد السحّابات على القوائم والأشجار الفكرة ذاتها بعينها.

تطبيق: مقارنة شجرتين ثنائيتين للبحث

في الفصل 5، عرضنا أشجار البحث الثنائية، التي يمكن أن تمثّل مجموعات من العناصر مزوّدة بترتيب كلي. فإذا أردنا بناء مجموعة من المجموعات، كان من الضروري أن نزوّد أشجار البحث الثنائية نفسها بترتيب كلي.

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

قد تختلفان بسرعة، وفي هذه الحالة نكون قد بنينا القائمتين عبثاً.

يُفضَّل حل أكثر كفاءة يعمل مباشرة على الشجرتين. غير أن هذا ليس مباشراً لأن شجرتي بحث ثنائيتين يمكن أن تحتويان على العناصر نفسها من دون أن يكون لهما البنية نفسها، كما هو مبيّن في الشكل 9.6. ويتمثّل أحد الحلول في استخدام بنية السحّاب لتنفيذ اجتياز وُسْطي متزامن للشجرتين.

الشكل 9.6: شجرتان ثنائيتان للبحث تحتويان على العناصر نفسها.

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

وبشكل ملموس، نكتب دالة leftmost بتمرير سحّاب إليها كمراكم. فإذا كانت الشجرة فارغة، نُرجع السحّاب الممرَّر كوسيط:

  let rec leftmost z = function
    | E -> z

وإلا ننزل عبر الشجرة الجزئية اليسرى، مع تجميع العقدة المزارة في السحّاب.

    | N (l, x, r) -> leftmost (Left (z, x, r)) l

وإذا أخذنا الشجرتين في الشكل 9.6، t1 و t2، فإن السحّابين الناتجين عن leftmostTopt1 و leftmostTopt2 يكونان على الشكل التالي:

  leftmost Top t1 = Left (Left (..., 3, ...), 1, ...)
  leftmost Top t2 = Left (Left (..., 4, ...), 1, ...)

يصور الشكل 9.7 السحّابين. ويمكننا التحقق من أن كليهما يبدأ بالقيمة الصغرى، وهي 1.

الشكل 9.7: السحّابان للشجرتين في الشكل 9.6.

التالي، علينا كتابة دالة compare لتنفيذ المقارنة الفعلية. تأخذ هذه الدالة كوسيطين سحّابين ودالة cmp لمقارنة العناصر. فإذا كان السحّابان Top، انتهت المقارنة، ونُرجع 0 للدلالة على التساوي.

  let rec compare cmp z1 z2 = match z1, z2 with
    | Top, Top ->
        0

وإذا كان السحّابان على الشكل Left، نقارن العنصرين اللذين يعيّنانهما باستخدام الدالة cmp. فإذا اختلفا، انتهت المقارنة، وتُرجع النتيجة التي تعطيها cmp.

    | Left (z1, x1, r1), Left (z2, x2, r2) ->
        let c = cmp x1 x2 in
        if c <> 0 then c

أما إذا تساويا، وجب أن تستمر المقارنة. فنبحث عن العنصرين التاليين، باستدعاء leftmost على الشجرتين الجزئيتين اليمنيين، r1 و r2. ثم نستدعي compare عودياً.

        else compare cmp (leftmost z1 r1) (leftmost z2 r2)

وإذا كان أحد السحّابين يساوي Top والآخر Left، فهذا يعني أن أحد الاجتيازين بلغ النهاية دون الآخر. ولذلك نُرجع -1 أو 1، حسب الحالة.

    | Top, Left _ ->
        -1
    | Left _, Top ->
        1

وأخيراً، بحكم البناء، لا يمكن أن تحدث حالة سحّاب على الشكل Right. ونتخلّص منها كما يلي:

    | Right _, _ | _, Right _ ->
        assert false

ولحلّ المشكلة الأولية المتمثّلة في كيفية مقارنة شجرتين t1 و t2، يكفي أن نبني السحّابين بالدالة leftmost، ثم نقارنهما باستخدام الدالة compare.

  let compare_tree cmp t1 t2 =
    compare cmp (leftmost Top t1) (leftmost Top t2)

تُعطى الشيفرة الكاملة في البرنامج 75. لاحظ أن الدالتين leftmost و compare عوديتان ذيليّتان.

9.3 المؤشّرات

عند مناقشة مشكلة مقارنة الأشجار الثنائية، رأينا أهمية اجتياز بنية معطيات خطوة بخطوة. وتختلف طريقة الاجتياز هذه عن طريقة المُكرِّرات ذات الرتبة الأعلى مثل iter و fold، التي لم يكن بوسعنا أن نحلّ بها تلك المشكلة.

وبشكل عام، بالنظر إلى بنية معطيات اعتباطية من النمط ’at، نرغب في واجهة مؤشّر (cursor) لاجتياز عناصرها واحداً واحداً. وتُعطى مثل هذه الواجهة في البرنامج 76.

تحتوي الواجهة على نمط مجرّد متعدّد الأشكال، ’aenum، للمؤشّر، حيث المتغيّر ’a هو نمط العناصر. وتُرجع الدالة start مؤشّراً جديداً. وتُرجع الدالة step العنصر الحالي والمؤشّر المقابل للعنصر التالي، أو ترفع الاستثناء Exit إذا اكتمل التكرار.

تُعرّف هذه الواجهة مؤشّرات دائمة، بمعنى أن المؤشّر الممرَّر كمدخل إلى الدالة step لا يُعدَّل. وهكذا يمكننا إعادة استخدام المؤشّر، مثلاً في خوارزمية تستخدم الرجوع بالآثار (backtracking). وهناك احتمال آخر هو المؤشّرات الأمرية، حيث تُرجع الدالة step العنصر الحالي فقط وتتقدّم بالمؤشّر إلى العنصر التالي بأثر جانبي (انظر التمرين 9.12).

سننفّذ الآن مؤشّرات دائمة على القوائم والأشجار.

المؤشّرات على القوائم

السحّاب على القوائم هو بحدّ ذاته مؤشّر مناسب. غير أنه مع ذلك معقّد بلا داعٍ لأننا لا نحتاج إلى تتبّع العناصر الواقعة إلى يسار المؤشّر. وبعبارة أخرى، ليس مؤشّر القوائم سوى القائمة اليمنى، أي:

  type ’a enum = ’a list

تختزل الدالة start إلى دالة الهوية. وترفع الدالة step الاستثناء Exit إذا كان المؤشّر فارغاً. وإلا فإنها تُرجع رأس القائمة وبقية القائمة كمؤشّر جديد.

  let step = function
    | [] -> raise Exit
    | x :: r -> x, r

لاحظ أن الطبيعة الدائمة للقوائم تضمن ديمومة المؤشّر. وتُعطى الشيفرة الكاملة في البرنامج 77.

المؤشّرات على الأشجار

لتعريف مؤشّر على الأشجار، يلزم أولاً اختيار ترتيب اجتياز. ونختار هنا الترتيب الوُسْطي اعتباطاً. (انظر التمرينين 9.8 و 9.9 لترتيبي اجتياز آخرين.)

وعلى خلاف السحّابات على القوائم، لا توفّر لنا السحّابات على الأشجار فوراً عملية لإنتاج العنصر التالي في الاجتياز الوُسْطي. غير أننا رأينا كيف يتيح السحّاب هذه العملية عند معالجة مشكلة مقارنة الأشجار الثنائية. ولا يلزم سوى البانيين Top و Left من السحّاب. ولذلك نعرّف النمط التالي للمؤشّر:

  type ’a enum = Top | Left of ’a * ’a tree * ’a enum

تضع الدالة start المؤشّر على العنصر الواقع في أسفل يسار الشجرة. ولهذا نستخدم الدالة leftmost التي كُتبت من أجل البرنامج 75.

  let start t =
    leftmost t Top

ترفع الدالة step الاستثناء Exit إذا كان المؤشّر Top. وإلا فإنها تُرجع العنصر x الموجود في الباني Left وتبني مؤشّراً جديداً باستدعاء leftmost على الشجرة الجزئية اليمنى لـ x.

  let step = function
    | Top -> raise Exit
    | Left (x, r, e) -> x, leftmost r e

وهذا بالضبط ما فعلناه في البرنامج 75 للانتقال إلى العنصر التالي.

وكما في حالة القوائم، تضمن الطبيعة غير القابلة للتغيير للنمط enum ديمومة المؤشّر. وتُعطى الشيفرة الكاملة في البرنامج 78 (انظر الصفحة السابقة).

  type line = { left: char list; right: char list }
  type text = { up: line list; current: line; down: line list }

  type tree = N of string * tree list