القوائم في Kotlin. نهج هاسكل

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

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

الوظائف الأساسية

تلعب القوائم دورًا مهمًا للغاية في اللغة ، ويتم تنفيذ العديد من الوظائف المفيدة لهم. دعونا نلقي نظرة على بعض منها وكيف يمكن تنفيذها على Kotlin.

head (x:_) = x head [] = badHead 

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

 val <T> List<T>.head: T get() = when (this.isEmpty()) { true -> throw NoSuchElementException("List is empty.") false -> this[0] } 

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

إليك ما يبدو على haskell:

 tail (_:xs) = xs tail [] = errorEmptyList "tail" 

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

 val <T> List<T>.tail: List<T> get() = drop(1) 

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

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

 operator fun <T> List<T>.plus(x: T): List<T> = ArrayList(this).also { it.add(x) } 

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

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

• isEmpty () - هل هناك أي عناصر في القائمة
• الرأس - العنصر الأول من القائمة
• الذيل - قائمة بدون العنصر الأول
• list + element - يمكننا ربط القائمة بكائن

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

 val <T> List<T>.size: Int get() = when (this.isEmpty()) { true -> 0 false -> 1 + this.tail.size } 

تطبيق الوظائف الأساسية

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

 fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> xs.head + sum(xs.tail) } 

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

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

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

 fun sum(xs: List<Int>): Int = when (xs.size) { 0 -> 0 else -> { val head = xs.head val tailSum = sum(xs.tail) head + tailSum } } 

الآن نرى أنه في الواقع المكالمة الأخيرة هي مجموع العنصر الأول والجزء المتبقي من الذيل.

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

 tailrec fun sum(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sum(xs.tail, xs.head + acum) } 

لحساب مجموع العناصر ، يكفي تمرير 0. كمعلمة ثانية لا حاجة.

 fun sum(xs: List<Int>):Int { tailrec fun sumInner(xs: List<Int>, acum: Int): Int = when (xs.size) { 0 -> acum else -> sumInner(xs.tail, xs.head + acum) } return sumInner(xs, 0) } 

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

الآن نحن جاهزون لتطبيق الخريطة ، التصفية ، التقليل باستخدام Kotlin. في وقت لاحق سنرى أنه كان كافياً لتحقيق هذا الأخير فقط ، والباقي ، بشكل عام ، مشتقات منه. لكن أول الأشياء أولاً.

الوظائف الرئيسية

الخريطة

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

 fun <T, R> List<T>.map(f: (T) -> R): List<R> = when (this.size) { 0 -> listOf() else -> f(head) + tail.map(f) } 

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

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

 operator fun <T> List<T>.plus(xs: List<T>): List<T> = when (xs.size) { 0 -> ArrayList(this) else -> (this + xs.head) + xs.tail } operator fun <T> T.plus(xs: List<T>): List<T> = listOf(this) + xs 

مرشح

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

 fun <T> List<T>.filter(f: (T) -> Boolean): List<T> = when (this.size) { 0 -> listOf() else -> if (f(head)) head + tail.filter(f) else tail.filter(f) } 

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

التقليل

الأصعب في الفهم ، وفي نفس الوقت ، الوظيفة الأقوى (في العالم الوظيفي تُعرف بالطيّة ). في أغلب الأحيان ، يتم استخدامه لطي قائمة إلى عنصر واحد. لديك قيمة بداية معينة s0 ، وهناك أيضًا قائمة بالعناصر a [] ووظيفة f ، والتي تُرجع قيمة جديدة لقيمة البداية والعنصر التالي من القائمة. f (s0، a [0]) = s1 . وبالتالي ، نتناول بالتسلسل قائمة كاملة من العناصر ، ونحصل على نوع ما من القيمة الفردية عند الإخراج. مثال شائع إلى حد ما هو جمع عناصر المصفوفة. في هذه الحالة ، تكون قيمة البداية هي 0 ، وتُرجع الدالة مجموع عنصرين: f (s، a [i]) = s + a [i] . ضع في اعتبارك كيف يمكننا تنفيذ هذه الوظيفة بشكل متكرر.

 fun <T, R> reduce(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> reduce(f(s, xs.head), xs.tail, f) } 

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

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

 fun <T> reduceSame(xs: List<T>) = reduce(listOf<T>(), xs) { ys, s -> ys + s } 

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

 fun <T, R> List<T>.map2(f: (T) -> R): List<R> = reduce(mutableListOf(), this) { xs, s -> (xs + f(s)).toMutableList() } fun <T> List<T>.filter2(f: (T) -> Boolean): List<T> = reduce(mutableListOf(), this) { ys, s -> if (f(s)) return@reduce (ys + s).toMutableList() else ys } 

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

 fun <T, R> reduceRight(s: T, xs: List<R>, f: (T, R) -> T): T = when (xs.size) { 0 -> s else -> f(reduceRight(s, xs.tail, f), xs.head) } 

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

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

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

