المصفوفات

4. المصفوفات

من أبسط بنى المعطيات المصفوفة (array)، التي يمثّلها النوع array في OCaml. نعرض في هذا الفصل عدة تنويعات على بنية المعطيات هذه. فنوضّح كيفية بناء مصفوفات قابلة لتغيير الحجم، ومصفوفات مضغوطة من القيم المنطقية، ومصفوفات ذات عملية دمج فعّالة، ومصفوفات دائمة.

4.1 المصفوفات القابلة لتغيير الحجم

المصفوفة القابلة لتغيير الحجم (resizeable array) هي مصفوفة يمكن زيادة حجمها أو إنقاصه في أي وقت بواسطة عملية resize. وتُعطى توقيعة هذه المصفوفات في البرنامج 17. (سنستعمل المصفوفات القابلة لتغيير الحجم في الفصلين 5 و6.)

الفكرة الكامنة وراء تنفيذ المصفوفات القابلة لتغيير الحجم بسيطة: نستعمل مصفوفة عادية لتخزين العناصر، فإذا صارت صغيرة جدًّا خصّصنا مصفوفة أكبر ننسخ إليها العناصر الموجودة. ولتفادي إضاعة وقت كبير في التخصيص والنسخ، نسمح للمصفوفة الداعمة (backing array) بأن تكون أكبر من اللازم، مع بقاء العناصر التي تتجاوز فهرسًا معينًا غير مستعملة.

وبالتالي فإن نوع المصفوفات القابلة لتغيير الحجم هو سجل (record) يحتوي على مصفوفة عادية في حقل data وعلى عدد العناصر المستعملة في حقل size.

  type ’a t = {
    mutable size: int;
    mutable data: ’a array;
  }

وهكذا، إذا كانت v مصفوفة قابلة لتغيير الحجم من هذا القبيل، أمكننا تمثيل الحالة كما يلي:

بناءً على ذلك، سنحافظ في ما يلي على الثابت (invariant) الآتي:

إذا أردنا زيادة حجم المصفوفة v، فهناك احتمالان ينبغي النظر فيهما. فإذا لم يتجاوز الحجم الجديد سعة المصفوفة v.data، كفى تعديل v.size. وإلا خصّصنا مصفوفة جديدة كبيرة بما يكفي ونسخنا

عناصر v.data إليها. ثم نُسند هذه المصفوفة الجديدة إلى v.data. وكلما أردنا إنقاص حجم المصفوفة v، كفى تعديل v.size.

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

  type ’a t = {
    default: ’a;
    mutable size: int;
    mutable data: ’a array;
  }

لنكتب الآن شفرة العمليات المختلفة. يُعطى طول المصفوفة القابلة لتغيير الحجم بواسطة الحقل size.

  let length a = a.size

لإنشاء مصفوفة جديدة قابلة لتغيير الحجم، يكفي استعمال Array.make وتخزين الحجم والقيمة الافتراضية.

  let make n d = { default = d; size = n; data = Array.make n d }

بصفة عامة، سنحافظ على الثابت الآتي على النوع t: كل عنصر يتجاوز الفهرس size، أي كل عنصر غير مستعمل، يحتوي على القيمة المخزَّنة في الحقل default.

للوصول إلى العنصر ذي الرتبة i في مصفوفة قابلة لتغيير الحجم a، لا بد من التحقق من صلاحية الفهرس، لأن المصفوفة a.data قد تحتوي على أكثر من a.size عنصر.

  let get a i =
    if i < 0 || i >= a.size then invalid_arg "get";
    a.data.(i)

لاحظ أنه متى جرى هذا التحقق، أمكننا استعمال Array.unsafe_get للوصول إلى a.data لمزيد من الفعالية. وعملية الإسناد مماثلة:

  let set a i v =
    if i < 0 || i >= a.size then invalid_arg "set";
    a.data.(i) <- v

يكمن كل الدقة في الدالة resize، التي تعدّل حجم مصفوفة قابلة لتغيير الحجم a. وهناك عدة حالات ممكنة. فإذا كان الحجم الجديد s أصغر من a.size أو يساويه، كفى استبدال العناصر الواقعة بين s وa.size-1 بالقيمة a.default.

  let resize a s =
    if s <= a.size then
      Array.fill a.data s (a.size - s) a.default

ويمكننا كذلك إعادة تخصيص العناصر في مصفوفة أصغر (انظر التمرين 4.2). أما إذا كان s أكبر من a.size، فلا بد من التحقق مما إذا كانت المصفوفة a.data كبيرة بما يكفي لاحتواء s عنصرًا. لذلك نحسب الحجم n للمصفوفة a.data ونقارنه بـ s.

    else begin
      let n = Array.length a.data in
      if s > n then begin

إذا كان s أكبر من n، فلا بد من تغيير حجم المصفوفة. ونختار هنا استراتيجية مضاعفة حجم المصفوفة a.data. (انظر التمرين 4.1 لاستراتيجية أخرى.) ولما كان ذلك قد لا يكفي، نحسب الحجم الجديد باعتباره القيمة العظمى لـ 2*n وs.

        let n’ = max (2 * n) s in

ولضمان السلامة التامة، كان يلزم تقييد الحجم الجديد بالحجم الأقصى للمصفوفات، أي Sys.max_array_length، والفشل إذا كانت القيمة s كبيرة جدًّا. وقد تُرك هذا تمرينًا للقارئ.

ثم نخصّص مصفوفة جديدة بحجم n’ ننسخ إليها عناصر a.data المستعملة. ولهذا نستعمل الدالة Array.blit، التي تنسخ جزءًا من مصفوفة إلى أخرى.

        let a’ = Array.make n’ a.default in
        Array.blit a.data 0 a’ 0 a.size;

ثم نستبدل المصفوفة a.data بالمصفوفة الجديدة.

        a.data <- a’
      end
    end;

عندما s<=n، لا يبقى ما يُفعل. وأخيرًا، في جميع الحالات، ننتهي بتحديث الحقل size.

    a.size <- s

وبهذا يكتمل تنفيذ المصفوفات القابلة لتغيير الحجم. والشفرة معطاة كاملة في البرنامج 18 (انظر الصفحة 303).

