البرمجة من الرتبة العليا

4. البرمجة من الرتبة العليا

الدوال قيم كأي قيمة أخرى في OCaml. وماذا يعني ذلك بالضبط؟ يعني أننا نستطيع تمرير الدوال كوسائط إلى دوال أخرى، وأننا نستطيع تخزين الدوال في بنى بيانات، وأننا نستطيع إعادة الدوال كنتيجة من دوال أخرى، وهكذا.

الدوال من الرتبة العليا (higher-order functions) إما تأخذ دوال أخرى كمدخل أو تعيد دوال أخرى كمخرج (أو كليهما معًا). وتُعرف الدوال من الرتبة العليا أيضًا باسم الدواليات (functionals)، ولذا يمكن تسمية البرمجة بها البرمجة الوظيفية — بما يدل على جوهر البرمجة في لغات مثل OCaml.

كانت الدوال من الرتبة العليا من أحدث ما تبنّته اللغات السائدة من اللغات الوظيفية. ومن الأمثلة على ذلك مكتبة Java 8 Streams ووحدات itertools في Python 2.3؛ كما تزيد C++ دعمها لها منذ عام 2011 على الأقل.

ملاحظة

قد يعترض سحرة C بأن هذا التبنّي ليس حديثًا إلى هذا الحد. فبعد كل شيء، تمتلك C منذ زمن طويل القدرة على البرمجة من الرتبة العليا عبر مؤشرات الدوال. لكن تلك القدرة تعتمد أيضًا على نمط برمجي يقوم بتمرير معامل بيئة (environment) إضافي لتوفير قيم المتغيرات في الدالة التي ستُستدعى عبر المؤشر. وكما سنرى في فصلنا اللاحق عن المفسّرات، فإن جوهر الدوال (من الرتبة العليا) في لغة وظيفية أنها في الحقيقة شيء يسمى إغلاقًا (closure) يغني عن الحاجة إلى ذلك المعامل الإضافي. وضع في اعتبارك أن المسألة ليست ما يمكن حسابه بلغة ما — ففي النهاية يُصرَّف كل شيء إلى شيفرة الآلة، فيمكننا ببساطة الكتابة بها حصرًا — بل ما هو ممتع الحساب بها.

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

4.1. الدوال من الرتبة العليا

انظر إلى الدالتين double وsquare على الأعداد الصحيحة:

let double x = 2 * x
let square x = x * x

val double : int -> int = <fun>

val square : int -> int = <fun>

لنستخدم هاتين الدالتين لكتابة دالتين أخريين تضاعفان العدد أربع مرات وترفعانه إلى القوة الرابعة:

let quad x = double (double x)
let fourth x = square (square x)

val quad : int -> int = <fun>

val fourth : int -> int = <fun>

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

let twice f x = f (f x)

val twice : ('a -> 'a) -> 'a -> 'a = <fun>

الدالة twice من الرتبة العليا: فمدخلها f دالة. وبما أننا نتذكر أن جميع دوال OCaml تأخذ في الحقيقة وسيطًا واحدًا فقط، فمخرجها تقنيًا هو fun x -> f (f x)، لذا تعيد twice دالة، ومن ثم فهي من الرتبة العليا من هذه الناحية أيضًا.

وباستخدام twice، يمكننا تنفيذ quad وfourth بطريقة موحّدة:

let quad x = twice double x
let fourth x = twice square x

val quad : int -> int = <fun>

val fourth : int -> int = <fun>

4.1.1. مبدأ التجريد

أعلاه، استغللنا التشابه البنيوي بين quad وfourth لتوفير الجهد. ومع التسليم بأنه قد لا يبدو جهدًا كبيرًا في هذا المثال اللعبة. لكن تخيّل أن twice كانت في الواقع دالة أكثر تعقيدًا بكثير. عندئذ، لو جاء أحدهم بنسخة أكثر كفاءة منها، لاستفادت كل دالة مكتوبة بدلالتها (مثل quad وfourth) من ذلك التحسن في الكفاءة، دون حاجة إلى إعادة كتابتها.

وجزء من كونك مبرمجًا ممتازًا هو إدراك مثل هذه التشابهات وتجريدها بإنشاء دوال (أو وحدات شيفرة أخرى) تنفّذها. ويسمي بروس ماكلينان هذا مبدأ التجريد (Abstraction Principle) في كتابه Functional Programming: Theory and Practice (1990). ويقول مبدأ التجريد إنه ينبغي تجنّب اشتراط قول شيء ما أكثر من مرة؛ بل استخلص النمط المتكرر. وتتيح الدوال من الرتبة العليا إعادة الهيكلة هذه، لأنها تسمح لنا باستخلاص الدوال وجعل الدوال تتضمن معاملات هي دوال أخرى.

وإلى جانب twice، إليك بعض الأمثلة الأخرى البسيطة نسبيًا، وعليها أيضًا فضل لماكلينان:

Apply. يمكننا كتابة دالة تطبّق مدخلها الأول على مدخلها الثاني:

let apply f x = f x

val apply : ('a -> 'b) -> 'a -> 'b = <fun>

بالطبع، كتابة apply f عمل أكبر بكثير من كتابة f فحسب.

خط الأنابيب. مؤثر خط الأنابيب، الذي رأيناه سابقًا، دالة من الرتبة العليا:

let pipeline x f = f x
let (|>) = pipeline
let x = 5 |> double

val pipeline : 'a -> ('a -> 'b) -> 'b = <fun>

val ( |> ) : 'a -> ('a -> 'b) -> 'b = <fun>

val x : int = 10

Compose. يمكننا كتابة دالة تركّب دالتين أخريين:

let compose f g x = f (g x)

val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

ستتيح لنا هذه الدالة إنشاء دالة جديدة يمكن تطبيقها مرات كثيرة، مثل التالية:

let square_then_double = compose double square
let x = square_then_double 1
let y = square_then_double 2

val square_then_double : int -> int = <fun>

val x : int = 2

val y : int = 8

Both. يمكننا كتابة دالة تطبّق دالتين على الوسيط نفسه وتعيد زوجًا من النتيجتين:

let both f g x = (f x, g x)
let ds = both double square
let p = ds 3

val both : ('a -> 'b) -> ('a -> 'c) -> 'a -> 'b * 'c = <fun>

val ds : int -> int * int = <fun>

val p : int * int = (6, 9)

Cond. يمكننا كتابة دالة تختار شرطيًا أي الدالتين ستطبّق بناءً على محمول (predicate):

let cond p f g x =
  if p x then f x else g x

