تعلّم البرمجة بلغة كوتلن (54): تقليل و طي القوائم Reducing And Folding Lists

تعلّم البرمجة بلغة كوتلن (54): تقليل و طي القوائم Reducing And Folding Lists
أستمع الى المقال

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

في هذا الدرس، نواصل رحلتنا في دراسة المزيد من الطرق المهمة، في إجراء العمليات على القوائم. مثل عمليات خفض أو تقليل reduce القوائم، عبر دالتي ()reduce و ()reduceRight، أو طي fold القوائم عبر دالتي ()fold و ()foldRight.

تعمل هذه الدوال، بطريقة التراكم Accumulation. أي أنها تُراكِم أو تُكَدِّس العناصر مع بعضها البعض، لتنتج في النهاية قيمة معينة واحدة.

دالة ()reduce:

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

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

val numbers = listOf(1, 2, 3, 4, 5)
val reducedList = numbers.reduce { accumulator, nextElement -> 
    accumulator + nextElement
}

قائمة numbers عناصرها من الأعداد الصحيحة Int، واستدعينا عبرها دالة ()reduce. ستتعامل الدالة مع القائمة حسب شرط تعبير اللامبدا المرسل إليها، وهو القيام بعملية جمع معاملي اللامبدا: accumulator و nextElement. ثم إضافة النتيجة للمتغير reducedList.

ولكن، من أين جاء المعاملان في تعبير اللامبدا المرسل إلى الدالة ()reduce؟ 

معاملي تعبير لامبدا دالة ()reduce:

تحتوي دالة ()reduce كدالة ذات مرتبة أعلى Higher-Order Function في مكتبة كوتلن القياسية، على معامل من نوع بيانات دالة، أي أنه معامل من النوع دالة. هذا المعامل (الدالة)، لديه معاملين يستقبل فيهما القيمة التراكمية بداية من العنصر الأول في القائمة، ثم العنصر الذي يليه. وهذا يعني، عند إرسال تعبير لامبدا إلى هذا المعامل الدالة، يتوفر هذان المعاملان داخل اللامبدا أيضًا.

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

وعند طباعة المتغير reducedList عبر دالة الطباعة، ستكون النتيجة: الرقم 15. وهي القيمة التي أعادتها الدالة كنتيجة لتجميع كل عناصر القائمة، قبل إسنادها إلى المتغير.

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

جمع عناصر numbers عبر العمليات الحسابية:

لدينا في القائمة الأعداد من 1 إلى 5. ففي المرة الأولى، نأخذ العدد 1 لأنه العنصر الأول من يسار القائمة:

accumulator = 1

ثم بعد ذلك، نأخذ الرقم الثاني:

nextElement = 2

الشرط في تعبير اللامبدا هو:

accumulator + nextElement

ولأن قيمة المتغيرين هي قيمة عددية، فاستخدام العامل الرياضي +، سيعمل على جمع العددين. وهذا ستكون نتيجته العدد 3. هذه القيمة سيتم إسنادها إلى المعامل accumulator:

accumulator = 3

العنصر التالي في القائمة، هو العدد 3، إذًا:

accumulator + nextElement = 3 + 3 = 6

أصبحت قيمة تجميع العناصر الآن تساوي 6، إذًا:

accumulator = 6

العنصر التالي هو العدد 4:

accumulator + nextElement = 6 + 4 = 10

والعنصر الأخير في القائمة هو العدد 5:

accumulator + nextElement = 10 + 5 = 15

وكل ذلك يعني، أنه تم تجميع عناصر القائمة قبل إسنادها للمتغير reducedList، بالطريقة التالية:

val reducedList = (((1 + 2) + 3) + 4) + 5

كما نعرف من الرياضيات، أن الأولوية في العمليات الحسابية هي للأقواس. ففي المرة أولى، سيتم جمع العددين 1 و 2، لأن لديهما الأولوية لوجودهما داخل القوس الأول الداخلي. ثم يتم إضافة العدد 3 إلى نتيجة جمعهما، قبل القيام بأية عملية حسابية أخرى، لوجوده في قوس مع نتيجة جمع العددين السابقين. وهكذا تجري العملية حتى نهاية عناصر القائمة numbers.