التعقيد

تُستعمل المصفوفات القابلة لتغيير الحجم عادةً عندما لا يكون عدد العناصر المراد تخزينها معروفًا مسبقًا (انظر التمرين 4.3). لنفترض أننا نبدأ بمصفوفة قابلة لتغيير الحجم

طولها 0 ونزيد طولها n مرة بمقدار وحدة واحدة، لننتهي بمصفوفة طولها n. وتقتضي الاستراتيجية الساذجة، التي تمنح المصفوفة data الطول نفسه بالضبط الذي للمصفوفة القابلة لتغيير الحجم، أن تكون تكلفة كل عملية resize بطول i مقدار i. وتكون التكلفة الإجمالية عندئذ تربيعية:

بيد أن الاستراتيجية التي تنفذها resize هنا أكثر دقة، وهي تتمثل في مضاعفة حجم المصفوفة (على الأقل) كلما احتاجت إلى الزيادة. وتكون التكلفة الإجمالية عندئذ خطية، ويمكن بيان ذلك كما يلي: لنفترض، دون إخلال بالعمومية، أن n ≥ 2. ولتكن k = ⌊log 2(n)⌋، أي 2k ≤ n < 2k+1. بدءًا من مصفوفة فارغة، نكون قد نفّذنا ما مجموعه k + 2 عملية تغيير حجم للوصول إلى مصفوفة data بحجم نهائي 2k+1. وبعد عملية تغيير الحجم رقم i، حيث i = 0,…,k + 1، يكون حجم المصفوفة 2i. لذلك تكون تكلفة عملية تغيير الحجم رقم i مقدار 2i. والتكلفة الإجمالية عندئذ:

وبعبارة أخرى، فإن بعض عمليات resize لها تكلفة ثابتة (عندما لا تكون زيادة الحجم ضرورية فعلاً). في المقابل، لعمليات أخرى تكلفة غير ثابتة، لكن التعقيد الإجمالي يبقى خطيًّا. وبأخذ المتوسط على العمليات n، يكون الأمر كما لو كانت كل إضافة ذات تكلفة ثابتة. لذلك فإن توسيع مصفوفة قابلة لتغيير الحجم بمقدار وحدة واحدة له تعقيد مطفأ (amortized complexity) من الرتبة O(1).

4.2 المتجهات البتية (bit vectors)

إذا احتاج برنامج إلى معالجة مجموعة من الأعداد الصحيحة تقع ضمن مجال معقول، وإذا لم تكن الاستدامة مطلوبة، أمكن استعمال مصفوفة من القيم المنطقية. وهذا ما فعلناه مثلاً في القسم 2.5 غربال إراتوستينس. غير أنه، بما أن القيمة المنطقية تُمثَّل بكلمة ذاكرة واحدة (32 أو 64 بتة حسب المعمارية)، تُهدر ذاكرة كثيرة. فبينما تكفي بتة واحدة لكل عنصر، تشغل مصفوفة القيم المنطقية 32 أو 64 ضعف هذا المقدار. وبنية معطيات المتجه البتي (bit vector) مفيدة تحديدًا في هذا الشأن: فهي تتيح استعمال بتة واحدة لكل عنصر.

توقيعة بنية المعطيات هذه هي نفسها تمامًا توقيعة المصفوفات، باستثناء أن العناصر من النوع bool. وتُعطى بداية هذه التوقيعة في البرنامج 19 (انظر أدناه).

يقوم التنفيذ على استعمال مصفوفة عادية من الأعداد الصحيحة وتخزين عدة قيم منطقية في كل عدد صحيح: 31 قيمة منطقية في معمارية 32 بتة و63 قيمة منطقية في معمارية 64 بتة. (تذكّر أن OCaml تحجز بتة واحدة من كل عدد صحيح لاستعمال جامع القمامة.) ونبدأ بجعل bpi عدد القيم المنطقية المخزَّنة في كل عدد صحيح.

  let bpi = Sys.word_size - 1

يُعطى الحجم الأقصى للمتجه البتي إذن بالقيمة الآتية:

  let max_length = Sys.max_array_length * bpi

لتمثيل متجه بتي، نُعرّف النوع الآتي t:

  type t = {
    length : int;
    bits : int array;
  }

يحتوي الحقل length على العدد الفعلي للقيم المنطقية الموجودة في المتجه البتي، إذ لا يكون هذا العدد بالضرورة مضاعفًا لـ bpi. ويحتوي الحقل bits على مصفوفة الأعداد الصحيحة. وإذا كانت b0,b1,…,bbpi−1 أول bpi عنصرًا من مصفوفة القيم المنطقية، فإنها تُمثَّل في الخلية الأولى من المصفوفة bits بالعدد الصحيح

وتُمثَّل العناصر bpi التالية بالطريقة نفسها بالعدد الصحيح الثاني من المصفوفة bits، وهكذا دواليك. وعندما لا يكون عدد العناصر مضاعفًا لـ bpi، تبقى بعض البتات عالية الرتبة في آخر عدد صحيح من المصفوفة غير مستعملة. وللسماح بمقارنة المتجهات البتية بنيويًّا، نفرض الثابت الآتي على التمثيل:

يمكننا إذن استعمال عمليتي OCaml = أو <> على المتجهات البتية، بغض النظر عن كيفية بنائها.

الإنشاء

نبدأ بالدالة create، التي تبني متجهًا بتيًّا بحجم n، حيث يكون لجميع العناصر القيمة نفسها b. وباستثناء العدد الصحيح الأخير، ستحتوي جميع عناصر المصفوفة bits على القيمة نفسها: 0 إذا كان b مساويًا false أو −1 إذا كان b مساويًا true. ويرجع ذلك إلى أنه في تمثيل المتمم الثنائي (two’s complement)، يُكتب −1 في النظام الثنائي باستعمال الرقم 1 فقط، أي −1 = (1⋯1)2. لذلك تبدأ الدالة create بتعريف هذه القيمة الأولية، 0 أو −1، حسب قيمة b.

  let create n b =
    let initv = if b then -1 else 0 in

