👂🏽 👆 👴🏻 Daftar di Kotlin. Pendekatan Haskell 🤽🏾 🛀🏻 🙆🏽

Haskell adalah bahasa yang berfungsi penuh dan sangat ringkas. Siapa pun yang pernah mencoba menulis kode di Haskell memperhatikan betapa ringkas dan anggunnya daripada menulis hal yang sama dalam bahasa imperatif. Untuk mencapai hal yang sama di Jawa, menurut saya, tidak mungkin, tetapi Kotlin memungkinkan Anda untuk bergerak ke arah ini dan mencoba gaya yang berfungsi penuh. Kita dapat memperoleh semua fungsi kompleks yang mungkin kita butuhkan dari basis awal dari 3 fungsi paling terkenal: peta, filter, kurangi. Selain itu, saya membuat repositori yang dapat Anda pelajari dan lihat tesnya.

Sebelum memulai, saya ingin menarik perhatian pada fakta bahwa tidak layak menerapkan pendekatan fungsional dengan cara ini, karena kode akan sangat lambat dan tidak boleh digunakan dalam aplikasi produksi. Tentu ada opsi untuk memperbaikinya, tetapi tujuan artikel ini bukan untuk mengungkapkan opsi-opsi ini, tetapi untuk mempertimbangkan pendekatan alternatif untuk menulis kode. Bagaimanapun, pemahaman tentang pendekatan ini akan membantu Anda dengan struktur data rekursif, dan Anda dapat menghargai keindahan dan keanggunan dari bagaimana kode dibaca dan betapa lebih mudah untuk memahami.

Fungsi dasar

Daftar memainkan peran yang sangat penting dalam bahasa, dan banyak fungsi yang bermanfaat diterapkan untuk mereka. Mari kita lihat beberapa dari mereka dan bagaimana mereka dapat diimplementasikan di Kotlin.

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

Jika ada elemen dalam daftar, kami akan mengembalikan yang pertama, jika tidak kami akan mengembalikan kesalahan.
Kami tidak memiliki kesempatan untuk menulis kode seperti itu, tetapi, secara umum, jika Anda melihat lebih dekat, sangat mirip dengan ketika template. Kami juga akan menggunakan fungsi ekstensi untuk nantinya dapat menggunakan metode ini pada daftar dan memiliki cara yang sedikit lebih ringkas untuk mendapatkan nilai, tanpa tanda kurung pada akhirnya, seperti pemanggilan metode.

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

Agar mudah menggunakan rekursi, kami juga ingin membagi daftar menjadi elemen pertama + yang lainnya. Mari kita coba menerapkan fungsi ekor untuk ini.

Begini tampilannya di haskell:

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

Sayangnya, Kotlin tidak menyediakan tingkat kecocokan pola yang dapat dijelaskan oleh pengembang dengan gaya yang sama, jadi di sini kita harus menulis sedikit kapan.

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

Agak tidak jujur untuk menggunakan fungsi dari perpustakaan bahasa, tetapi di sisi lain, kita harus menulis kode untuk metode ini, jadi akan lebih baik menggunakan metode yang sudah bekerja.

Sekarang kita dapat membagi daftar menjadi elemen pertama + sisa daftar. Kita juga memerlukan fungsi menggabungkan daftar dan satu elemen, yang nantinya akan digunakan secara aktif untuk konversi dan operasi lainnya dalam daftar.

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

Sekarang kita dapat menambahkan daftar ke elemen di akhir, dan implementasi kita dari fungsi peta menjadi bekerja dan siap digunakan. Sayangnya, sekali lagi tidak ada cara untuk menambahkan objek ke daftar dengan cara yang lebih nyaman, jadi kami menggunakan metode add .

Saat ini kami memiliki hampir semua yang kami butuhkan. Satu-satunya hal yang kita butuhkan sekarang adalah untuk dapat menggambarkan kondisi batas untuk keluar dari rekursi. Untuk melakukan ini, kita akan menggunakan metode isEmpty () standar. Mari kita berhenti dan melihat apa yang kita miliki saat ini:

isEmpty () - apakah ada elemen dalam daftar
head - elemen pertama dari daftar
tail - daftar tanpa elemen pertama
daftar + elemen - kita dapat menggabungkan daftar dengan objek

