Teori kategori untuk programmer. Dengan jari

Halo kolega.







Mengembangkan minat yang tak kunjung padam dalam literatur akademis yang serius , bisa dikatakan , kami sampai pada teori kategori . Topik dalam presentasi terkenal Bartosz Milevsky ini telah muncul di Habré dan sekarang ini dapat membanggakan indikator-indikator seperti itu: Semakin menyenangkan bahwa kami berhasil menemukan bahan yang relatif segar (Januari 2020), yang berfungsi sebagai pengantar yang sangat baik dan pada saat yang sama sesingkat mungkin dengan teori kategori. Kami berharap kami dapat membuat Anda tertarik dengan topik ini.











Jika Anda dan saya, pembaca yang budiman, menghadapi masalah yang sama, maka Anda pernah tersiksa oleh pertanyaan "apa itu monad ?!" Kemudian Anda mencari pertanyaan ini di Google, menyelinap diam-diam ke lubang kelinci matematika abstrak , terjerat dalam fungsi , monoid , kategorisampai mereka menyadari bahwa mereka sudah lupa pertanyaan apa yang membawamu ke sini. Pengalaman ini bisa sangat luar biasa jika Anda belum pernah melihat bahasa pemrograman fungsional sebelumnya, tetapi jangan khawatir! Saya telah mempelajari banyak halaman matematika padat untuk Anda dan menonton berjam-jam ceramah tentang topik ini. Jadi untuk menyelamatkan Anda dari kebutuhan itu, saya akan meringkas topik di sini dan juga menunjukkan kepada Anda bagaimana Anda dapat menerapkan teori kategori sehingga Anda dapat berpikir (dan menulis kode) dalam gaya fungsional sekarang.



Artikel ini ditujukan untuk siapa saja yang menganggap diri mereka sebagai "pemula" dalam pemrograman fungsional dan baru mulai bekerja dengan Scala, Haskell, atau bahasa serupa lainnya. Setelah membaca artikel ini, Anda akan merasa sedikit lebih percaya diri dalam menafsirkan dasar-dasar teori kategori dan mengidentifikasi prinsip-prinsipnya "di lapangan". Juga, jika Anda pernah mencoba matematika teoretis, jangan langsung menyebutkan konsep yang dibahas di sini. Sebagai aturan, lebih banyak yang dapat dikatakan tentang masing-masing daripada yang tertulis di sini, tetapi artikel ini akan cukup untuk programmer yang ingin tahu.

Dasar

Jadi apa sebenarnya kategori itu dan bagaimana hubungannya dengan pemrograman? Seperti banyak konsep yang digunakan dalam pemrograman, kategori adalah hal yang sangat sederhana dengan nama yang mewah. Ini hanyalah grafik berarah berlabel dengan beberapa batasan tambahan. Setiap node dalam kategori disebut "objek" dan setiap tepinya disebut "morphism".







Seperti yang mungkin sudah Anda duga, tidak semua grafik berarah adalah kategori; agar grafik dapat dianggap sebagai kategori, beberapa kriteria tambahan harus dipenuhi. Pada gambar berikutnya, kita perhatikan bahwa setiap objek memiliki morfisme yang menunjuk ke dirinya sendiri. Ini adalah morfisme yang identik, dan setiap objek harus memiliki sedemikian rupa sehingga grafik dianggap sebagai kategori. Selanjutnya, perhatikan bahwa objek tersebut Amemiliki morfisme yang fmenunjukkanB, dan, juga, objek tersebut Bmemiliki morfisme yang gmenunjuk ke C. Karena ada jalan dari Ake Bdan dari Bke C, jelas ada jalan dari Ake C, bukan? Ini adalah kategori persyaratan selanjutnya untuk morfisme yang harus komposisi asosiatif harus dilakukan, sehingga untuk morfisme f: A = > B , dan g: B = > Cada morfisme h = g(f): A = > C.



Perhitungan ini mungkin sudah tampak sedikit abstrak, jadi mari kita lihat contoh yang memenuhi definisi ini dan ditulis dalam Scala.

trait Rock
trait Sand
trait Glass
def crush(rock: Rock): Sand
def heat(sand: Sand): Glass

Saya pikir contoh ini membuat hubungan menjadi sedikit lebih mudah. Menghapus batu menjadi pasir adalah morfisme yang mengubah suatu benda rockmenjadi benda sand, sedangkan peleburan kaca dari pasir merupakan morfisme yang mengubah suatu benda sandmenjadi benda glass. Dalam hal ini, komposisi relasi ini pasti akan terlihat

val glass: Glass = heat(crush(rock))