يتحدد عدد عناصر المصفوفة bits عندئذ بالقسمة الإقليدية لـ n على bpi.

    let q = n / bpi and r = n mod bpi in

إذا كان الباقي r مساويًا 0، فجميع عناصر المصفوفة مستعملة بالكامل، ويكفي بناء مصفوفة بحجم q مهيّأة بالقيمة initv.

    if r = 0 then
      { length = n; bits = Array.make q initv }

أما إذا لم يكن الباقي r مساويًا 0، فنحتاج إلى بناء مصفوفة من q + 1 عددًا صحيحًا. وتحتوي جميع العناصر على initv، باستثناء الأخير، الذي يجب أن تكون بتاته عالية الرتبة 0 احترامًا للثابت. وبشكل أدق، إذا كان b مساويًا true، فيجب أن يحتوي العنصر الأخير من المصفوفة على r بتة مضبوطة منخفضة الرتبة بالضبط. ويُحصل على ذلك بسهولة باستعمال التعبير (1lslr)-1. وبهذا تكتمل الدالة create:

    else begin
      let a = Array.make (q + 1) initv in
      if b then a.(q) <- (1 lsl r) - 1;
      { length = n; bits = a }
    end

الشفرة الكاملة معطاة في البرنامج 20.

القراءة

لقراءة العنصر ذي الرتبة n في متجه بتي، يجب أولاً تحديد الفهرس i للعدد الصحيح المقابل في المصفوفة، ثم الفهرس j للبتة المقابلة داخل هذا العدد الصحيح. وتُستخرج قيمتا i وj من القسمة الإقليدية لـ n على bpi. وبمعرفة العنصر ذي الرتبة i من المصفوفة، يكفي، لاستخراج البتة ذات الرتبة j، إزاحة هذا العدد الصحيح j موضعًا إلى اليمين باستعمال lsr، ثم اختبار بتته الأقل دلالة. فننتهي إلى الدالة الآتية:

  let get v n =
    let i = n / bpi and j = n mod bpi in
    (v.bits.(i) lsr j) land 1 <> 0

وبشكل مكافئ، يمكننا كذلك إجراء عملية العطف البتي (logical and) على العدد الصحيح الذي يحتوي على بتة واحدة مضبوطة في الموضع j، والذي نحصل عليه بالتعبير 1lslj:

    v.bits.(i) land (1 lsl j) <> 0

الكتابة

لإسناد قيمة b من النوع bool إلى العنصر ذي الرتبة n في متجه بتي v، نبدأ بتحديد موضعه تمامًا كما فعلنا في القراءة، عبر القسمة الإقليدية لـ n على bpi.

  let set v n b =
    let i = n / bpi and j = n mod bpi in

ثم ننظر في الحالتين الممكنتين كلًّا على حدة. فإذا كان b مساويًا true، أي إذا كان يجب ضبط البتة ذات الرتبة j في v.bits.(i) على 1، أجرينا عملية الفصل المنطقي (logical or) على العدد الصحيح الذي يحتوي على بتة واحدة مضبوطة في الموضع j.

    if b then
      v.bits.(i) <- v.bits.(i) lor (1 lsl j)

وإلا وجب ضبط البتة ذات الرتبة j على 0، وهو ما يمكن إجراؤه بعملية العطف المنطقي (logical and) على عدد صحيح جميع بتاته مضبوطة باستثناء البتة j.

    else
      v.bits.(i) <- v.bits.(i) land lnot (1 lsl j)

الشفرة الكاملة للدالتين get وset معطاة في البرنامج 21. ومن الواضح أن تكلفة العمليتين O(1).

العمليات المتعلقة بالمجموعات

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

خُذ مثلاً عملية العطف المنطقي (logical and) لمتجهين بتين، inter، التي تحسب أيضًا تقاطع المجموعتين المقابلتين. وهذه العملية لا معنى لها إلا عندما يكون المتجهان البتيان بالحجم نفسه. ونبدأ بالتحقق من ذلك.

  let inter v1 v2 =
    let l1 = v1.length in
    if l1 <> v2.length then invalid_arg "Bitv.inter";

ومتى علمنا أن المتجهين بالحجم نفسه، نفّذنا عملية العطف المنطقي نفسها. ولهذا يمكننا استعمال الدالة Array.mapi، التي تبني مصفوفة بتطبيق دالة على جميع عناصر مصفوفة أخرى.

    let b = Array.mapi (fun i ei -> ei land v2.bits.(i)) v1.bits in
    { length = l1; bits = b }

وبهذا تكتمل الدالة inter. ويمكننا بالمثل كتابة الدالة union، التي تحسب الاتحاد المجموعي، بإجراء عملية الفصل المنطقي (logical or).

لاحظ أن الثابت (4.1) محترَم، لأن العطف والفصل يحافظان على الأصفار عالية الرتبة غير المستعملة. أما العمليات البتية مثل النفي (negation) أو الفصل الحصري (exclusive or) فليس الأمر كذلك. وفي هذه الحالات، لا بد من إعادة إرساء الثابت بتصفير البتات عالية الرتبة غير المستعملة بعديًّا (a posteriori). ولنكتب دالة normalize تفعل ذلك. نبدأ بجعل r عدد البتات المستعملة في العدد الصحيح الأخير من المصفوفة.

  let normalize v =
    let r = v.length mod bpi in

فإذا لم يكن هذا العدد صفرًا، وجب تصفير جميع البتات ذات الرتبة r وما فوقها. ويمكن تنفيذ ذلك باستعمال قناع يحتوي على r بتة مضبوطة منخفضة الرتبة بالضبط، أي 1lslr-1.

    if r > 0 then
      let s = Array.length v.bits - 1 in
      v.bits.(s) <- v.bits.(s) land (1 lsl r - 1)

وبهذا تكتمل الدالة normalize.

ويمكننا بسهولة أن نستخلص من هذا دالة compl تحسب النفي البتي لمتجه بتي، أي متمم المجموعة المقابلة.

  let compl v =
    let b = Array.map lnot v.bits in
    let r = { length = v.length; bits = b } in
    normalize r;
    r