Faktanya, hanya itu yang kita butuhkan untuk mendapatkan semua metode yang kita butuhkan.
Untuk selera saya, akan lebih mudah untuk menggunakan perbandingan panjang daftar di saat pernyataan. Kotlin sudah memberi kami ukuran untuk mendapatkan panjang daftar ini. Namun, misalkan kita ingin mengimplementasikannya sendiri. Dengan fungsionalitas kami, itu akan sangat sederhana:

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

Penerapan fungsi dasar

Pertimbangkan contoh paling umum. Misalkan kita memiliki daftar bilangan bulat, dan kami ingin menjumlahkannya, melupakan keberadaan siklus. Semua yang kita miliki adalah metode yang kita peroleh di atas, dan rekursi. Untuk melakukan ini, kami akan menggunakan pendekatan yang sama seperti ketika menghitung ukuran daftar:

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

Idenya sangat sederhana: jika tidak ada elemen dalam daftar, maka jumlahnya adalah 0; jika tidak, itu adalah jumlah dari elemen pertama dan panggilan rekursif dari jumlah untuk ekor.

Terlepas dari kenyataan bahwa kami tidak peduli dengan kecepatan dan optimisasi dalam kode ini, kami tidak bisa tidak mengingat kemampuan bahasa untuk menggunakan rekursi ekor. Rekursi ekor adalah kasus rekursi khusus di mana panggilan rekursif adalah operasi terakhir sebelum kembali dari suatu fungsi. Rekursi semacam ini patut diperhatikan karena dijamin memungkinkan Anda membangun kembali kode untuk iterasi. Seperti yang Anda tahu, masalah utama rekursi adalah bahwa selama pelaksanaan fungsi itu perlu untuk menyimpan tumpukan panggilan sehingga ketika kondisi batas tercapai, Anda dapat kembali dan menceritakan hasil akhir.

Mungkin tampak bahwa fungsi jumlah yang kami jelaskan persis seperti itu, karena panggilan terakhir adalah jumlah (xs.tail) . Namun, ini tidak benar. Jika Anda menjelaskan kode sedikit berbeda, itu akan menjadi jelas:

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

Sekarang kita melihat bahwa sebenarnya panggilan terakhir adalah jumlah dari elemen pertama dan bagian ekor yang tersisa.

Berita baiknya adalah jika Anda menambahkan pengubah tailrec ke suatu fungsi, IDE akan memberi tahu Anda bahwa fungsinya tidak. Namun, memperbaiki ini cukup mudah. Trik umum yang mengoreksi suatu fungsi adalah dengan menggunakan variabel bantu untuk menyimpan hasilnya. Ini terlihat seperti ini:

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

Untuk menghitung jumlah elemen, cukup untuk lulus 0 sebagai parameter kedua. Dan, untuk membuatnya benar-benar idiomatis, kita akan mengulang fungsinya sedikit lagi, menyembunyikan perhitungan utama dalam fungsi internal tanpa dunia luar memiliki akses ke parameter yang tidak dibutuhkan.

 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) }

Memiliki pengetahuan ini, Anda dapat melihat bahwa fungsi ukuran yang kami terapkan di atas tidak memenuhi kondisi yang diperlukan untuk rekursi ekor.

Sekarang kita siap mengimplementasikan peta, filter, kurangi menggunakan Kotlin. Nanti kita akan melihat bahwa itu cukup untuk menyadari hanya yang terakhir, dan sisanya, secara umum, adalah turunan dari itu. Tetapi hal pertama yang pertama.

Fungsi utama

PETA

Implementasi berulang fungsi ini melibatkan gerakan berurutan melalui daftar, menggunakan fungsi konversi dan menambahkan semua elemen yang diterima ke koleksi baru. Kami akan menggunakan panggilan rekursif di mana kondisi batas adalah daftar kosong. Maka implementasinya akan terlihat seperti ini:

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

Jika tidak ada elemen dalam daftar asli, maka kami mengembalikan daftar kosong, jika tidak, kami menerapkan transformasi ke elemen pertama dan menambahkan panggilan rekursif ke ujung untuk sisa daftar.