Ada juga fungsi identitas (didefinisikan dalam PredefScala), karena untuk objek apa pun tidak sulit untuk menulis fungsi yang mengembalikan objek yang sama. Oleh karena itu, sistem ini merupakan suatu kategori, meskipun cukup sederhana.

Pemahaman yang lebih dalam dengan kategori

Sekarang kita akan mempelajari lebih dalam tentang terminologi teori kategori dan mulai dengan kategori yang disebut magma. Jika Anda belum terlalu paham dengan konsep dasar ini, izinkan saya menjelaskan bahwa magma hanyalah operasi biner, yaitu operasi pada dua nilai, sebagai akibatnya diperoleh nilai baru. Agar tidak membahas secara detail, saya tidak akan memberikan bukti bahwa himpunan semua operasi biner sebenarnya adalah kategori, tetapi bagi mereka yang tertarik dengan detail, saya sarankan membaca artikel berikut oleh Bartosz Milevsky. Semua aritmatika dari penjumlahan hingga perkalian termasuk dalam subkategori, disatukan oleh kategori magmatik (lihat diagram).



Urutan warisan berikut berlaku di sini:

• 1. Magma: semua operasi biner
• 2. Semigroups: semua operasi biner yang asosiatif
• o : .
• 3. : ,
• o : , (aka )

Jadi, kembali ke contoh sebelumnya, penjumlahan dan perkalian adalah monoid karena keduanya asosiatif (a + (b + c) = (a + b) + c)dan memiliki satu elemen (ax 1 = 1 xa = a). Lingkaran terakhir pada diagram ini berisi kuasigroup yang prinsip embedding berbeda mungkin berlaku daripada semigroup atau monoid. Quasigroup adalah operasi biner yang dapat dibalik. Menjelaskan properti ini tidak begitu mudah, jadi saya merujuk Anda ke serangkaian artikel oleh Mark Siman yang membahas topik ini. Operasi biner dapat dibalik ketika untuk nilai apa pun adan bada nilai-nilai seperti itu xdan yyang memungkinkan konversi akeb... Saya tahu ini terdengar rumit. Untuk memperjelasnya, mari kita lihat contoh pengurangan berikut:

val x = a - b
val y = a + b
assert(a - x == b)
assert(y - a == b)

Harap dicatat: itu ytidak berpartisipasi dalam pengurangan seperti itu, tetapi contoh tetap dihitung. Objek dalam kategori diabstraksi dan bisa berupa apa saja; dalam hal ini, penting bahwa untuk setiap adan byang dapat dibuat, pernyataan ini tetap benar.

Jenis dalam konteks

Terlepas dari disiplin khusus Anda, topik tipe harus jelas bagi siapa saja yang memahami arti tipe data dalam pemrograman. Integer, boolean, floating point, dan sebagainya adalah semua tipe, tetapi bagaimana Anda menggambarkan tipe Platonis yang ideal dalam kata-kata? Dalam bukunya Category Theory for Programmers, yang berubah menjadi serangkaian posting blog, Milevsky mendeskripsikan tipe hanya sebagai "kumpulan nilai". Misalnya, boolean adalah himpunan terbatas yang berisi nilai “true” dan “false” (false). Karakter (char) adalah himpunan terbatas dari semua karakter angka-huruf, dan string (string) adalah himpunan char tak terbatas.



Masalahnya adalah bahwa dalam teori kategori kita cenderung menjauh dari himpunan dan berpikir dalam kerangka objek dan morfisme. Tetapi fakta bahwa tipe hanyalah set tidak bisa dihindari. Untungnya, ada tempat dalam teori kategori untuk himpunan ini, karena objek kita adalah abstraksi dan dapat mewakili apa pun. Oleh karena itu, kami berhak untuk mengatakan bahwa objek kami adalah set, dan selanjutnya mempertimbangkan program Scala kami sebagai kategori, di mana tipe adalah objek dan fungsi adalah morfisme. Bagi banyak orang, ini mungkin tampak sangat menyakitkan; lagipula, di Scala kita terbiasa berurusan dengan objek, tetapi perlu ditunjukkan secara eksplisit.



Jika Anda pernah bekerja dengan bahasa berorientasi objek seperti Java, Anda mungkin akrab dengan konsep tipe generik. Ini adalah hal-hal sepertiLinkedListatau, dalam kasus Scala, di Option[T]mana Tmewakili tipe data yang mendasari disimpan dalam beberapa struktur. Bagaimana jika kita ingin membuat pemetaan dari satu jenis ke jenis lainnya sehingga struktur jenis pertama dipertahankan? Selamat datang di dunia functor, yang didefinisikan sebagai pemetaan antar kategori untuk memelihara struktur. Dalam pemrograman, Anda biasanya harus bekerja dengan subkategori functor, yang disebut endofunctors, yang membantu memetakan kategori ke dirinya sendiri. Jadi saya hanya akan mengatakan bahwa ketika saya berbicara tentang functor yang saya maksud adalah endofunctors.