الدالتان inter وcompl ملخَّصتان في البرنامج 22 (انظر الصفحة 320). وتكلفتهما O(n) في الزمن والمكان، حيث n حجم المتجهات البتية المعنية.

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

  val iteri_true : (int -> unit) -> t -> unit

لتنفيذ هذه الدالة، نكرّر على عناصر المصفوفة باستعمال Array.iteri. ولكل عنصر، نكرّر على البتات المضبوطة بحلقة تختبر كل بتة على التوالي. فنحصل على الشفرة الآتية:

  let iteri_true f v =
    Array.iteri
      (fun i ei ->
         let index = i * bpi in
         for j = 0 to bpi - 1 do
           if ei land (1 lsl j) <> 0 then f (index + j)
         done)
      v.bits

ليس من الضروري معالجة حالة العنصر الأخير من المصفوفة على حدة، لأن الثابت يضمن بدقة أن البتات غير المستعملة قيمتها 0.

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

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

غير أنه تبقى صعوبة واحدة: فالتعبير xland-x لا يعيد الفهرس i للبتة المضبوطة منخفضة الرتبة في x، بل يعيد 2i. ولذلك نحتاج إلى حساب اللوغاريتم ذي الأساس 2 لهذه القيمة، أو ما يكافئه، أي عدد الأصفار منخفضة الرتبة. ولهذا، لنفترض أن لدينا دالة ntz، اختصارًا لـ number of trailing zeros، تحسب عدد الأصفار منخفضة الرتبة في عدد صحيح.

ويمكننا عندئذ إعادة كتابة الجزء من شفرة iteri_true الذي يفحص البتات المضبوطة في ei بمساعدة دالة عودية visit بدلاً من حلقة for.

       let rec visit x =
         if x <> 0 then begin
           let b = x land -x in
           f (index + ntz b);
           visit (x - b)
         end
       in
       visit ei

تنتهي الدالة visit بمجرد أن تصير وسيطها 0، أي عندما لا تحتوي على أي بتة مضبوطة. وإلا استخرجنا البتة المضبوطة منخفضة الرتبة، b. فنستدعي f على الفهرس المقابل index+ntzb، ثم نستدعي visit مرة أخرى على x-b، وهي x بعد تصفير البتة ذات الرتبة b. والشفرة الكاملة لـ iteri_true معطاة في البرنامج 23 (انظر الصفحة 324). وتُخصص الدالة ntz للتمرين 4.6.

أخيرًا، لنكتب دالة cardinal:t->int، تحسب عدد البتات المضبوطة في المتجه البتي، أي أصل المجموعة (cardinal). ويكفي حساب مجموع عدد البتات المضبوطة في كل عنصر من المصفوفة. وإذا افترضنا أن لدينا دالة pop من النوع int->int تحسب عدد البتات المضبوطة في عدد صحيح، أمكن الحصول على الدالة cardinal بسهولة.

  let cardinal v =
    Array.fold_left (fun n x -> n + pop x) 0 v.bits

وتبقى الدالة pop (اختصارًا لـ population count) بحاجة إلى كتابة. ويمكننا كتابتها باستخراج البتات واحدة تلو الأخرى، مرة أخرى بفضل التعبير xland-x:

  let pop x =
    let rec count n x =
      if x = 0 then n else count (n + 1) (x - (x land -x)) in
    count 0 x

ويمكننا جعل هذه الدالة أكثر فعالية بجدولتها (انظر التمرين 4.12).

عمليات أخرى على المتجهات البتية

لتكتمل مكتبة المتجهات البتية، ينبغي أن توفر عمليات أخرى أيضًا. فمن جهة، ينبغي أن توفر العمليات نفسها التي نستعملها للمصفوفات، مثل append وsub وfill وblit. ومن جهة أخرى، ينبغي أن تقدّم كذلك عمليات حسابية تفسّر المتجه البتي كعدد صحيح من n بتة، مثل الجمع والإزاحات والتحويلات من وإلى الأنواع الصحيحة المختلفة في OCaml. ويُقترح بعض هذه العمليات في التمارين 4.8–4.11.

4.3 الحبال (ropes)

يعرض هذا القسم بنية معطيات الحبل (rope). وقد أدخلت هذه البنية في الأصل بديلاً عن السلاسل النصية (strings)، لمعالجة المسائل الآتية:

• السلاسل النصية ليست دائمة؛ فهي غير قابلة للتعديل في OCaml، لكن هذا ليس بالضرورة الحال في لغات أخرى، مثل C مثلاً.
• السلاسل النصية محدودة الحجم، خصوصًا عند استعمال OCaml على جهاز 32 بتة، حيث الحد هو 224 − 5 حرفًا.
• للدمج واستخراج السلسلة الجزئية تكلفة كبيرة، وخاصة في المكان، لأنهما يتضمنان نسخ محتوى السلسلة النصية الأساسية.

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

  type t =
    | Str of string
    | App of t * t

مثلاً، إحدى القيم الممكنة التي يمكن أن تمثّل بها السلسلة النصية "averylongstring" هي الآتية:

يدفعنا اعتباران إلى تنقيح النوع المقترح t. فمن جهة، تتطلب خوارزميات عديدة وصولاً فعّالاً إلى طول الحبل، خصوصًا لتقرير ما إذا كان ينبغي النزول عبر الشجرة الجزئية اليسرى أم اليمنى لعقدة App. لذلك يُستحسن توسيم كل عقدة داخلية بطول الحبل. ومن جهة أخرى، من المهم تقاسم السلاسل الجزئية بين الحبال نفسها وكذلك مع السلاسل النصية العادية المستعملة لبناء الحبال. ومن ثَمّ، بدلاً من أن تشير عقدة Str إلى سلسلة نصية كاملة في OCaml، نفضّل أن تدلّ على سلسلة جزئية من سلسلة نصية في OCaml. وتُمثَّل السلسلة الجزئية من سلسلة s بثلاثية (s,o,n)، تدل على s[o..o + n − 1]، أي الجزء من s الذي طوله n والبداية عند الإزاحة o. وهكذا نحصل على النوع الآتي:

  type t =
    | Str of string * int * int
    | App of t * t * int