دالة ()reduceRight:

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

الفرق بين ()reduce و ()reduceRight:

ولفهم الفرق بين الدالتين، دعونا نستدعيهما على نفس القائمة numbers، مع تغيير شرط اللامبدا إلى طرح العناصر من بعضها بدلًا عن جمعها:

val reducedList = numbers.reduceRight { next, acc ->
    next - acc
}

القيمة التي ستعود من الدالة، والتي سيتم إسنادها إلى المتغير reducedList، هي العدد 3. فكأن الدالة قامت بالعملية الحسابية كالتالي:

val reducedList = 1 - (2 - (3 - (4 - 5)))

أول ما سيتم تنفيذه في التعبير أعلاه، هو 5 – 4 والذي يساوي 1-. ثم 1 – – 3 والذي يساوي 4 موجب. ثم 4 – 2 ويساوي 2-. وأخيرًا، 2 – – 1 ويساوي 3 موجب، وهي القيمة التي أعادتها الدالة.

نلاحظ أيضًا، أن معاملي اللامبدا معكوسين، هذا لأن معامل التجميع سيحمل قيمة العنصر الأخير وهو العدد 5 في قائمة numbers. والمعامل next سيحمل قيمة العنصر الثاني من اليمين في المرة الأولى، وهو العدد 4 في القائمة. لذلك، ستكون أول عملية تجميع في الشفرة أعلاه حسب شرط اللامبدا، هي طرح قيمة العنصر التالي next من قيمة العنصر الذي يحمل ما تم تجميعه حتى الآن، أي قيمة acc.

أمّا إذا استخدمنا دالة ()reduce:

val reducedList = numbers.reduce { acc, next ->
    acc - next
}

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

val reducedList = (((1 - 2) - 3) - 4) - 5

أول ما سيتم تنفيذه في التعبير أعلاه، هو 2 – 1 والذي يساوي 1-. ثم 3 – 1- والذي يساوي 4. ثم 4 – 4- ويساوي 8-. وأخيرًا، 5 – 8- ويساوي 13-، وهي القيمة التي أعادتها الدالة.

كما يظهر في المثالين، أن هناك فرق كبير بين نتيجة عمل الدالتين، لأن كلا منها يبدأ بعنصر مختلف في القائمة ولديه مسار مختلف أيضًا. فدالة ()reduce تبدأ من العنصر الأول، ويكون مسارها من اليسار إلى اليمين. أمّا دالة ()reduceRight، تبدأ من العنصر الأخير ويكون مسارها من اليمين إلى اليسار.

نوع بيانات القيمة العائدة:

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

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

accumulator + nextElement

أو

acc - next

ستكون قيمة من النوع Int. لأن طرح أو جمع عدد صحيح من آخر، ستكون النتيجة عدد صحيح. القائمة عناصرها أعداد صحيحة، القيمة العائدة هي عدد صحيح، هنا لن تحدث أية مشاكل. ولكن، إذا حاولنا إعادة قيمة من النوع String بوضع نتيجة تعبير اللامبدا بين علامات التنصيص الخاصة بنوع البيانات هذا:

val reducedList = numbers.reduce { acc, next ->
        "${acc - next}"
}

سيحدث الخطأ التالي أثناء تجميع وترجمة الشفرة أي Compile-Time Error:

Type mismatch: inferred type is String but Int was expected

هذا لأن الدالة تتوقع أن تعيد نتيجة قيمتها هي من النوع Int، ولكننا نحاول إعادة قيمة من النوع String.

استدعاء دالة ()reduce عبر قائمة فارغة Empty List:

في كوتلن، لدينا إمكانية إنشاء قائمة فارغة والتي قد نحتاجها لبعض الاستخدامات في شفرة برامجنا. وبطريقة مشابهة لطرق إنشاء القوائم التي درسناها في درس القوائم Lists، نستخدم دالة ()emptyList، لإنشاء قائمة فارغة:

val empty1 = emptyList<Int>()
val empty2 = emptyList<String>()
val empty3 = emptyList<Long>()
val empty4 = emptyList<Boolean>()