val cond : ('a -> bool) -> ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b = <fun>

4.1.2. معنى «الرتبة العليا»

تُستخدم عبارة «الرتبة العليا» في المنطق وعلوم الحاسوب كله، وإن لم يكن لها بالضرورة معنى دقيق أو متسق في جميع الحالات.

في المنطق، يشير التكميم من الرتبة الأولى (first-order quantification) أساسًا إلى المُكمِّمين الكلي والوجودي ($\forall$ و$\exists$). وهذان يتيحان لك التكميم على مجال ما يهمنا، مثل الأعداد الطبيعية. لكن في أي تكميم معيّن، لنقل $\forall x$، يمثل المتغير المكمَّم عليه عنصرًا فرديًا من ذلك المجال، لنقل العدد الطبيعي 42.

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

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

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

4.1.3. دوال شهيرة من الرتبة العليا

في الأقسام القليلة التالية سنغوص في ثلاث من أشهر الدوال من الرتبة العليا: map وfilter وfold. وهذه دوال يمكن تعريفها لكثير من بنى البيانات، ومنها القوائم والأشجار. والفكرة الأساسية لكل منها هي:

• map تحوّل العناصر،
• وfilter تحذف العناصر، و
• fold تدمج العناصر.

4.2. Map

إليك دالتين قد نريد كتابتهما:

(** [add1 lst] adds 1 to each element of [lst]. *)
let rec add1 = function
  | [] -> []
  | h :: t -> (h + 1) :: add1 t
let lst1 = add1 [1; 2; 3]

val add1 : int list -> int list = <fun>

val lst1 : int list = [2; 3; 4]

(** [concat_bang lst] concatenates "!" to each element of [lst]. *)
let rec concat_bang = function
  | [] -> []
  | h :: t -> (h ^ "!") :: concat_bang t
let lst2 = concat_bang ["sweet"; "salty"]

val concat_bang : string list -> string list = <fun>

val lst2 : string list = ["sweet!"; "salty!"]

هناك تشابه كبير بين هاتين الدالتين:

• كلتاهما تطابق نمطيًا قائمة.
• كلتاهما تعيد القيمة نفسها في الحالة الأساسية للقائمة الفارغة.
• كلتاهما تتعاود على الذيل في حالة القائمة غير الفارغة.

بل إن الفرق الوحيد (عدا اسميهما) هو ما تفعلانه بعنصر الرأس: الجمع مقابل الدمج. لنعد كتابة الدالتين لجعل ذلك الفرق أكثر وضوحًا:

(** [add1 lst] adds 1 to each element of [lst]. *)
let rec add1 = function
  | [] -> []
  | h :: t ->
    let f = fun x -> x + 1 in
    f h :: add1 t
(** [concat_bang lst] concatenates "!" to each element of [lst]. *)
let rec concat_bang = function
  | [] -> []
  | h :: t ->
    let f = fun x -> x ^ "!" in
    f h :: concat_bang t

val add1 : int list -> int list = <fun>

val concat_bang : string list -> string list = <fun>

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

let rec add1' f = function
  | [] -> []
  | h :: t -> f h :: add1' f t
(** [add1 lst] adds 1 to each element of [lst]. *)
let add1 = add1' (fun x -> x + 1)
let rec concat_bang' f = function
  | [] -> []
  | h :: t -> f h :: concat_bang' f t
(** [concat_bang lst] concatenates "!" to each element of [lst]. *)
let concat_bang = concat_bang' (fun x -> x ^ "!")

val add1' : ('a -> 'b) -> 'a list -> 'b list = <fun>

val add1 : int list -> int list = <fun>

val concat_bang' : ('a -> 'b) -> 'a list -> 'b list = <fun>

val concat_bang : string list -> string list = <fun>

لكن الآن لا يوجد في الحقيقة أي فرق على الإطلاق بين add1' وconcat_bang' إلا اسميهما. فهما شيفرة مكررة تمامًا. بل إن نوعيهما أصبحا متماثلين، لأن شيئًا فيهما لا يذكر الأعداد الصحيحة أو السلاسل النصية. فقد نكتفي بالإبقاء على واحدة منهما فحسب ونأتي باسم جديد جيد لها. ومن الاحتمالات اسم transform، لأنهما يحوّلان قائمة بتطبيق دالة على كل عنصر من عناصر القائمة:

let rec transform f = function
  | [] -> []
  | h :: t -> f h :: transform f t
(** [add1 lst] adds 1 to each element of [lst]. *)
let add1 = transform (fun x -> x + 1)
(** [concat_bang lst] concatenates "!" to each element of [lst]. *)
let concat_bang = transform (fun x -> x ^ "!")

val transform : ('a -> 'b) -> 'a list -> 'b list = <fun>

val add1 : int list -> int list = <fun>

val concat_bang : string list -> string list = <fun>

ملاحظة

بدلًا من

let add1 lst = transform (fun x -> x + 1) lst

أعلاه، كتبنا

let add1 = transform (fun x -> x + 1)

وهذه طريقة أخرى لكون الدالة من الرتبة العليا، لكنها طريقة تعلمناها بالفعل تحت غطاء التطبيق الجزئي. فطريقة كتابة الدالة الأخيرة تطبّق transform جزئيًا على وسيط واحد فحسب من وسيطيها، فتعيد دالة. وتلك الدالة تُربط بالاسم add1.

والواقع أن مكتبة C++ تسمي الدالة المكافئة transform. لكن OCaml ولغات أخرى كثيرة (منها Java وPython) تستخدم الكلمة الأقصر map، بالمعنى الرياضي لكيفية ربط دالة مدخلًا بمخرج. فلنُجرِ تغييرًا أخيرًا على ذلك الاسم:

let rec map f = function
  | [] -> []
  | h :: t -> f h :: map f t
(** [add1 lst] adds 1 to each element of [lst]. *)
let add1 = map (fun x -> x + 1)
(** [concat_bang lst] concatenates "!" to each element of [lst]. *)
let concat_bang = map (fun x -> x ^ "!")

val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

val add1 : int list -> int list = <fun>

val concat_bang : string list -> string list = <fun>

طبّقنا الآن مبدأ التجريد بنجاح: فاستُخلصت البنية المشتركة. وما تبقّى يعبّر بوضوح عن الحساب، على الأقل للقارئ المألوف بـ map، على نحو لا توضحه النسخ الأصلية بهذه السرعة.

4.2.1. الآثار الجانبية

توجد الدالة map بالفعل في المكتبة القياسية لـ OCaml باسم List.map، لكن مع فرق صغير عن التنفيذ الذي اكتشفناه أعلاه. أولًا، لنرَ ما قد يكون معيبًا في تنفيذنا، ثم سننظر في تنفيذ المكتبة القياسية.

رأينا سابقًا في مناقشتنا لـالاستثناءات أن مواصفة لغة OCaml لا تحدد عمومًا ترتيب تقييم التعبيرات الفرعية، وأن تنفيذ اللغة الحالي يقيّم عمومًا من اليمين إلى اليسار. وبسبب ذلك، تتسبب الشيفرة التالية (المتكلّفة نوعًا ما) فعليًا في طباعة عناصر القائمة بترتيب قد يبدو معكوسًا:

let p x = print_int x; print_newline(); x + 1
let lst = map p [1; 2]

val p : int -> int = <fun>

2

1

val lst : int list = [2; 3]

وإليك السبب:

• التعبير map p [1; 2] يقيّم إلى p 1 :: map p [2].
• ثم يقيّم الجانب الأيمن من ذلك التعبير إلى p 1 :: (p 2 :: map p []). ولم يحدث بعد تطبيق p على 1.
• ويقيّم بعد ذلك الجانب الأيمن من :: مرة أخرى، فينتج p 1 :: (p 2 :: []).
• ثم تُطبَّق p على 2، وأخيرًا على 1.

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

let rec map f = function
  | [] -> []
  | h :: t -> let h' = f h in h' :: map f t
let lst2 = map p [1; 2]

val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

1

2

val lst2 : int list = [2; 3]

وإليك سبب نجاح ذلك:

• التعبير map p [1; 2] يقيّم إلى let h' = p 1 in h' :: map p [2].
• يقيّم تعبير الربط p 1، فيُطبع 1 وتُربط h' بـ 2.
• ثم يقيّم تعبير الجسم h' :: map p [2]، فيؤدي ذلك إلى طباعة 2 بعد ذلك.

وهكذا تعرّف المكتبة القياسية List.map. وينبغي أن نستخدمها بدلًا من إعادة تعريف الدالة بأنفسنا من الآن فصاعدًا. لكن من الجيد أننا اكتشفنا الدالة «من الصفر» إن جاز التعبير، وأننا نستطيع إعادة كتابتها سريعًا إن احتجنا.

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

4.2.2. Map والتعاود الذيلي

سيلاحظ القراء الفطّن أن تنفيذ map ليس تعاوديًا ذليًا. وهذا لا مفر منه إلى حد ما. وإليك طريقة مغربة لكنها سيئة لإنشاء نسخة تعاودية ذيلية منه:

let rec map_tr_aux f acc = function
  | [] -> acc
  | h :: t -> map_tr_aux f (acc @ [f h]) t
let map_tr f = map_tr_aux f []
let lst = map_tr (fun x -> x + 1) [1; 2; 3]

val map_tr_aux : ('a -> 'b) -> 'b list -> 'a list -> 'b list = <fun>

val map_tr : ('a -> 'b) -> 'a list -> 'b list = <fun>

val lst : int list = [2; 3; 4]

يعمل ذلك إلى حد ما: فالمخرجات صحيحة، وmap_tr_aux تعاودية ذيلية. والعيب الخفي هو التعبير الفرعي acc @ [f h]. تذكّر أن الإلحاق عملية خطية الزمن على القوائم المترابطة أحادية الاتجاه. أي أنه إذا كان هناك $n$ من عناصر القائمة فإن الإلحاق يستغرق زمنًا $O(n)$. لذا ننفّذ في كل نداء تعاودي عملية $O(n)$. وسيكون هناك $n$ من النداءات التعاودية، نداء لكل عنصر من عناصر القائمة. أي مجموع قدره $n \cdot O(n)$ من العمل، وهو $O(n^2)$. فحققنا التعاود الذيلي، لكن بكلفة باهظة: ما كان ينبغي أن يكون عملية خطية الزمن أصبح تربيعي الزمن.

وفي محاولة لإصلاح ذلك، يمكننا استخدام عملية cons الثابتة الزمن بدلًا من عملية الإلحاق الخطية الزمن:

let rec map_tr_aux f acc = function
  | [] -> acc
  | h :: t -> map_tr_aux f (f h :: acc) t
let map_tr f = map_tr_aux f []
let lst = map_tr (fun x -> x + 1) [1; 2; 3]

val map_tr_aux : ('a -> 'b) -> 'b list -> 'a list -> 'b list = <fun>

val map_tr : ('a -> 'b) -> 'a list -> 'b list = <fun>

val lst : int list = [4; 3; 2]

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

ملاحظة

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

• المدخل: Alice، Bob.
• المخرج: فارغ.

ثم نزيل Alice من المدخل ونضيفها إلى المخرج:

• المدخل: Bob.
• المخرج: Alice.

ثم نزيل Bob من المدخل ونضيفه إلى المخرج:

• المدخل: فارغ.
• المخرج: Bob، Alice.

والنقطة هي أننا مع القوائم المترابطة أحادية الاتجاه لا نستطيع العمل إلا على رأس القائمة وأن نبقى في زمن ثابت. فلا يمكننا نقل Bob إلى مؤخرة المخرج دون أن يجتاز Alice — وأي شخص آخر قد يكون واقفًا في المخرج.

ولهذا السبب، تسمي المكتبة القياسية هذه الدالة List.rev_map، أي دالة map (تعاودية ذيلية) تعيد مخرجاتها بترتيب معكوس.

let rec rev_map_aux f acc = function
  | [] -> acc
  | h :: t -> rev_map_aux f (f h :: acc) t
let rev_map f = rev_map_aux f []
let lst = rev_map (fun x -> x + 1) [1; 2; 3]

val rev_map_aux : ('a -> 'b) -> 'b list -> 'a list -> 'b list = <fun>

val rev_map : ('a -> 'b) -> 'a list -> 'b list = <fun>

val lst : int list = [4; 3; 2]

وإذا أردت المخرجات بالترتيب «الصحيح»، فالأمر سهل: طبّق List.rev عليها فحسب:

let lst = List.rev (List.rev_map (fun x -> x + 1) [1; 2; 3])

val lst : int list = [2; 3; 4]

وبما أن List.rev خطية الزمن وتعاودية ذيلية معًا، فإن ذلك يعطي حلًا كاملًا. فنحصل على حساب map خطي الزمن وتعاودي ذيلي. والكلفة أنه يتطلب مرورين على القائمة: أحدهما للتحويل والآخر للعكس. ولن نصل إلى كفاءة أفضل من هذه مع قائمة مترابطة أحادية الاتجاه. وبالطبع، هناك بنى بيانات أخرى تنفّذ القوائم، وسنصل إليها في النهاية. وفي الأثناء، تذكّر أننا عمومًا لا نحتاج إلى القلق بشأن التعاود الذيلي (أي بشأن مساحة المكدّس) حتى تصل القوائم إلى 10,000 عنصر أو أكثر.

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

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

4.2.3. Map في لغات أخرى

ذكرنا أعلاه أن فكرة map موجودة في لغات برمجة كثيرة. وإليك مثالًا من Python:

>>> print(list(map(lambda x: x + 1, [1, 2, 3])))
[2, 3, 4]

علينا استخدام الدالة list لتحويل نتيجة map مرة أخرى إلى قائمة، لأن Python، من أجل الكفاءة، تنتج كل عنصر من مخرجات map عند الحاجة إليه. وهنا مرة أخرى نرى موضوع «متى تتم التقييم؟» يعود للظهور.

وفي Java، تعد map جزءًا من تجريد Stream الذي أُضيف في Java 8. وبما أنه لا توجد صياغة Java مدمجة للقوائم أو التدفقات، فإعطاء مثال يكون أكثر إسهابًا قليلًا. وهنا نستخدم دالة مصنع هي Stream.of لإنشاء تدفق:

jshell> Stream.of(1, 2, 3).map(x -> x + 1).collect(Collectors.toList())
$1 ==> [2, 3, 4]

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

4.3. Filter

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

(** [even n] is whether [n] is even. *)
let even n =
  n mod 2 = 0
(** [evens lst] is the sublist of [lst] containing only even numbers. *)
let rec evens = function
  | [] -> []
  | h :: t -> if even h then h :: evens t else evens t
let lst1 = evens [1; 2; 3; 4]

val even : int -> bool = <fun>

val evens : int list -> int list = <fun>

val lst1 : int list = [2; 4]

(** [odd n] is whether [n] is odd. *)
let odd n =
  n mod 2 <> 0
(** [odds lst] is the sublist of [lst] containing only odd numbers. *)
let rec odds = function
  | [] -> []
  | h :: t -> if odd h then h :: odds t else odds t
let lst2 = odds [1; 2; 3; 4]

val odd : int -> bool = <fun>

val odds : int list -> int list = <fun>

val lst2 : int list = [1; 3]

الدالتان evens وodds شيفرة متطابقة تقريبًا: والفرق الجوهري الوحيد هو الاختبار الذي تطبّقانه على عنصر الرأس. فلنستخلص، كما فعلنا مع map في القسم السابق، ذلك الاختبار كدالة. ولنسمِّ الدالة p اختصارًا لـ «predicate» (محمول)، وهي طريقة منمقة لقول إنها تختبر ما إذا كان شيء صحيحًا أم خاطئًا:

let rec filter p = function
  | [] -> []
  | h :: t -> if p h then h :: filter p t else filter p t

val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

والآن يمكننا إعادة تنفيذ دالتينا الأصليتين:

let evens = filter even
let odds = filter odd

val evens : int list -> int list = <fun>

val odds : int list -> int list = <fun>

ما أبسطهما! وما أوضحهما! (على الأقل للقارئ المألوف بـ filter.)

4.3.1. Filter والتعاود الذيلي

كما فعلنا مع map، يمكننا إنشاء نسخة تعاودية ذيلية من filter:

let rec filter_aux p acc = function
  | [] -> acc
  | h :: t -> if p h then filter_aux p (h :: acc) t else filter_aux p acc t
let filter p = filter_aux p []
let lst = filter even [1; 2; 3; 4]

val filter_aux : ('a -> bool) -> 'a list -> 'a list -> 'a list = <fun>

val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

val lst : int list = [4; 2]

ومرة أخرى نكتشف أن المخرجات معكوسة. وهنا تتخذ المكتبة القياسية خيارًا مختلفًا عمّا اتخذته مع map. فهي تبني العكس داخل List.filter، المنفّذة هكذا:

let rec filter_aux p acc = function
  | [] -> List.rev acc (* note the built-in reversal *)
  | h :: t -> if p h then filter_aux p (h :: acc) t else filter_aux p acc t
let filter p = filter_aux p []

val filter_aux : ('a -> bool) -> 'a list -> 'a list -> 'a list = <fun>

val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

ولماذا تعامل المكتبة القياسية map وfilter معاملة مختلفة في هذه النقطة؟ سؤال جيد. ربما لم يكن هناك ببساطة طلب على دالة filter تكون كفاءتها الزمنية أفضل بعامل ثابت. أو ربما هي مجرد مصادفة تاريخية.

4.3.2. Filter في لغات أخرى

مرة أخرى، فكرة filter موجودة في لغات برمجة كثيرة. وإليك إياها في Python:

>>> print(list(filter(lambda x: x % 2 == 0, [1, 2, 3, 4])))
[2, 4]

وفي Java:

jshell> Stream.of(1, 2, 3, 4).filter(x -> x % 2 == 0).collect(Collectors.toList())
$1 ==> [2, 4]

4.4. Fold

تمنحنا دالة map طريقة لتحويل كل عنصر من عناصر القائمة على حدة. وتمنحنا دالة filter طريقة لتقرير ما إذا كنا سنبقي على كل عنصر من عناصر القائمة أو نحذفه على حدة. لكن كلتيهما في الحقيقة تنظر إلى عنصر واحد في كل مرة فحسب. فماذا لو أردنا دمج جميع عناصر القائمة بطريقة ما؟ هذا ما وُجدت الدالة fold من أجله. وتبيّن أن لها نسختين، وسندرسهما في هذا القسم. لكن لنبدأ بالنظر إلى دالة ذات صلة — ليست فعلًا في المكتبة القياسية — نسميها combine.

4.4.1. Combine

مرة أخرى، لنكتب دالتين:

(** [sum lst] is the sum of all the elements of [lst]. *)
let rec sum = function
  | [] -> 0
  | h :: t -> h + sum t
let s = sum [1; 2; 3]

val sum : int list -> int = <fun>

val s : int = 6

(** [concat lst] is the concatenation of all the elements of [lst]. *)
let rec concat = function
  | [] -> ""
  | h :: t -> h ^ concat t
let c = concat ["a"; "b"; "c"]

val concat : string list -> string = <fun>

val c : string = "abc"

وكما في تماريننا المشابهة مع map وfilter، تتشارك الدالتان قدرًا كبيرًا من البنية المشتركة. والفرق هنا:

• حالة القائمة الفارغة تعيد قيمة أولية مختلفة، 0 مقابل ""
• حالة القائمة غير الفارغة تستخدم مؤثرًا مختلفًا لدمج عنصر الرأس مع نتيجة النداء التعاودي، + مقابل ^.

فهل يمكننا تطبيق مبدأ التجريد مرة أخرى؟ بالتأكيد! لكننا هذه المرة نحتاج إلى استخلاص وسيطين: واحد لكل من هذين الفرقين.

لنبدأ باستخلاص القيمة الأولية فحسب:

let rec sum' init = function
  | [] -> init
  | h :: t -> h + sum' init t
let sum = sum' 0
let rec concat' init = function
  | [] -> init
  | h :: t -> h ^ concat' init t
let concat = concat' ""

val sum' : int -> int list -> int = <fun>

val sum : int list -> int = <fun>

val concat' : string -> string list -> string = <fun>

val concat : string list -> string = <fun>

الآن الفرق الحقيقي الوحيد المتبقي بين sum' وconcat' هو المؤثر المستخدم لدمج الرأس مع النداء التعاودي على الذيل. ويمكن أن يصبح ذلك المؤثر أيضًا وسيطًا لدالة موحّدة نسميها combine:

let rec combine op init = function
  | [] -> init
  | h :: t -> op h (combine op init t)
let sum = combine ( + ) 0
let concat = combine ( ^ ) ""

val combine : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>

val sum : int list -> int = <fun>

val concat : string list -> string = <fun>

وإحدى طرق التفكير في combine هي أنها:

• تستبدل القيمة [] في القائمة بـ init، و
• تستبدل كل منشئ :: بـ op.

على سبيل المثال، [a; b; c] مجرد سكر صياغي لـ a :: (b :: (c :: [])). لذا إذا استبدلنا [] بـ 0 و:: بـ (+)، نحصل على a + (b + (c + 0)). ويكون ذلك مجموع القائمة.

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

4.4.2. الطي نحو اليمين (Fold Right)

دالة combine هي الفكرة الكامنة وراء دالة فعلية من مكتبة OCaml. وللوصول إليها، نحتاج إلى إجراء تغييرين على التنفيذ الذي لدينا حتى الآن.

أولًا، لنعد تسمية بعض الوسائط: سنغيّر op إلى f للتأكيد على أننا في الحقيقة نستطيع تمرير أي دالة، لا مجرد مؤثر مدمج مثل +. وسنغيّر init إلى acc، وهو كما هي العادة اختصار لـ «accumulator» (المجمِّع). فينتج:

let rec combine f acc = function
  | [] -> acc
  | h :: t -> f h (combine f acc t)

val combine : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>

ثانيًا، لنجرِ تغييرًا أقل تبريرًا كما نعترف. سنبادل وسيط القائمة الضمني لـ combine بوسيط init:

let rec combine' f lst acc = match lst with
  | [] -> acc
  | h :: t -> f h (combine' f t acc)
let sum lst = combine' ( + ) lst 0
let concat lst = combine' ( ^ ) lst ""

val combine' : ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b = <fun>

val sum : int list -> int = <fun>

val concat : string list -> string = <fun>

برمجة الدالة بهذه الطريقة أقل ملاءمة قليلًا، لأننا لم نعد نستفيد من الكلمة المفتاحية function، ولا من التطبيق الجزئي في تعريف sum وconcat. لكن لا يوجد تغيير خوارزمي.

وما لدينا الآن هو التنفيذ الفعلي لدالة المكتبة القياسية List.fold_right. كل ما بقي علينا فعله هو تغيير اسم الدالة وإضافة تعليق نوعي يدوي:

let rec fold_right f lst (acc : 'acc) = match lst with
  | [] -> acc
  | h :: t -> f h (fold_right f t acc)

val fold_right : ('a -> 'acc -> 'acc) -> 'a list -> 'acc -> 'acc = <fun>

ولماذا تسمى هذه الدالة «الطي نحو اليمين»؟ الحدس هو أن طريقة عملها هي «الطي للداخل» لعناصر القائمة من اليمين إلى اليسار، بدمج كل عنصر جديد باستخدام المؤثر. على سبيل المثال، ينتج عن fold_right ( + ) [a; b; c] 0 تقييم التعبير a + (b + (c + 0)). والأقواس تترابط من التعبير الفرعي الأقصى يمينًا إلى اليسار.

ملاحظة

التعليق النوعي اليدوي ليس ضروريًا لتنفيذ صحيح للدالة. والغرض منه توفير نوع أجمل. فبدون التعليق، سيكون النوع المستنتج لـ fold_right هو ('a -> 'b -> 'b) -> 'a list -> 'b -> 'b، حيث يختار المصرّف 'b نوعًا للمجمِّع. وبتعليق ذلك الوسيط يدويًا باسم وصفي لذاته، نحصل على النوع الأكثر قابلية للقراءة ('a -> 'acc -> 'acc) -> 'a list -> 'acc -> 'acc.

4.4.3. التعاود الذيلي وCombine

لا fold_right ولا combine تعاودية ذيلية: فبعد عودة النداء التعاودي، لا يزال هناك عمل يجب إجراؤه في تطبيق الوسيط الدالي f أو op. لنعد إلى combine ونعد كتابتها لتكون تعاودية ذيلية. وكل ما يتطلبه ذلك هو تغيير فرع cons:

let rec combine_tr f acc = function
  | [] -> acc
  | h :: t -> combine_tr f (f acc h) t  (* only real change *)

val combine_tr : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

(سيلاحظ القراء المتيقظون أن نوع combine_tr مختلف عن نوع combine. وسنتناول ذلك قريبًا.)

الآن تُطبَّق الدالة f على عنصر الرأس h والمجمِّع acc قبل إجراء النداء التعاودي، مما يضمن عدم بقاء أي عمل يجب إجراؤه بعد عودة النداء. وإن بدا ذلك غامضًا بعض الشيء، فإليك إعادة كتابة للدالتين قد تساعد:

let rec combine f acc = function
  | [] -> acc
  | h :: t ->
    let acc' = combine f acc t in
    f h acc'
let rec combine_tr f acc = function
  | [] -> acc
  | h :: t ->
    let acc' = f acc h in
    combine_tr f acc' t

val combine : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>

val combine_tr : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

انتبه جيدًا إلى تعريف acc'، المجمِّع الجديد، في كل من هاتين النسختين:

• في النسخة الأصلية، نؤجّل استخدام عنصر الرأس h. فندمج أولًا جميع عناصر الذيل المتبقية لنحصل على acc'. وعندها فقط نستخدم f لطي الرأس للداخل. لذا فالقيمة الممرَّرة كقيمة أولية لـ acc تكون هي نفسها في كل استدعاء تعاودي لـ combine: فهي تمرَّرت نزولًا حتى موضع الحاجة إليها، عند العنصر الأقصى يمينًا في القائمة، ثم تُستخدم هناك مرة واحدة بالضبط.
• أما في النسخة التعاودية الذيلية، فنحن «نُقدّم» فورًا بطي h باستخدام المجمِّع القديم acc. ثم نطوي ذلك مع جميع عناصر الذيل. لذا ففي كل استدعاء تعاودي، يمكن أن تكون القيمة الممرَّرة كوسيط acc مختلفة.

تعمل النسخة التعاودية الذيلية من combine بشكل جيد تمامًا في الجمع (والدمج، الذي نحذفه):

let sum = combine_tr ( + ) 0
let s = sum [1; 2; 3]

val sum : int list -> int = <fun>

val s : int = 6

لكن شيئًا قد يكون مفاجئًا يحدث مع الطرح:

let sub = combine ( - ) 0
let s = sub [3; 2; 1]
let sub_tr = combine_tr ( - ) 0
let s' = sub_tr [3; 2; 1]

val sub : int list -> int = <fun>

val s : int = 2

val sub_tr : int list -> int = <fun>

val s' : int = -6

النتيجتان مختلفتان!

• مع combine نحسب 3 - (2 - (1 - 0)). فنطوي أولًا 1، ثم 2، ثم 3. أي أننا نعالج القائمة من اليمين إلى اليسار، ونضع المجمِّع الأولي في أقصى اليمين.
• أما مع combine_tr فنجري الحساب (((0 - 3) - 2) - 1). أي أننا نعالج القائمة من اليسار إلى اليمين، ونضع المجمِّع الأولي في أقصى اليسار.

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

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

4.4.4. الطي نحو اليسار (Fold Left)

دالتنا combine_tr موجودة أيضًا في المكتبة القياسية باسم List.fold_left:

let rec fold_left f (acc : 'acc) = function
  | [] -> acc
  | h :: t -> fold_left f (f acc h) t
let sum = fold_left ( + ) 0
let concat = fold_left ( ^ ) ""

val fold_left : ('acc -> 'a -> 'acc) -> 'acc -> 'a list -> 'acc = <fun>

val sum : int list -> int = <fun>

val concat : string list -> string = <fun>

لقد نجحنا مرة أخرى في تطبيق مبدأ التجريد.

4.4.5. الطي نحو اليسار مقابل الطي نحو اليمين

لنراجع الفروق بين fold_right وfold_left:

• إنهما تدمجان عناصر القائمة بترتيبين متعاكسين، كما يشير اسماهما. فالدالة fold_right تدمج من اليمين إلى اليسار، بينما تمضي fold_left من اليسار إلى اليمين.
• الدالة fold_left تعاودية ذيلية بينما fold_right ليست كذلك.
• نوعا الدالتين مختلفان. ففي fold_X يذهب وسيط المجمِّع إلى موضع X من وسيط القائمة. وهذا خيار اتخذته المكتبة القياسية لا فرق تنفيذي ضروري.

وإذا وجدت صعوبة في تتبّع ترتيب الوسائط، فقد تساعدك وحدة ListLabels في المكتبة القياسية. فهي تستخدم وسائط مسمّاة لإعطاء أسماء لمؤثر الدمج (الذي تسميه f) والقيمة الأولية للمجمِّع (التي تسميها init). أما داخليًا، فالتنفيذ في الواقع مطابق لتنفيذ وحدة List.

ListLabels.fold_left ~f:(fun x y -> x - y) ~init:0 [1; 2; 3];;

- : int = -6

ListLabels.fold_right ~f:(fun y x -> x - y) ~init:0 [1; 2; 3];;

- : int = -6

لاحظ كيف تمكّنا في تطبيقي fold أعلاه من كتابة الوسائط بترتيب موحّد بفضل تسمياتها. ومع ذلك، لا يزال علينا الحذر بشأن أي وسيط لمؤثر الدمج هو عنصر القائمة وأيّها قيمة المجمِّع.

4.4.6. استطراد عن الوسائط المسمّاة وFold

من الممكن كتابة نسختنا الخاصة من دالتي fold تسمّي وسائط مؤثر الدمج، فلا نضطر حتى إلى تذكّر ترتيبها:

let rec fold_left ~op:(f: acc:'a -> elt:'b -> 'a) ~init:acc lst =
  match lst with
  | [] -> acc
  | h :: t -> fold_left ~op:f ~init:(f ~acc:acc ~elt:h) t
let rec fold_right ~op:(f: elt:'a -> acc:'b -> 'b) lst ~init:acc =
  match lst with
  | [] -> acc
  | h :: t -> f ~elt:h ~acc:(fold_right ~op:f t ~init:acc)

val fold_left : op:(acc:'a -> elt:'b -> 'a) -> init:'a -> 'b list -> 'a =
  <fun>

val fold_right : op:(elt:'a -> acc:'b -> 'b) -> 'a list -> init:'b -> 'b =
  <fun>

لكن هاتين الدالتين ليستا مفيدتين كما قد تبدوان:

let s = fold_left ~op:( + ) ~init:0 [1;2;3]

File "[16]", line 1, characters 22-27:
1 | let s = fold_left ~op:( + ) ~init:0 [1;2;3]
                          ^^^^^
Error: The value (+) has type int -> int -> int
       but an expression was expected of type acc:'a -> elt:'b -> 'a
       A label acc was expected

المشكلة أن المؤثر المدمج + ليس له وسائط مسمّاة، لذا لا يمكننا تمريره كمؤثر دمج إلى دوالنا المسمّاة. وسنضطر إلى تعريف نسختنا المسمّاة منه:

let add ~acc ~elt = acc + elt
let s = fold_left ~op:add ~init:0 [1; 2; 3]

لكن علينا الآن أن نتذكر أن المعامل ~acc في add سيصبح الوسيط الأيسر لـ ( + ). وهذا ليس تحسنًا كبيرًا فعلًا عمّا كان علينا تذكّره في البداية.

4.4.7. استخدام Fold لتنفيذ دوال أخرى

الطي قوي إلى حد أننا نستطيع كتابة دوال قوائم كثيرة أخرى بدلالة fold_left أو fold_right. على سبيل المثال،

let length lst =
  List.fold_left (fun acc _ -> acc + 1) 0 lst
let rev lst =
  List.fold_left (fun acc x -> x :: acc) [] lst
let map f lst =
  List.fold_right (fun x acc -> f x :: acc) lst []
let filter f lst =
  List.fold_right (fun x acc -> if f x then x :: acc else acc) lst []

val length : 'a list -> int = <fun>

val rev : 'a list -> 'a list = <fun>

val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

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

4.4.8. Fold مقابل التعاود مقابل المكتبة

رأينا الآن ثلاث طرق مختلفة لكتابة الدوال التي تتعامل مع القوائم:

• مباشرةً كدالة تعاودية تطابق نمطيًا القائمة الفارغة وcons،
• باستخدام دوال fold، و
• باستخدام دوال مكتبة أخرى.

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

فكّر في كتابة دالة lst_and: bool list -> bool، بحيث تعيد lst_and [a1; ...; an] ما إذا كانت جميع عناصر القائمة true. أي أنها تقيّم مثل a1 && a2 && ... && an. وعند تطبيقها على قائمة فارغة، تقيّم إلى true.

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

let rec lst_and_rec = function
  | [] -> true
  | h :: t -> h && lst_and_rec t
let lst_and_fold =
	List.fold_left (fun acc elt -> acc && elt) true
let lst_and_lib =
	List.for_all (fun x -> x)

val lst_and_rec : bool list -> bool = <fun>

val lst_and_fold : bool list -> bool = <fun>

val lst_and_lib : bool list -> bool = <fun>

زمن تشغيل الدوال الثلاث في أسوأ الحالات خطي في طول القائمة. لكن:

• للدالة الأولى، lst_and_rec، ميزة أنها لا تحتاج إلى معالجة القائمة بأكملها. فهي تعيد false فورًا عند أول اكتشافها عنصرًا false في القائمة.
• أما الدالة الثانية، lst_and_fold، فستعالج دائمًا كل عنصر من عناصر القائمة.
• وأما الدالة الثالثة، lst_and_lib، فوفقًا لتوثيق List.for_all، تعيد (p a1) && (p a2) && ... && (p an). لذا فهي، مثل lst_and_rec، لا تحتاج إلى معالجة كل عنصر.

4.5. ما بعد القوائم

لا تقتصر الدواليات مثل map وfold على القوائم. فهي ذات معنى مع أي نوع تقريبًا من تجميعات البيانات. على سبيل المثال، تذكّر تمثيل الشجرة هذا:

type 'a tree =
  | Leaf
  | Node of 'a * 'a tree * 'a tree

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

4.5.1. Map على الأشجار

هذه سهلة. كل ما علينا فعله هو تطبيق الدالة f على القيمة v في كل عقدة:

let rec map_tree f = function
  | Leaf -> Leaf
  | Node (v, l, r) -> Node (f v, map_tree f l, map_tree f r)

val map_tree : ('a -> 'b) -> 'a tree -> 'b tree = <fun>

4.5.2. Fold على الأشجار

هذه أصعب قليلًا فحسب. لنطوّر دالة fold لـ 'a tree شبيهة بـ fold_right لدينا على 'a list. وإحدى طرق التفكير في List.fold_right هي أن القيمة [] في القائمة تُستبدل بالوسيط acc، وأن كل منشئ :: يُستبدل بتطبيق للوسيط f. على سبيل المثال، [a; b; c] سكر صياغي لـ a :: (b :: (c :: [])). لذا إذا استبدلنا [] بـ 0 و:: بـ ( + )، نحصل على a + (b + (c + 0)). وعلى هذا المنوال، إليك طريقة يمكننا بها إعادة كتابة fold_right تساعدنا على التفكير بوضوح أكبر قليلًا:

type 'a mylist =
  | Nil
  | Cons of 'a * 'a mylist
let rec fold_mylist f acc = function
  | Nil -> acc
  | Cons (h, t) -> f h (fold_mylist f acc t)

type 'a mylist = Nil | Cons of 'a * 'a mylist

val fold_mylist : ('a -> 'b -> 'b) -> 'b -> 'a mylist -> 'b = <fun>

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

وفي الأشجار، سنريد أن تستبدل القيمة الأولية لـ acc كل منشئ Leaf، تمامًا كما استبدلت [] في القوائم. وسنريد أن يستبدل كل منشئ Node بالمؤثر. لكن المؤثر سيحتاج الآن إلى أن يكون ثلاثيًا بدلًا من ثنائي — أي سيحتاج إلى أخذ ثلاثة وسائط بدلًا من اثنين — لأن عقدة الشجرة لها قيمة وطفل أيسر وطفل أيمن، بينما كان cons في القائمة له رأس وذيل فقط.

واستلهامًا من تلك الملاحظات، إليك دالة fold على الأشجار:

let rec fold_tree f acc = function
  | Leaf -> acc
  | Node (v, l, r) -> f v (fold_tree f acc l) (fold_tree f acc r)

val fold_tree : ('a -> 'b -> 'b -> 'b) -> 'b -> 'a tree -> 'b = <fun>

وإذا قارنت تلك الدالة بـ fold_mylist، فستلاحظ أنها تكاد تكون مطابقة لها. فلا يزيد الأمر إلا عن نداء تعاودي واحد في فرع التطابق النمطي الثاني، مقابل وجود إضافي واحد لـ 'a tree في تعريف ذلك النوع.

ويمكننا بعدها استخدام fold_tree لتنفيذ بعض دوال الأشجار التي رأيناها سابقًا:

let size t = fold_tree (fun _ l r -> 1 + l + r) 0 t
let depth t = fold_tree (fun _ l r -> 1 + max l r) 0 t
let preorder t = fold_tree (fun x l r -> [x] @ l @ r) [] t

val size : 'a tree -> int = <fun>

val depth : 'a tree -> int = <fun>

val preorder : 'a tree -> 'a list = <fun>

ولماذا اخترنا fold_right لا fold_left لهذا التطوير؟ لأن fold_left تعاودية ذيلية، وهو أمر لن نحققه أبدًا على الأشجار الثنائية. افترض أننا عالجنا الفرع الأيسر أولًا؛ فسيظل علينا بعد ذلك معالجة الفرع الأيمن قبل أن نتمكن من العودة. لذا سيكون هناك دائمًا عمل متبقٍ يجب إجراؤه بعد النداء التعاودي على أحد الفرعين. وبذلك، يكون مكافئ fold_right هو أفضل ما نطمح إليه في الأشجار.

والتقنية التي استخدمناها لاشتقاق fold_tree تعمل مع أي نوع متغاير t في OCaml:

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

وتبني هذه التقنية شيئًا يسمى كاتامورفيزم (catamorphism)، أي عملية طي معمّمة. ولمعرفة المزيد عن الكاتامورفيزمات، خذ مقررًا في نظرية الفئات (category theory).

4.5.3. Filter على الأشجار

هذه ربما أصعبها تصميمًا. فالمشكلة هي: إذا قررنا ترشيح عقدة، فماذا نفعل بأطفالها؟

• يمكننا التعاود على الأطفال. فإذا لم يبقَ بعد ترشيحهم إلا طفل واحد، أمكننا ترقيته ليحل محل والده. لكن ماذا لو بقي الطفلان معًا، أو لم يبقَ أي منهما؟ عندئذ سيتعين علينا إعادة تشكيل الشجرة بطريقة ما. ومن دون معرفة المزيد عن كيفية استعمال الشجرة — أي نوع البيانات الذي تمثله — نكون متعطلين.
• وبدلًا من ذلك، يمكننا ببساطة إزالة الأطفال كليًا. فيكون قرار ترشيح عقدة يعني تقليم الشجرة الفرعية كلها المتجذرة عند تلك العقدة.

والاحتمال الأخير سهل التنفيذ:

let rec filter_tree p = function
  | Leaf -> Leaf
  | Node (v, l, r) ->
    if p v then Node (v, filter_tree p l, filter_tree p r) else Leaf

val filter_tree : ('a -> bool) -> 'a tree -> 'a tree = <fun>

4.6. خطوط الأنابيب

افترض أننا أردنا حساب مجموع مربعات الأعداد من 0 حتى $n$. كيف قد نفعل ذلك؟ بالطبع (والرياضيات أفضل أشكال التحسين)، ستكون الطريقة الأكثر كفاءة صيغة مغلقة:

لكن لنتخيل أنك نسيت تلك الصيغة. في لغة أمرية قد تستخدم حلقة for:

# Python
def sum_sq(n):
	sum = 0
	for i in range(0, n+1):
		sum += i * i
	return sum

وتكون الشيفرة التعاودية (الذيلية) المكافئة في OCaml:

let sum_sq n =
  let rec loop i sum =
    if i > n then sum
    else loop (i + 1) (sum + i * i)
  in loop 0 0

val sum_sq : int -> int = <fun>

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

let rec ( -- ) i j = if i > j then [] else i :: i + 1 -- j
let square x = x * x
let sum = List.fold_left ( + ) 0
let sum_sq n =
  0 -- n              (* [0;1;2;...;n]   *)
  |> List.map square  (* [0;1;4;...;n*n] *)
  |> sum              (*  0+1+4+...+n*n  *)

val ( -- ) : int -> int -> int list = <fun>

val square : int -> int = <fun>

val sum : int list -> int = <fun>

val sum_sq : int -> int = <fun>

تنشئ الدالة sum_sq أولًا قائمة تحتوي على جميع الأعداد 0..n. ثم تستخدم مؤثر خط الأنابيب |> لتمرير تلك القائمة عبر List.map square، الذي يربّع كل عنصر. ثم تمر القائمة الناتجة عبر خط أنابيب إلى sum، الذي يجمع جميع العناصر معًا.

أما البدائل الأخرى التي قد تفكر فيها فهي أقبح بعض الشيء:

(* Maybe worse: a lot of extra [let..in] syntax and unnecessary names
   for intermediate values we don't care about. *)
let sum_sq n =
  let l = 0 -- n in
  let sq_l = List.map square l in
  sum sq_l
(* Maybe worse: have to read the function applications from right to left
   rather than top to bottom, and extra parentheses. *)
let sum_sq n =
  sum (List.map square (0--n))

val sum_sq : int -> int = <fun>

val sum_sq : int -> int = <fun>

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

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

4.7. الكاري

رأينا بالفعل أن دالة OCaml تأخذ وسيطين من النوعين t1 وt2 وتعيد قيمة من النوع t3 لها النوع t1 -> t2 -> t3. ونستخدم متغيرين بعد اسم الدالة في تعبير let:

let add x y = x + y

val add : int -> int -> int = <fun>

وثمة طريقة أخرى لتعريف دالة تأخذ وسيطين هي كتابة دالة تأخذ زوجًا مرتبًا:

let add' t = fst t + snd t

val add' : int * int -> int = <fun>

وبدلًا من استخدام fst وsnd، يمكننا استخدام نمط زوج مرتب في تعريف الدالة، فينتج تنفيذ ثالث:

let add'' (x, y) = x + y

val add'' : int * int -> int = <fun>

الدوال المكتوبة بالأسلوب الأول (بالنوع t1 -> t2 -> t3) تسمى دوال مكارَية (curried)، والدوال المستخدمة بالأسلوب الثاني (بالنوع t1 * t2 -> t3) تسمى غير مكارَية (uncurried). ومن باب الاستعارة، الدوال المكارَية «أكثر بهارات» لأنك تستطيع تطبيقها جزئيًا (وهو ما لا تستطيع فعله بالدوال غير المكارَية: لا يمكنك تمرير نصف زوج). في الواقع، لا يشير مصطلح curry إلى البهارات، بل إلى منطقي اسمه Haskell Curry (وهو واحد من مجموعة صغيرة جدًا من الأشخاص الذين سُميت لغات برمجة باسمهم الأول واسمهم الأخير معًا).

أحيانًا ستصادف مكتبات توفر نسخة غير مكارَية من دالة، لكنك تريد نسخة مكارَية منها لاستخدامها في شيفرتك؛ أو العكس. لذا من المفيد معرفة كيفية التحويل بين نوعي الدوال، كما فعلنا مع add أعلاه.

بل يمكنك كتابة بضع دوال من الرتبة العليا تقوم بالتحويل عنك:

let curry f x y = f (x, y)
let uncurry f (x, y) = f x y

val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c = <fun>

val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c = <fun>

let uncurried_add = uncurry add
let curried_add = curry add''

val uncurried_add : int * int -> int = <fun>

val curried_add : int -> int -> int = <fun>

4.8. قوانين جبرية للدوال من الرتبة العليا

استخدمنا map وfilter وfold لوصف حسابات على القوائم. وتخضع هذه الدوال أيضًا لقوانين جبرية (algebraic laws): معادلات تتيح لنا استبدال تعبير بآخر يحسب النتيجة نفسها. وعلى وجه الخصوص، يمكن للقوانين أن تدمج عدة اجتيازات في اجتياز واحد، وهو تحويل يسمى الدمج (fusion).

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

4.8.1. ثلاث دواليات صغيرة

وكخطوة تمهيدية، لنعرّف بعض الدوال التي سنستخدمها في القوانين. يؤلّف المؤثر << بين دالتين: فـ f << g تطبّق g أولًا ثم f. أي أنه يركّب الدوال من اليمين إلى اليسار. ويجمع المؤثر &&& بين محمولين. وأخيرًا، تطبّق guard p f الدالة f فقط عندما يتحقق p:

let ( << ) f g x = f (g x)
let ( &&& ) p q x = p x && q x
let id x = x
let guard p f x =
  if p x then f x else id

val ( << ) : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

val ( &&& ) : ('a -> bool) -> ('a -> bool) -> 'a -> bool = <fun>

val id : 'a -> 'a = <fun>

val guard : ('a -> bool) -> ('a -> 'b -> 'b) -> 'a -> 'b -> 'b = <fun>

كما سنستخدم هذه الأسماء المختصرة لدوال المكتبة القياسية:

let map = List.map
let filter = List.filter
let foldr f z lst = List.fold_right f lst z

val map : ('a -> 'b) -> 'a list -> 'b list = <fun>

val filter : ('a -> bool) -> 'a list -> 'a list = <fun>

val foldr : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>

غيّرنا ترتيب معاملات foldr لتصبح القائمة الوسيط الأخير، حتى نتمكن من تركيبها مع map وfilter في القوانين أدناه.

4.8.2. دمج Map وFilter

تخطيط دالة الهوية يترك عناصر القائمة دون تغيير. وتخطيط دالتين على التوالي يكافئ تخطيط تركيبتهما:

map id = id
map (f << g) = map f << map g

على سبيل المثال، ينتج هذان التعبيران كلاهما [4; 9; 16]:

let add_one x = x + 1
let square x = x * x
let mapped = (map square << map add_one) [1; 2; 3]
let mapped_fused = map (square << add_one) [1; 2; 3]

val add_one : int -> int = <fun>

val square : int -> int = <fun>

val mapped : int list = [4; 9; 16]

val mapped_fused : int list = [4; 9; 16]

تتجنب النسخة المدمجة بناء القائمة الوسيطة map g lst.

ويمكن دمج مرشّحين اثنين أيضًا:

filter p << filter q = filter (p &&& q)

ومرة أخرى، تتجنب النسخة المدمجة قائمة وسيطة.

let positive x = x > 0
let even x = x mod 2 = 0
let selected = (filter positive << filter even) [-2; -1; 0; 1; 2; 3; 4]
let selected_fused = filter (positive &&& even) [-2; -1; 0; 1; 2; 3; 4]

val positive : int -> bool = <fun>

val even : int -> bool = <fun>

val selected : int list = [2; 4]

val selected_fused : int list = [2; 4]

كل من selected وselected_fused هو [2; 4].

4.8.3. دمج Map أو Filter في طي نحو اليمين

يزيل القانونان التاليان القائمة التي كانت map أو filter ستنشئها قبل الطي نحو اليمين:

foldr f z << map g = foldr (f << g) z
foldr f z << filter p = foldr (guard p f) z

في القانون الأول، يحسب (f << g) x acc المقدار f (g x) acc. وفي الثاني، إما أن تدمج guard p f x acc العنصر x مع المجمِّع أو تمرّر المجمِّع دون تغيير. ويحافظ كلا القانونين على الترتيب الذي يدمج به الطي نحو اليمين العناصر.

4.8.4. دمج خط أنابيب كامل

يمكننا تطبيق تلك القوانين على التوالي. وعندما يأتي filter قبل map، تختبر خطوة الطي العنصر الأصلي ثم تحوّله:

foldr f z << map g << filter p
= foldr (guard p (f << g)) z

وعندما يأتي map قبل filter، يجب أن يختبر المحمول العنصر المحوَّل. وهذا يفسّر التركيب الإضافي p << g:

foldr f z << filter p << map g
= foldr (guard (p << g) (f << g)) z

وإليك الترتيبين في OCaml:

let sum_even_squares =
  foldr ( + ) 0 << map square << filter even
let sum_even_squares_fused =
  foldr (guard even (( + ) << square)) 0
let large x = x > 10
let sum_large_squares =
  foldr ( + ) 0 << filter large << map square
let sum_large_squares_fused =
  foldr (guard (large << square) (( + ) << square)) 0

val sum_even_squares : int list -> int = <fun>

val sum_even_squares_fused : int list -> int = <fun>

val large : int -> bool = <fun>

val sum_large_squares : int list -> int = <fun>

val sum_large_squares_fused : int list -> int = <fun>

بالنسبة إلى [1; 2; 3; 4]، يعيد الزوج الأول 20: فهو يختار المدخلات الزوجية ثم يربّعها. وبالنسبة إلى [1; 2; 4; 5]، يعيد الزوج الثاني 41: فهو يربّع كل مدخل ثم يختار النتائج الأكبر من 10. وكل دالة مدمجة تجتاز مدخلها مرة واحدة دون بناء قائمة وسيطة.

4.8.5. قانون ذو صلة للطي نحو اليسار

يمكن أيضًا دمج map في List.fold_left:

List.fold_left f z (List.map g lst)
= List.fold_left (fun acc x -> f acc (g x)) z lst

يبدأ الطرفان بـ z ويحدّثان المجمِّع بـ f acc (g x) لكل عنصر، من اليسار إلى اليمين. على سبيل المثال:

let sum_of_squares lst =
  lst |> List.map square |> List.fold_left ( + ) 0
let sum_of_squares_fused lst =
  lst |> List.fold_left (fun acc x -> acc + square x) 0

val sum_of_squares : int list -> int = <fun>

val sum_of_squares_fused : int list -> int = <fun>

4.8.6. عن الحاجة إلى دوال نقية

تصف المعادلات أعلاه تساوي النتائج، لا تساوي كل سلوك قابل للملاحظة. فدوال map المنفصلة تنفّذ كل استدعاءات g قبل أي استدعاء لـ f، بينما يمكن لدالة map مدمجة أن تشابك بينها. ويمكن لقانون filter أيضًا أن يغيّر ترتيب استدعاءات المحمول. وإذا كانت دالة تطبع أو تطلق استثناءً أو تغيّر حالة قابلة للتغيير، فإن تلك الفروق تهم.

لذا لا تطبّق OCaml عمومًا عمليات الدمج هذه تلقائيًا، وإن كان بإمكان مصرّف أن يفعل ذلك إن استطاع إثبات أن الدوال نقية. ومصرّف Haskell، أي GHC، ينفّذ بعض عمليات الدمج هذه تلقائيًا.

4.9. الملخّص

هذا الفصل من أهم فصول الكتاب. لم يغطِّ أي ميزة لغوية جديدة. بل تعلمنا كيفية استخدام بعض الميزات القائمة بطرق قد تكون جديدة أو مفاجئة أو صعبة. والبرمجة من الرتبة العليا ومبدأ التجريد فكرتان ستساعدانك على أن تصبح مبرمجًا أفضل في أي لغة، لا في OCaml فقط. وبالطبع، تتفاوت اللغات في مدى دعمها لهاتين الفكرتين، فبعضها يوفر مساعدة أقل بكثير في كتابة شيفرة من الرتبة العليا — وهذا أحد أسباب استخدامنا OCaml في هذا المقرر.

أصبح map وfilter وfold وغيرها من الدواليات معترفًا بها على نطاق واسع طرقًا ممتازة لهيكلة الحساب. ومن أسباب ذلك أنها تستخلص الاجتياز (iteration) على بنية بيانات من الحساب الذي يُجرى عند كل عنصر. وتدعم لغات مثل Python وRuby وJava 8 الآن هذا النوع من الاجتياز.

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

4.9.1. المصطلحات والمفاهيم

• مبدأ التجريد (Abstraction Principle)
• قانون جبري (algebraic law)
• المجمِّع (accumulator)
• apply
• تجميعي (associative)
• compose
• استخلاص (factor)
• filter
• دالة من الرتبة الأولى (first-order function)
• fold
• دالية (functional)
• الدمج (fusion)
• عملية طي معمّمة (generalized fold operation)
• guard
• دالة من الرتبة العليا (higher-order function)
• map
• خط أنابيب (pipeline)
• خطوط الأنابيب (pipelining)

4.9.2. قراءات إضافية

• Introduction to Objective Caml، الفصول 3.1.3 و5.3
• OCaml from the Very Beginning، الفصل 6
• More OCaml: Algorithms, Methods, and Diversions، الفصل 1، بقلم John Whitington. وهذا الكتاب تكملة لـ OCaml from the Very Beginning.
• Real World OCaml، الفصل 3 (احترس من أن مكتبة Core في هذا الكتاب لها وحدة List مختلفة عن وحدة List في المكتبة القياسية، بأنواع مختلفة لـ map وfold عن التي رأيناها هنا)
• «Higher Order Functions»، الفصل 6 من Functional Programming: Practice and Theory. Bruce J. MacLennan، Addison-Wesley، 1990. مناقشتنا للدوال من الرتبة العليا ومبدأ التجريد مدينة لهذا الفصل.
• «Can Programming be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs.» محاضرة جائزة تورينغ لعام 1977 لجون باكوس بصيغتها الموسّعة مقالًا منشورًا.
• «Second-order and Higher-order Logic» في The Stanford Encyclopedia of Philosophy.

let double x = 2 * x
let square x = x * x
let twice f x = f (f x)
let quad = twice double
let fourth = twice square

let ( $ ) f x = f x

let ( @@ ) f g x = x |> g |> f

let uncurried_nth (lst, n) = List.nth lst n

let square x = x * x
let even x = x mod 2 = 0
let large x = x > 10
let score =
  foldr ( + ) 0
  << filter large
  << map square
  << filter even