تمثّل العقدة App(r1,r2,n) دمج الحبلين r1 وr2، وطولهما الإجمالي n. وكان يمكننا كذلك تخزين حجمي r1 وr2 في العقدة. غير أن الاحتفاظ بالحجم الإجمالي وحده أكثر اقتصادًا من حيث حيّز الذاكرة، ولا ضياع في الفعالية عمليًّا.

العمومية (genericity)

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

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

يعطي البرنامج 24 توقيعة دنيا STRING لبنية معطيات السلاسل النصية. النوع المجرّد t هو نوع السلاسل النصية، والنوع char هو نوع محارفها. ولا تحتوي هذه التوقيعة إلا على العمليات اللازمة لتنفيذ بنية الحبل. وهي متوافقة مع عمليات الوحدة String في OCaml.

نُعرّف توقيعة ROPE للحبال في البرنامج 25. وتتضمن هذه التوقيعة الوحدة S للسلاسل النصية التي ستكون أوراق الحبال. وتوفّر التوقيعة ROPE العمليات نفسها التي توفّرها السلاسل النصية، لنوع المحارف نفسه، وهو ما يمكن ترجمته كما يلي:

  include STRING with type char = S.char

الحبال غير قابلة للتعديل. وعمليات التحديث (set وغيرها) تعيد حبالاً جديدة.

تُنفَّذ بنية الحبل طبيعيًّا كدالّية محدِّدة الوسائط (functor) تُعامَل بوحدة X ذات التوقيعة STRING:

  module Make(X : STRING) : (ROPE with module S = X) = struct

للوحدة الناتجة عن تطبيق هذه الدالّية المحدِّدة الوسائط التوقيعة ROPEwithmoduleS=X، التي تحدّد أن وحدتها S هي الوحدة X الممرَّرة وسيطًا للدالّية المحدِّدة الوسائط. ولذلك تبدأ الشفرة بتعريف S على أنها تساوي X:

  module S = X

نوع محارف الحبل هو نوع محارف السلاسل النصية نفسه:

  type char = S.char

ونوع الحبال كما عُرض سابقًا:

  type t =
    | Str of S.t * int * int
    | App of t * t * int

سنفرض عدة ثوابت على هذا النوع. فمن جهة، لكل حبل من الشكل Str(s,o,n)، لدينا المتباينات:

ومن جهة أخرى، لكل حبل من الشكل App(u,v,n)، لدينا المتباينات:

العمليات الأساسية

بتعريف النوع t، يمكن حساب طول الحبل في زمن ثابت.

  let length = function
    | Str (_,_,n)
    | App (_,_,n) -> n

وبناء الحبل الفارغ مباشر باستعمال السلسلة النصية الفارغة:

  let empty =
    Str (S.empty, 0, 0)

وبصفة أعم، يُعطى الحبل المقابل لسلسلة نصية s بما يلي:

  let of_string s =
    Str (s, 0, S.length s)

والأهم أنه يجب أن يكون النوع S.t نفسه دائمًا، لضمان كلٍّ من الطبيعة الدائمة للحبال وصحة عمليات الحبال. وهذا هو الحال عندما يكون S.t هو النوع string، إذ إن السلاسل النصية في OCaml غير قابلة للتعديل.

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

  let rec unsafe_get t i = match t with
    | Str (s, ofs, _) ->
        S.get s (ofs + i)
    | App (t1, t2, _) ->
        let n1 = length t1 in
        if i < n1 then unsafe_get t1 i else unsafe_get t2 (i - n1)

نرى هنا أهمية القدرة على استرجاع حجم t1 في زمن ثابت. لذلك يتحدد تعقيد هذه العملية بارتفاع الشجرة. وكما سنرى لاحقًا، يمكن موازنة الحبال لتقليل هذا الارتفاع.

نُعرّف دالة get تتحقق أيضًا من صلاحية الفهرس، كغلاف حول unsafe_get.

  let get t i =
    if i < 0 || i >= length t then invalid_arg "get";
    unsafe_get t i

تُعرض هذه العمليات الأساسية على الحبال معًا في البرنامج 26 (انظر الصفحة 339).

الدمج

مبدئيًّا (A priori)، فإن دمج حبلين t1 وt2 بسيط بقدر تطبيق البانية App وحساب الطول الإجمالي، أي:

  let append t1 t2 =
    App (t1, t2, length t1 + length t2)

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

ثمة فكرتان تتيحان لنا التحكم في عدد العقد وارتفاع الشجرة. وتتمثل الفكرة الأولى في دمج الأوراق «الصغيرة» فعليًّا (أي السلاسل النصية القصيرة) عندما توجد متجاورة في الشجرة. ويمكننا أن نختار، مثلاً، دمج الورقتين s1 وs2 في الحالات الثلاث المبيَّنة في الشكل 4.1. وتقابل الحالة الأولى دمج حبل فرعه الأيمن هو الورقة الصغيرة s1 مع ورقة صغيرة أخرى s2. وتقابل الثانية دمج ورقتين صغيرتين، s1 وs2. أما الثالثة فهي الصورة المعكوسة للأولى.

الشكل 4.1: الحالات الممكنة مع الأوراق المتجاورة.

لتحديد ما إذا كانت الأوراق صغيرة بما يكفي لتُدمج، نستعمل ثابتًا:

  let small_length = 256

الثابت اعتباري وينبغي اختياره حسب الاستعمال المحدَّد لبنية الحبل. ويقترح التمرين 4.15 جعل هذا الثابت وسيطًا للدالّية المحدِّدة الوسائط.

لتنفيذ دمج ورقتين، نُعرّف الدالة العامة الآتية التي تدمج أجزاء من سلسلتين نصيتين، s1 وs2:

  let append_string s1 ofs1 len1 s2 ofs2 len2 =
    Str (S.append (S.sub s1 ofs1 len1) (S.sub s2 ofs2 len2),
         0, len1 + len2)

نعطي الآن شفرة الدالة append، التي تنفّذ دمج حبلين t1 وt2.