كل متغير من المتغيرات الأربعة، يُمثل نوع قائمة فارغة تختلف عناصرها حسب نوع البيانات الموضوع بين قوسي الزاوية <> في الدالة.

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

val reducedList = empty1.reduce { acc, next ->
    acc + next
}

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

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

دالة ()fold:

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

فمثلًا، إذا استدعينا الدالة عبر نفس القائمة السابقة:

val foldedList = numbers.fold(0) { accumulator, element ->
    accumulator + element
}

لدى دالة ()fold معاملين، أحدهما يستقبل القيمة الابتدائية التي سيتم تجميع العناصر إليها، والمعامل الثاني يستقبل تعبير اللامبدا. وبما أننا أرسلنا العدد 0 كقيمة للمعامل الأول، لذلك لن تختلف القيمة العائدة عن تلك العائدة من الدالة ()reduce، وهي العدد 15.

التحكم في نوع بيانات القيمة العائدة:

ولكن، بما أنه يمكننا أن نرسل القيمة الابتدائية، هذا يعني أنه يمكننا أن نرسل قيمة من أي نوع بيانات نريده:

val foldedList = numbers.fold("0") { accumulator, element ->
    accumulator + element
}

فبمجرد وضع علامتي تنصيص مزدوجة حول العدد 0، فهو لم يعد عدد من النوع Int، بل نص من النوع String. بالتالي، القيمة التي ستعيدها الدالة، ستكون من نفس نوع القيمة الابتدائية، وهو هنا النوع String.

وعند تنفيذ الشفرة، كانت النتيجة:

012345

هذه المرة لم يتم جمع العناصر كالمرة السابقة، بل تم تكديس العناصر على القيمة الابتدائية “0”، لأنه لايمكن إجراء عمليات حسابية على النصوص. إذًا تم تحويل كل عناصر القائمة التي من النوع Int، لتوافق نوع بيانات القيمة التي أرسلناها للدالة.

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

مثال آخر:

كمثال آخر، إذا كان لدينا قائمة عشوائية من الحروف، ونريد تحويلها إلى حروف أخرى. ثم ننتج قائمتين، إحداها للحروف الجديدة، والأخرى تحتوي على رمز ASCII الذي يُمثل هذه الحروف:

fun main() {

    val letters = listOf('F', 'y', 'W', 'b', 's')

    val (lettersList, codesList) = letters.fold(
        Pair(mutableListOf<Char>(), mutableListOf<Int>())
    ) { pair, element ->
        val newLetter = element - 1
        pair.first += newLetter
        pair.second += newLetter.code
        pair
    }
}

قائمة letters تحتوي على عناصر من الحروف العشوائية. وبما أننا نريد قائمتين عبر استخدام قائمة letters، استدعينا دالة ()fold، وأرسلنا إليها كائن Pair يحتوي على قائمتين من النوع MutableList، حتى نستطيع إضافة العناصر إليهما.

هذه الكائن Pair، هو ما ستعيده الدالة كنتيجة نهائية بعد انتهاء عملها. لذلك يمكننا استخدام طريقة تفكيك التصريحات destructuring declarations، لإسناد كل قائمة من القائمتين في كائن الـ Pair في متغير منفرد. المتغير lettersList للقائمة الأولى، والمتغير codesList للقائمة الثانية.

داخل دالة ()fold، لدينا القيمة الابتدائية كائن الـ Pair والذي يُمثله المعامل pair، والمعامل الآخر element سيُمثل عناصر قائمة letters. ثم متغير newLetter نضع به قيمة الحرف السابق للحرف الحالي، والذي نصل إليه بحذف العدد 1 من الحرف (لأن الحروف تُمثَّل بأرقام في الحاسب، يمكننا أن نجمع او نطرح منها أعداد صحيحة Int). نتيجة عملية الطرح، ستكون الحرف السابق للحرف حسب ترتيب الحروف في جدول الترميز آسكي.

بعد ذلك نقوم بإضافة الحرف الجديد newLetter، إلى القائمة الأولى في الكائن Pair، والتي يمكننا الوصول إليها عبر استخدام الخاصية first. ثم نضيف للقائمة الثانية في الكائن Pair، والتي يمكننا الوصول إليها عبر استخدام الخاصية second، الرمز العددي للحرف الجديد في جدول آسكي، والذي يمكننا الوصول إليه باستخدام الخاصية code الخاصة بنوع البيانات Char.