Sebagai contoh dari seorang functor, mari kita lihat tipe Scala Option[T]dalam hubungannya dengan contoh kita sebelumnya, yang menyebutkan batu, pasir, dan kaca:

val rockOpt: Option[Rock] = Some(rock)

Di atas kita memiliki tipe Rockseperti yang kita definisikan sebelumnya, tetapi dibungkus Option. Ini adalah tipe generik (dan lebih banyak lagi, lebih lanjut tentang ini di bawah), memberi tahu kita bahwa suatu objek adalah entitas tertentu yang kita cari, atau Noneyang dapat dibandingkan dengan nulldalam bahasa lain.



Jika kita tidak menggunakan functors, maka kita bisa membayangkan bagaimana kita menerapkan fungsi crush()untuk Rock, yang akan membutuhkan beralih ke operator if untuk menangani situasi di mana ia Optionadalah None.

var sandOpt: Option[Sand] = None
if(rockOpt != None) {
  sandOpt = Some(crush(rockOpt.get))
}

Kami mungkin mengatakan bahwa ini adalah sidetrack, tetapi tolong jangan gunakan var - kode seperti itu buruk di Scala karena beberapa alasan. Sekali lagi, kembali ke topik: di Java atau C # ini tidak akan menjadi masalah. Anda memeriksa untuk melihat apakah nilai Anda adalah tipe yang Anda harapkan untuk dilihat dan melakukan apa pun yang Anda inginkan dengannya. Tetapi dengan kekuatan dari para fungtor, semuanya dapat dilakukan dengan lebih elegan dengan fungsi map():

val sandOpt: Option[Sand] = rockOpt.map(crush)

Boom, satu baris dan selesai. Mungkin saja untuk meletakkan contoh pertama dalam satu baris, menggunakan operator terner atau yang serupa, tetapi Anda tidak akan berhasil begitu ringkas. Contoh ini benar-benar luar biasa dalam kesederhanaannya. Inilah yang terjadi di sini: ia map()mengambil sebuah fungsi dan memetakan fungsi itu (dalam pengertian matematis) ke dirinya sendiri. Strukturnya Optiondipertahankan, tetapi sekarang berisi salah satu Sand, atau None, sebagai ganti Rockatau None. Ini dapat diilustrasikan seperti ini:







Perhatikan betapa indahnya segala sesuatu berbaris, setiap objek dan morfisme dipertahankan di kedua sistem. Akibatnya, morfisme di tengah adalah fungsi yang mewakili pemetaan dari Tke Option[T].

Bersama

Sekarang kita akhirnya bisa kembali ke pertanyaan awal “apa sih itu monad”? Ada jawaban yang bisa Anda temukan secara membabi buta jika Anda hanya mencoba Google saja, dan bunyinya seperti ini: monad hanyalah monoid dalam kategori endofunctors, yang sering diikuti dengan ucapan yang sangat sarkastis, "apa masalahnya?" Sebagai aturan, dengan cara ini mereka mencoba untuk bercanda menunjukkan betapa sulitnya segala sesuatu dalam topik ini, tetapi pada kenyataannya, tidak semuanya begitu menakutkan - lagipula, kami telah menemukan arti frasa ini. Mari kita lakukan langkah demi langkah lagi.



Pertama, kita tahu bahwa monoid adalah operasi biner asosiatif, yang masing-masing berisi elemen netral (tunggal). Kedua, kami tahu bahwa fungsi akhir memungkinkan Anda memetakan kategori ke kategori itu sendiri, sambil mempertahankan strukturnya. Jadi, monad hanyalah sejenis jenis pembungkus (seperti pada contoh jenis umum di atas) yang mempertahankan beberapa metode untuk menerima fungsi dan memetakannya ke dirinya sendiri. List- ini adalah monad, Option(seperti yang telah kita bahas di atas) adalah monad, dan seseorang bahkan mungkin memberi tahu Anda dan Futurejuga monad. Contoh:

val l: List[Int] = List(1, 2, 3)
def f(i: Int) = List(i, i*2, i*3)
println(l.flatMap(f)) // : List(1, 2, 3, 2, 4, 6, 3, 6, 9)

Sederhana saja, bukan? Paling tidak, harus ada perasaan bahwa tidak sulit untuk memahami semuanya di sini, meskipun sekilas tidak sepenuhnya jelas apa gunanya konsep semacam itu.