نبدأ بالنظر في الحالة التي يكون فيها أحد الحبلين فارغًا.

  let append t1 t2 = match t1, t2 with
    | Str (_,_,0), t | t, Str (_,_,0) ->
        t

بعد ذلك، ننظر في الحالات الثلاث الممكنة التي توجد فيها ورقتان صغيرتان متجاورتين. وأبسط حالة هي التي تكون فيها t1 وt2 هما الورقتان المعنيتان. فنستعمل عندئذ الدالة append_string:

    | Str (s1, ofs1, len1), Str (s2, ofs2, len2)
     when len1 <= small_length && len2 <= small_length ->
        append_string s1 ofs1 len1 s2 ofs2 len2

والحالتان الأخريان مماثلتان:

    | App (t1, Str (s1, ofs1, len1), _), Str (s2, ofs2, len2)
      when ... -> ...
    | Str (s1, ofs1, len1), App (Str (s2, ofs2, len2), t2, _)
      when ... -> ...

وأخيرًا، الحالة العامة هي ببساطة تطبيق البانية App، كما ناقشنا سابقًا:

    | t1, t2 ->
        App (t1, t2, length t1 + length t2)

الشفرة الكاملة لـ append معطاة في البرنامج 27.

في ما تبقى من القسم، سنستعمل المعامل المُداخل (infix) ++ للدلالة على دمج الحبال.

   let (++) = append

تتضمن الفكرة الثانية التي تتيح لنا التحكم في ارتفاع الحبال إعادة موازنة (rebalancing) الشجرات الأساسية. ويمكننا تنفيذ الموازنة تدريجيًّا أثناء بناء الحبل، باستعمال مثلاً التقنية نفسها التي تُستعمل لشجرات AVL (انظر الفصل 5). وسيلزم عندئذ تعديل السطر الأخير من الدالة append لاستدعاء دالة موازنة بدلاً من البانية App. ويمكننا بالمثل تصوّر إعادة موازنة بعدية (a posteriori) تُنفَّذ إما انتقائيًّا، عندما يصبح ارتفاع الشجرة كبيرًا جدًّا، أو صراحةً، عندما يطلب المستعمل ذلك. وتقترح التمارين 4.17–4.20 طرقًا مختلفة لتنفيذ إعادة موازنة بعدية.

استخراج حبل فرعي

تتعلق العملية التالية باستخراج جزء من حبل، محدَّد بإزاحة وطول. ويقوم الاستخراج على الاحتفاظ فقط بأجزاء الحبل الواقعة ضمن هذا الجزء، مع إعادة بناء عقد Str التي تتداخل معه جزئيًّا عند الحاجة. بل إن الأفضل تحديد الجزء المراد استخراجه بأنه يمتد من الإزاحة start (شاملة) إلى الإزاحة stop (غير شاملة). ونفترض أن هذا جزء صالح وغير فارغ، أي:

تبدأ دالة الاستخراج، mksub، بالنظر في الحالة الخاصة التي يكون فيها الجزء هو الحبل كله.

  let rec mksub start stop t =
    if start = 0 && stop = length t then
      t

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

وفي الحالة العامة، نفحص شكل الحبل t. فإذا كانت t ورقة، كفى تعديل مواصفة الجزء:

    else match t with
      | Str (s, ofs, _) ->
          Str (s, ofs+start, stop-start)

لاحظ أن هذه عملية ذات زمن ثابت، لا تستدعي S.sub، وأنها تتقاسم s بين الحبل الأولي وناتج الاستخراج. أما الحبل من الشكل App، فهناك ثلاث حالات ينبغي النظر فيها. الأولى هي عندما يكون الجزء محتوى بالكامل في الحبل الفرعي الأيسر. ويكفي عندئذ إجراء استدعاء عودي.

      | App (t1, t2, _) ->
          let n1 = length t1 in
          if stop <= n1 then mksub start stop t1

وبالتناظر، قد يكون الجزء محتوى بالكامل في الحبل الفرعي الأيمن.

          else if start >= n1 then mksub (start-n1) (stop-n1) t2

وأخيرًا، قد يتداخل الجزء مع كلٍّ من t1 وt2. ويكفي عندئذ دمج جزء t1 مع جزء t2.

          else mksub start n1 t1 ++ mksub 0 (stop-n1) t2

لاحظ أن أياً من هذين الجزأين ليس فارغًا، وهو ما يحترم ثابت mksub. ولاحظ أيضًا أن t1 أو t2 قد يكون محتوى بالكامل في الناتج، وفي هذه الحالة سيُتقاسمان بحكم السطرين الأولين من الدالة mksub.

بعد ذلك، نُعرّف دالة استخراج sub محدَّدة بإزاحة ofs وطول len (مشابهة لـ String.sub أو Array.sub). وهي تتحقق من صلاحية الوسائط، ثم تعالج الحالة الخاصة بجزء فارغ أو تستدعي الدالة العودية mksub.

  let sub t ofs len =
    let stop = ofs + len in
    if ofs < 0 || len < 0 || stop > length t then invalid_arg "sub";
    if len = 0 then empty else mksub ofs stop t

الشفرة الكاملة معطاة في البرنامج 28.

عمليات التحديث

ننظر الآن في عدة عمليات لإدراج المحارف أو حذفها في حبل. ولما كانت الحبال دائمة، فإن هذه العمليات لا تعدّلها في مكانها، بل تعيد حبالاً جديدة.

لننظر مثلاً في العملية set، التي تُدرج المحرف c عند الإزاحة i في حبل t. نبدأ بالتحقق من أن الإزاحة i صالحة، أي 0 ≤ i < length t.

  let set t i c =
    let n = length t in
    if i < 0 || i >= n then invalid_arg "set";

بعد ذلك، يكفي استخراج الحبلين الفرعيين الواقعين إلى يسار الإزاحة i وإلى يمينها، واستعمال الدمج لإدراج المحرف c.

    sub t 0 i ++ make 1 c ++ sub t (i + 1) (n - i - 1)