Namun, kami masih belum memiliki fungsi untuk menggabungkan elemen dan daftar. Tapi kita sudah bisa menyadarinya. Untuk memulainya, kita mendapatkan kasus yang lebih umum dari menggabungkan daftar dan setelah itu kita menggunakannya untuk menambahkan daftar lain ke elemen.

 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

Saring

Implementasinya akan sangat mirip dengan peta. Satu-satunya perbedaan adalah bahwa Anda perlu memahami apakah Anda perlu menambahkan elemen saat ini ke hasilnya. Untuk melakukan ini, kita akan memanggil lambda yang kita terima sebagai parameter. Implementasinya akan terlihat seperti ini:

 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) }

Jika elemen saat ini memenuhi kondisi filter, tambahkan secara rekursif ke ekor daftar, jika tidak, kami terus bekerja hanya dengan ekor daftar.

KURANGI

Yang paling sulit untuk dipahami dan, pada saat yang sama, fungsi yang paling kuat (dalam dunia fungsional itu disebut lipatan ). Paling sering, ini digunakan untuk menciutkan daftar menjadi satu item. Anda memiliki nilai awal tertentu s0 , dan juga ada daftar elemen a [] dan fungsi f , yang mengembalikan yang baru untuk nilai awal dan elemen berikutnya dari daftar. f (s0, a [0]) = s1 . Dan dengan demikian, kita secara berurutan menelusuri seluruh daftar elemen, mendapatkan semacam nilai tunggal pada output. Contoh yang cukup umum adalah penjumlahan elemen array. Dalam kasus ini, nilai awal adalah 0, dan fungsinya mengembalikan jumlah dari dua elemen: f (s, a [i]) = s + a [i] . Pertimbangkan bagaimana kita dapat mengimplementasikan fungsi ini secara rekursif.

 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) }

Pada prinsipnya, implementasinya persis sama dengan yang kami ulas di atas. Jika tidak ada elemen dalam daftar, kami mengembalikan nilai saat ini, jika tidak, kami menghitung elemen pertama yang baru, dan sekali lagi memanggil fungsi pengurangan untuk itu dan bagian belakang daftar.

Perhatikan bahwa kami juga dapat membuat modifikasi pada fungsi ini. Misalnya, jangan melewati nilai awal, tetapi gunakan elemen pertama dari daftar untuk ini. Untuk memahami bahwa pengurangan tidak berakhir di sana, bayangkan kita menggunakan daftar yang berbeda sebagai nilai awal. Dalam hal ini, setiap kali pada iterasi kami akan menyimpan tidak hanya satu nilai, tetapi sebuah daftar, berkat kemampuan kami yang sangat meningkat. Sebagai contoh, mari kita coba menerapkan fungsi pengurangan sedemikian rupa sehingga hasilnya adalah daftar asli:

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

Sekarang, saya pikir, Anda menebak bahwa kita bisa menggunakan pengurangan, untuk implementasi peta alternatif, filter. Karena kami belajar mengembalikan daftar yang sama persis dengan pengurangan, kami perlu melakukan sedikit perubahan untuk dapat mengonversi setiap elemen. Untuk filter, semuanya sangat mirip.

 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 }

Selain itu, mereka sering lupa bahwa kita juga dapat menggunakan pengurangan bukan dari awal daftar, tetapi dari akhir. Tentu, kita bisa memperluas daftar, dan setelah itu berlaku kurangi, tetapi ini tidak menarik. Mari kita coba menulis dan memahami bagaimana mengurangi karya untuk menciutkan daftar dalam urutan terbalik.

 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) }

Jika daftar tidak kosong, maka kita menerapkan fungsi f ke hasil melipat ekor daftar dan kepala daftar. Dengan demikian, elemen pertama akan diproses terakhir; kedua dari belakang - ke-2 dan seterusnya. Untuk opsi ini, Anda juga dapat menambahkan modifikasi yang akan menggunakan elemen terakhir dari daftar sebagai nilai awal, dll.

Hampir selalu, ketika bekerja dengan daftar, Anda dapat menggunakan beberapa kombinasi dari 3 fungsi ini untuk mendapatkan hasil yang Anda minati.

Mari kita juga mengimplementasikan fungsi zip , yang akan memungkinkan kita untuk menggabungkan 2 daftar.
Di pintu masuk kami mendapatkan 2 daftar. Dan kami ingin mengembalikan daftar pasangan yang panjangnya sama dengan minimum daftar asli.