وأخيرًا، نعيد كائن الـ pair هذا، لأنه هو من أرسلناه كقيمة ابتدائية إلى دالة ()fold. لأن الدالة تعطينا الحرية في اختيار نوع بيانات القيمة الابتدائية، ولكن بعد ذلك يجب أن نعيد نفس القيمة في آخر سطر في الدالة.

وعند طباعة قيمة المتغيرين، ستكون النتيجة:

[E, x, V, a, r]
[69, 120, 86, 97, 114]

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

استدعاء دالة ()fold عبر قائمة فارغة Empty List:

يمكننا أن نستدعي هذه الدالة على قائمة فارغة. فبما أننا نرسل لها قيمة ابتدائية، ستعيدها الدالة في هذه الحالة:

val empty1 = emptyList<Int>()

val foldingEmptyList = empty1.fold(0) { acc, element ->
    acc + element
}

println(foldingEmptyList)

ستعيد الدالة العدد 0 المرسل إليها كقيمة ابتدائية، لأن القائمة فارغة. وهنا نرى أن الدالة تجنبت إحداث خطأ استثنائي يتسبب في تحطم البرنامج. وهذا خلافًا لدالة ()reduce والتي بالطبع يمكننا استخدامها، ولكن عندما نكون متأكدين 100% أن القائمة التي تستدعيها، لن تكون فارغة أثناء عمل البرنامج.

دالة ()foldRight:

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

fun main() {

    val list = listOf('a', 'b', 'c', 'd')

    val foldingLeft = list.fold("*") { acc, elem ->
        "$acc + $elem"
    }
    val foldingRight = list.foldRight("*") { elem, acc ->
        "$acc + $elem"
    }
}

لدينا قائمة list تحتوي على عناصر من النوع محرف Char. ثم استدعينا أولًا دالة ()fold وأرسلنا لها النص “*”. (هو نص String لأنه يتواجد بين علامتي تنصيص مزدوجة). هذا النص، سيُمثل بالمعامل الأول في تعبير اللامبدا. وبما أن القيمة الابتدائية هي من النوع String، يجب أن نعيد قيمة من هذا النوع. لذلك، التعبير:

"$acc + $elem"

سينتج نص أيضًا لتواجده بين علامتي تنصيص مزدوجة. علامة الـ + عبارة عن محرف Char في هذه الحالة، ويتم طباعته كما هو. وستكون طباعة قيمة المتغير foldingLeft هي:

* + a + b + c + d

بدأت الدالة بالقيمة الابتدائية “*” ثم أول عنصر من اليسار إلى نهاية العناصر في القائمة.

أمّا عند طباعة قيمة المتغير foldingRight:

* + d + c + b + a

بدأت الدالة مرة أخرى بالقيمة الابتدائية “*”. ولكن عملت على تجميع عناصر القائمة، بداية من آخر عنصر في أقصى يمين القائمة. نلاحظ أيضًا، أن الدالة ستستقبل القيمة الابتدائية “*” المرسلة إليها، في المعامل الثاني في تعبير اللامبدا.

الخلاصة:

عندما نريد إنتاج قيمة واحدة من تجميع أو تكديس عناصر القوائم Lists، وكنا متأكدين من أن هذه القوائم لن تكون فارغة، أو هي للقراءة فقط، عندها يمكننا استخدام دالتي ()reduce و ()reduceRight وستؤديان العمل.

أمّا إذا كنا نريد مرونة في القيمة العائدة من الدالة، وتجنب المشاكل والأخطاء حينما تكون القوائم فارغة، ستكون دالتي ()fold و ()foldRight هما الخيار الأفضل. ولكن يجب أن نرسل للدالتين، قيمة ابتدائية.

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

هل أعجبك المحتوى وتريد المزيد منه يصل إلى صندوق بريدك الإلكتروني بشكلٍ دوري؟
انضم إلى قائمة من يقدّرون محتوى إكسڤار واشترك بنشرتنا البريدية.