غير أننا نلاحظ أن هذا الحل ليس أمثل، لأنه يُجري اجتيازين عوديين للحبل حيث كان يكفي اجتياز واحد. ويقترح التمرين 4.16 تحسينًا في هذا الشأن.

ويمكننا بالمثل تعريف العمليات insert (التي تُدرج حبلاً داخل حبل آخر عند إزاحة معطاة)، وinsert_char (التي تُدرج محرفًا في حبل)، وdelete_char (التي تحذف المحرف ذا الرتبة i من حبل). والشفرة الكاملة للعمليات الأربع معطاة في البرنامج ?? (انظر الصفحة السابقة). وبهذا ننهي مناقشتنا للدالّية المحدِّدة الوسائط التي تعرّف الحبال.

تطبيق: محرر نصوص

تعدّ الحبال بنية مثالية لمحررات النصوص، خصوصًا لدعم النصوص الطويلة جدًّا، التي قلّما تُعالَج جيدًا في محررات النصوص، بما فيها أشهرها.

فبدلاً من استعمال حبل واحد لتمثيل النص المراد تحريره كاملاً، سنستعمل الدالّية المحدِّدة الوسائط لمزيد من المرونة. فالتعامل مع أسطر النص باستعمال حبل واحد أمر عسير: إذ يجب إيجاد فواصل الأسطر، أو تسجيل إزاحاتها في جدول

يجب إبقاؤه متزامنًا مع النص. وبدلاً من ذلك، يمكننا استعمال حبال عناصرها محارف لتمثيل الأسطر، وحبل عناصره أسطر لتمثيل النص كله.

لذلك نبدأ ببناء بنية حبل للأسطر. وتستند وسيطة الدالّية المحدِّدة الوسائط Make إلى الوحدة String في OCaml:

  module Str = struct
    include String
    let get = unsafe_get
    type char = Char.t
    let empty = ""
    let append = (^)
  end

لاحظ أننا نستعمل String.unsafe_get بدلاً من String.get، لأن كل وصول إلى محارف سلسلة نصية موجودة في حبل مضمون أنه صالح. ويمكننا بذلك تفادي فحوص لا لزوم لها. وتُحصل الحبال بتطبيق الدالّية المحدِّدة الوسائط Make كما يلي:

  module Line = Make(Str)

بعد ذلك، نُنشئ بنية حبل أخرى للنص كله، «محارفها» هي الأسطر. ويكفي لهذا تطبيق الدالّية المحدِّدة الوسائط Make مرة أخرى، باستعمال مصفوفات هذه المرة لأوراق حبالنا.

  module Text = Make(struct
                       type char = Line.t
                       type t = Line.t array
                       let empty = [||]
                       let length = Array.length
                       let make = Array.make
                       let append = Array.append
                       let get = Array.unsafe_get
                       let sub = Array.sub
                     end)

نرى هنا فائدة تعريف الحبال كدالّية محدِّدة الوسائط، وهو ما يتيح لنا تطبيقها مرتين على وسيطين مختلفين.

ولنفترض، تبسيطًا، أن النص الذي يعالجه المحرر مخزَّن في مرجع يحتوي على حبل من النوع Text.t.

  let text = ref ...

لإدراج محرف c عند الإزاحة ofs في السطر l من النص، يكفي استرجاع السطر بواسطة Text.get، وتعديله باستعمال Line.insert، ثم تحديث النص أخيرًا باستعمال Text.set:

  let insert_char l ofs c =
    let line = Text.get !text l in
    let line’ = Line.insert_char line ofs c in
    text := Text.set !text l line’

وبالمثل، لحذف محرف:

  let delete_char l ofs =
    let line = Text.get !text l in
    let line’ = Line.delete_char line ofs in
    text := Text.set !text l line’

وأخيرًا، لإدراج سطر جديد عند الإزاحة ofs في السطر l من النص، يكفي قطع السطر l عند الإزاحة ofs باستدعاءين لـ Line.sub، ثم إدراج البادئة في السطر l باستعمال Text.insert، ووضع اللاحقة في السطر l+1 باستعمال Text.set:

  let insert_newline l ofs =
    let line = Text.get !text l in
    let prefix = Line.sub line 0 ofs in
    let suffix = Line.sub line ofs (Line.length line - ofs) in
    let r = Text.insert_char !text l prefix in
    text := Text.set r (l + 1) suffix

لاحظ أنه ليس من الضروري «إزاحة» جميع الأسطر: فنحن نستعمل الإدراج في حبل الأسطر، كما استعملنا الإدراج في حبال المحارف في insert_char.

ملاحظة

وكما أن عمليات الدمج معلَّقة (suspended) في الحبال، فإن عمليات الاستخراج أيضًا قد تكون معلَّقة. وسيكون نوع OCaml الناتج كما يلي:

  type t =
    | Str of S.t
    | Sub of t * int * int
    | App of t * t * int

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

بل يمكن تعليق عملية الاستخراج «مجانًا»، بتطبيق الدالّية المحدِّدة الوسائط Make مرارًا على ناتجها هي، كما يلي:

  module R1 = Make(Str)
  module R2 = Make(R1)
  ...

في حبال الوحدة R2، تكون الأوراق حبالاً من R1. ومن ثَمّ، لا تُستدعى الدالة R1.sub إلا عندما تصبح الورقة صغيرة بما يكفي. وما دام الأمر ليس كذلك، تبقى العملية معلَّقة. وبقليل من التسامح في الترميز، يمكن القول إن النوعين R1.t وR2.t يقابلان التعريفين الآتيين:

  type R1.t =
    | R1.Str of string * int * int
    | R1.App of R1.t * R1.t * int
  type R2.t =
    | R2.Str of R1.t * int * int
    | R2.App of R2.t * R2.t * int

ومن الواضح أن العقدة R2.Str تعلّق الاستخراج على قيمة من النوع R1.t. وبتكرار هذه العملية، نحصل على نوع مكافئ للنوع السابق t.

4.4 المصفوفات الدائمة (persistent arrays)

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

تُعطى توقيعة المصفوفات الدائمة في البرنامج 30. وهي نفس توقيعة المصفوفات تمامًا، باستثناء أن الدالة set تعيد مصفوفة دائمة جديدة،