كالعادة ، عليك التفكير في الخروج من العودية وكتابة دالة.

 fun <T, R> zip(xs: List<T>, ys: List<R>): List<Pair<T, R>> { return when (xs.isEmpty() || ys.isEmpty()) { true -> listOf() false -> Pair(xs.head, ys.head) + zip(xs.tail, ys.tail) } } 

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

 fun <T, R, C> zipWith(xs: List<T>, ys: List<R>, f: (T, R) -> C): List<C> = zip(xs, ys).map { f(it.first, it.second) } 

في كثير من الأحيان ، عند استخدام النهج الوظيفي ، تنشأ المشاكل عندما تحتاج إلى إجراء معالجات لا تستند إلى الكائنات في القوائم ، ولكن على أساس المؤشرات. على سبيل المثال ، نحتاج إلى جمع كل العناصر الزوجية في القائمة. يمكنك محاولة تحقيق ذلك من خلال تقليل ، والحفاظ على زوج <Int ، Boolean> كقيمة حالية وإضافة قيمة إذا flag == true ، وأخذ علامة التنبيه في كل مرة للخطوة التالية. ومع ذلك ، لا يبدو هذا جميلًا جدًا ، وسيتعين على القارئ معرفة ما تريد التعبير عنه باستخدام هذا الرمز. لدى Kotlin تسلسلات لا نهائية ، وهي رائعة لحل هذه المشكلة. إذا قمنا بتحليل ما نريد القيام به ، اتضح أننا نريد تصفية جميع العناصر بمؤشرات فردية ، وجمع العناصر المتبقية. ولكي تتمكن من الحصول على فهارس ، يكفي استدعاء الرمز البريدي للقائمة والتسلسل [0،1،2 ..]

 fun sumWithEvenIndexes(xs: List<Int>) = zip(xs, generateSequence(0) { it + 1 }.take(xs.size).toList()) .filter { it.second % 2 == 0 } .map { it.first } .sum() 

في مكتبة Kotlin القياسية ، يمكنك العثور على وظيفة zip لزوج التسلسل.

الآن دعونا نلقي نظرة على لغز بسيط ألهمني لكتابة هذا الدليل ، وكيف يبدو تنفيذه بلغة حتمية في Kotlin وفي النهاية في Haskell.

من الضروري حساب المبلغ الأقصى بين أزواج الأرقام المجاورة في مجموعة من الأعداد الصحيحة. طول المصفوفة أكبر من 1 ، ولا داعي للقلق بشأن الفائض عند جمع العناصر.

نهج جافا الحتمي:

 public Integer maxSum(List<Integer> array) { Integer max = array.get(0) + array.get(1); for (int i = 2; i < array.size(); i++) if (array.get(i) + array.get(i-1) > max) max = array.get(i) + array.get(i-1); return max; } 

نهج وظيفي في Kotlin باستخدام وظائف مكتوبة (أقترح تنفيذ أقصى وظيفة كتدريب بنفسك):

 fun maxSum(xs: List<Int>) = zipWith(xs, xs.tail, {a, b -> a + b}).max() 

تنفيذ هاسكل:

 maxSum xs = maximum $ zipWith (+) xs (tail xs) 

كما نرى ، ما قمنا بتطبيقه على Kotlin (بالمناسبة ، يمكننا استخدام تقليل لحل هذه المشكلة) يشبه إلى حد كبير ما يمكن كتابته في Haskell.

الخلاصة

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

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

ملاحظة: كما ذكر أعلاه ، يمكنك رؤية المستودع مع جميع الأمثلة الواردة في المقالة. قم بإجراء الاختبارات وانظر كيف يعمل!

PPS: يمكنك أيضًا إلقاء نظرة على نهج بديل يقوم بتنفيذ وظائف مماثلة.

وتأكد من رؤية لاحقًا https://arrow-kt.io/ . في رأيي ، لا يجب أن تنظر هناك على الفور ، لأن كل شيء يبدو مخيفًا جدًا ، ولكن في وقت لاحق ، عندما لا يخيفك الوحوش والموناد ، تأكد من دراسته.