Seperti biasa, Anda perlu memikirkan untuk keluar dari rekursi dan menulis suatu fungsi.

 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) } }

Anda dapat menambahkan modifikasi Anda sendiri, yang akan memungkinkan Anda, alih-alih mengembalikan sepasang elemen, menerapkan fungsi tertentu ke dua elemen. Di Haskell, fungsi ini disebut zipWith . Dan itu diimplementasikan dengan fungsi yang kami berhasil menulis dengan sangat sederhana:

 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) }

Sangat sering, ketika menggunakan pendekatan fungsional, masalah muncul ketika Anda perlu melakukan manipulasi berdasarkan bukan pada objek dalam daftar, tetapi berdasarkan indeks. Sebagai contoh, kita perlu menjumlahkan semua elemen genap dari daftar. Anda dapat mencoba untuk mencapai ini dengan mengurangi, mempertahankan Pair <Int, Boolean> sebagai nilai saat ini dan menambahkan nilai jika flag == true, dan ambil negasi bendera setiap kali untuk langkah berikutnya. Namun, ini tidak terlihat terlalu cantik, dan pembaca harus mencari tahu apa yang ingin Anda ungkapkan dengan kode ini. Kotlin memiliki urutan yang tak terbatas, dan mereka bagus untuk menyelesaikan masalah ini. Jika kita menganalisis apa yang ingin kita lakukan, ternyata kita ingin menyaring semua elemen dengan indeks ganjil, dan menjumlahkan yang tersisa. Dan untuk dapat memperoleh indeks, cukup memanggil zip untuk daftar dan urutan [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()

Di perpustakaan standar Kotlin, Anda dapat menemukan fungsi zip untuk pasangan urutan.

Sekarang mari kita lihat sebuah teka-teki sederhana yang mengilhami saya untuk menulis panduan ini, dan bagaimana implementasinya terlihat dalam bahasa imperatif di Kotlin dan di bagian paling akhir di Haskell.

Penting untuk menghitung jumlah maksimum di antara pasangan angka yang berdekatan dalam array bilangan bulat. Panjang array lebih besar dari 1, dan Anda tidak perlu khawatir meluap saat menambahkan elemen.

Pendekatan Java imperatif:

 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; }

Pendekatan fungsional pada Kotlin menggunakan fungsi tertulis (saya mengusulkan untuk mengimplementasikan sendiri fungsi max sebagai pelatihan sendiri):

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

Implementasi Haskell:

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

Seperti yang bisa kita lihat, apa yang kita implementasikan di Kotlin (omong-omong, kita bisa menggunakan mengurangi untuk menyelesaikan masalah ini) sangat mirip dengan apa yang dapat ditulis dalam Haskell.

Kesimpulan

Tidak diragukan lagi, ini tidak boleh digunakan dalam pengembangan, karena semuanya dilaksanakan secara tidak optimal hanya untuk menunjukkan pendekatan fungsional. Juga, hampir semua yang ditulis ada di perpustakaan standar Kotlin, jadi mungkin di masa depan, alih-alih menulis yang lain untuk loop, Anda akan menggunakan gaya fungsional yang disediakan oleh Kotlin.

Mungkin yang paling sulit dalam gaya fungsional adalah bahwa masalahnya dapat diselesaikan dengan berbagai cara. Yang paling jelas mungkin rumit dan sulit untuk dipahami di masa depan, dan menulis yang paling dimengerti mungkin membutuhkan waktu dan pemikiran yang serius. Satu-satunya hal yang dapat membantu dalam penguasaan adalah latihan dan pelatihan yang konstan.

PS: Seperti yang disebutkan di atas, Anda dapat melihat repositori dengan semua contoh yang ada di artikel. Jalankan tes dan lihat cara kerjanya!

PPS: Anda juga dapat melihat pendekatan alternatif yang mengimplementasikan fungsi serupa.

Dan pastikan untuk melihat nanti https://arrow-kt.io/ . Menurut pendapat saya, Anda tidak harus melihat ke sana segera, karena semuanya terlihat cukup menakutkan, tetapi kemudian, ketika functors dan monad tidak akan membuat Anda takut, pastikan untuk mempelajarinya.

Daftar di Kotlin. Pendekatan Haskell