دون تغيير وسيطها.

من الخصائص المرغوبة في المصفوفات الدائمة أنها توفّر العمليتين set وget بالفعالية نفسها — O(1) — التي توفّرها المصفوفات، على الأقل ما دامت طبيعتها الدائمة غير مستعملة. غير أننا نقبل أن تكون هناك تكلفة مقابل الوصول إلى إصدارات سابقة من المصفوفة. ويعرض هذا القسم بنية معطيات تمتلك هذه الخاصة.

تتضمن الفكرة الأساسية استعمال مصفوفة لأحدث إصدار من المصفوفة الدائمة، إلى جانب معلومات إضافية تتيح لنا العودة إلى الإصدارات السابقة. وتحقيقًا لهذه الغاية، نُعرّف النوعين العوديين المتقابلين الآتيين:

  type ’a t = ’a data ref
  and ’a data =
    | Arr of ’a array
    | Diff of int * ’a * ’a t

النوع ’at هو نوع المصفوفات الدائمة. وهو يتضمن مرجعًا إلى معطيات من النوع ’adata، تدلّ على طبيعتها: إما قيمة مباشرة Arr a، حيث a مصفوفة، وإما إحالة (indirection) Diff (i,v,p)، تمثّل مصفوفة دائمة مطابقة عنصرًا بعنصر للمصفوفة الدائمة p، باستثناء الفهرس i حيث توجد القيمة v.

نوضّح استعمال بنية المعطيات هذه بمثال. خُذ سلسلة التعريفات الآتية التي تعرّف مصفوفة دائمة pa0، ثم مصفوفتين أخريين، pa1 وpa2، نحصل عليهما بتحديثين متتاليين:

  let pa0 = init 7 (fun i -> Char.chr (Char.code ’a’ + i))
  let pa1 = set pa0 1 ’h’
  let pa2 = set pa1 2 ’i’

تكون الحالة بعد هذه التعريفات الثلاثة كما يلي:

آخر مصفوفة دائمة بُنيت، pa2، هي مرجع يحتوي على القيمة Arr[|’a’;’h’;’i’;’d’;’e’;’f’;’g’|]. والمصفوفة الدائمة pa1 مرجع يحتوي على Diff(2,’c’,pa2)، والمصفوفة pa0 مرجع يحتوي على Diff(1,’b’,pa1). ولنفترض الآن أننا نبني مصفوفة رابعة pa3 كما يلي:

  let pa3 = set pa1 2 ’j’

نعمل على خطوتين: نبدأ بالتأكد من أن المصفوفة الدائمة التي نُجري عليها العملية، pa1، من الشكل Arra. ولهذا نعكس سلسلة عقد Diff التي تؤدي من pa1 إلى المصفوفة a. فتصبح لدينا الحالة الآتية:

وفي الخطوة الثانية، نُنشئ مرجعًا جديدًا لـ pa3، يحتوي على Arra، حيث عُدّلت a لتحتوي على ’j’ في الخلية الثانية. وننتهي بتعديل المرجع pa1 بحيث يحتوي الآن على Diff(2,’c’,pa3). وتكون الحالة النهائية إذن كما يلي:

سنصف الآن شفرة العمليات المختلفة على المصفوفات الدائمة. وإنشاء مصفوفة دائمة جديدة مباشر:

  let init n f = ref (Arr (Array.init n f))

بالنسبة لجميع العمليات الأخرى، نحتاج إلى دالة reroot لعكس سلسلة عقد Diff بما يضمن أن المصفوفة الدائمة pa من الشكل Arr a. ونكتبها كدالة عودية reroot:’at->’aarray تضمن هذا العكس للمؤشرات وتعيد المصفوفة a. فإذا كان pa مرجعًا لقيمة من الشكل Arra، كفى إعادة a.

  let rec reroot pa = match !pa with
    | Arr a ->
        a

أما إذا كان pa مرجعًا لقيمة من الشكل Diff(i,v,pa’)، فإننا نبدأ باستدعاء reroot عوديًّا على المصفوفة الدائمة pa’.

    | Diff (i, v, pa’) ->
        let a = reroot pa’ in

وعندئذ يُضمن أن pa’ مرجع يحتوي على Arra. ويكفي الآن تبادل دوري pa’ وpa، أي تخزين القيمة Arr a في pa، بعد تعديل a في مكانها، وتخزين قيمة Diff في pa’ تدلّ على القيمة السابقة التي كانت في a.

        let old = a.(i) in
        a.(i) <- v;
        pa := Arr a;
        pa’ := Diff (i, old, pa);
        a

تعريفا العمليتين length وget مباشران إذا استعملنا مكافئيهما في الوحدة Array مع الدالة reroot.

  let length pa = Array.length (reroot pa)
  let get pa i = (reroot pa).(i)

وتُنفَّذ العملية iteri باستعمال الدالة Array.iteri، التي تطبّق دالة على جميع عناصر مصفوفة وعلى فهارسها.

  let iteri f pa = Array.iteri f (reroot pa)

وتبقى الدالة set بحاجة إلى كتابة. وهي تبني مصفوفة دائمة جديدة انطلاقًا من مصفوفة دائمة موجودة pa، وفهرس i، وقيمة v. ونبدأ باستدعاء reroot على pa.

  let set pa i v =
    let a = reroot pa in

ثم نتابع كما فعلنا في حالة الدالة reroot، لكننا نُنشئ مرجعًا جديدًا للناتج:

    let old = a.(i) in
    a.(i) <- v;
    let res = ref (Arr a) in
    pa := Diff (i, old, res);
    res

لاحظ أنه في نهاية هذه العملية، تكون المصفوفة الدائمة pa على إحالة واحدة من المصفوفة Arra. والشفرة الكاملة للمصفوفات الدائمة معطاة في البرنامج 31.

  module type Stack = sig
    type ’a t
    val make : int -> ’a -> ’a t
    val length : ’a t -> int
    val push : ’a t -> ’a -> unit
    val pop : ’a t -> ’a
  end

  module Bitset : Set.S type elt = int

  val balance : t -> t