Apakah Teori Kategori berguna untuk mempelajari pemrograman fungsional?

Saya belajar Haskell dan saya kagum dengan bahasanya. Namun saya tidak memiliki latar belakang matematika atau CS yang serius. Tapi saya seorang programmer perangkat lunak yang berpengalaman.

Saya ingin belajar teori kategori sehingga saya bisa menjadi lebih baik di Haskell.

Topik apa dalam teori kategori yang harus saya pelajari untuk memberikan dasar yang baik untuk memahami Haskell?

Dalam jawaban sebelumnya di situs Theoretical Computer Science , saya mengatakan bahwa teori kategori adalah "fondasi" untuk teori jenis. Di sini, saya ingin mengatakan sesuatu yang lebih kuat. Teori kategori adalah teori tipe . Sebaliknya, teori tipe adalah teori kategori . Biarkan saya memperluas poin-poin ini.

Teori kategori adalah teori tipe

Dalam setiap bahasa formal diketik, dan bahkan dalam matematika biasa menggunakan notasi resmi, kita akhirnya menyatakan fungsi dengan jenis . Secara implisit dalam penulisan itu adalah gagasan bahwa dan adalah beberapa hal yang disebut "jenis" dan adalah "fungsi" dari satu jenis ke jenis lainnya. Teori kategori adalah teori aljabar dari "jenis" dan "fungsi" tersebut. (Secara resmi, teori kategori menyebut mereka "objek" dan "morfisme" untuk menghindari menginjak-injak jari-jari teoretis tradisionalis, tetapi semakin saya melihat ahli teori kategori melemparkan kehati-hatian seperti itu pada angin dan menggunakan istilah yang lebih intuitif: "type "dan" berfungsi ". Tapi,A B $f : A \to B$$A$$B$$f$

Kita semua dibesarkan dengan teori himpunan mulai dari SMA dan seterusnya. Jadi, kita terbiasa memikirkan tipe-tipe seperti dan sebagai set, dan fungsi-fungsi seperti sebagai pemetaan set-theoretik. Jika Anda tidak pernah memikirkannya seperti itu, Anda dalam kondisi yang baik. Anda telah lolos dari pencucian otak teori-set. Teori kategori mengatakan bahwa ada banyak jenis jenis dan banyak jenis fungsi. Jadi, ide tipe sebagai set membatasi. Alih-alih, teori kategori menunjukkan tipe dan fungsi secara aljabar. Pada dasarnya, itulah yang disebut teori kategori. Teori tipe dan fungsi. Itu menjadi cukup canggih, melibatkan abstraksi tingkat tinggi. Tetapi, jika Anda bisa mempelajarinya, Anda akan memperoleh pemahaman yang mendalam tentang jenis dan fungsi.B $A$$B$$f$

Teori tipe adalah teori kategori

Yang dimaksud dengan "teori jenis," maksud saya adalah segala jenis bahasa formal yang diketik, berdasarkan aturan kaku pembentukan istilah yang memastikan bahwa segala sesuatu diketik. Ternyata, setiap kali kita bekerja dalam bahasa seperti itu, kita bekerja dalam struktur kategori-teori. Sekalipun kita menggunakan notasi set-theoretik dan berpikir set-secara teoritis, tetap saja kita akhirnya menulis hal-hal yang masuk akal secara kategoris. Itu adalah fakta yang luar biasa .

Secara historis, Dana Scott mungkin adalah orang pertama yang menyadari hal ini. Dia bekerja pada memproduksi model semantik bahasa pemrograman berdasarkan pada kalkulus lambda yang diketik (dan tidak diketik). Model set-theoretik tradisional tidak memadai untuk tujuan ini, karena bahasa pemrograman melibatkan rekursi tidak terbatas yang tidak dimiliki teori set. Scott menemukan serangkaian model semantik yang menangkap fenomena pemrograman, dan sampai pada kesadaran bahwa mengetik kalkulus lambda persis mewakili kelas kategori yang disebut kategori tertutup cartesian . Ada banyak kategori tertutup kartesian yang tidak "set-theoretic". Tetapi kalkulus lambda yang diketik berlaku untuk semuanya secara merata. Scott menulis esai yang bagus yang disebut " Teori yang menghubungkan kalkulus lambda"menjelaskan apa yang sedang terjadi, bagian-bagian yang sepertinya tersedia di web. Artikel asli diterbitkan dalam volume yang disebut" Kepada HB Curry: Esai tentang Logika Combinatory, Kalkulus dan Formalisme Lambda ", Academic Press, 1980. Berry dan Curien datang ke realisasi yang sama, mungkin secara independen.Mereka mendefinisikan mesin abstrak kategorikal (CAM) untuk menggunakan ide-ide ini dalam mengimplementasikan bahasa fungsional, dan bahasa yang mereka implementasikan disebut "CAML" yang merupakan kerangka kerja yang mendasari Microsoft F # .

Tipe konstruktor standar seperti , , dll. Adalah functors . Itu berarti bahwa mereka tidak hanya memetakan tipe ke tipe, tetapi juga berfungsi antara tipe ke fungsi antara tipe. Fungsi polimorfik mempertahankan semua fungsi yang dihasilkan dari tindakan functor. Teori kategori ditemukan pada 1950-an oleh Eilenberg dan MacLane→ L i s $\times$$\to$$List$tepatnya untuk memformalkan konsep fungsi polimorfik. Mereka menyebutnya "transformasi alami", "alami" karena hanya mereka yang dapat Anda tulis dengan cara yang benar menggunakan variabel tipe. Jadi, dapat dikatakan bahwa teori kategori diciptakan tepat untuk memformalkan bahasa pemrograman polimorfik, bahkan sebelum bahasa pemrograman muncul!

Seorang tradisionalis teori-set tidak memiliki pengetahuan tentang fungsi dan transformasi alami yang terjadi di bawah permukaan ketika ia menggunakan notasi teori-set. Tapi, selama dia menggunakan sistem tipe dengan setia, dia benar-benar melakukan konstruksi kategoris tanpa menyadarinya.

Semua dikatakan dan dilakukan, teori kategori adalah teori matematika klasik dari jenis dan fungsi. Jadi, semua programmer dapat mengambil manfaat dari belajar sedikit teori kategori, terutama programmer fungsional. Sayangnya, tampaknya tidak ada buku teks tentang teori kategori yang ditargetkan khusus untuk programmer. Buku-buku "teori kategori untuk ilmu komputer" biasanya ditargetkan pada mahasiswa / peneliti ilmu komputer teoretis. Buku karya Benjamin Pierce, teori kategori dasar untuk ilmuwan komputer mungkin adalah yang paling mudah dibaca.

Namun, ada banyak sumber daya di web, yang ditargetkan pada pemrogram. The halaman Haskellwiki dapat menjadi titik awal yang baik. Di Midlands Graduate School , kami memiliki kuliah tentang teori kategori (antara lain). Kursus Graham Hutton dipatok sebagai kursus "pemula", dan kursus saya dipatok sebagai kursus "lanjutan". Tetapi keduanya pada dasarnya mencakup konten yang sama, pergi ke kedalaman yang berbeda. University of Chalmers memiliki halaman sumber yang bagus tentang buku dan catatan kuliah dari seluruh dunia. Situs blog antusias "sigfpe" juga menyediakan banyak intuisi yang baik dari sudut pandang seorang programmer.

Topik dasar yang ingin Anda pelajari adalah:

• definisi kategori, dan beberapa contoh kategori
• functors, dan contohnya
• transformasi alami, dan contoh-contohnya
• definisi produk, coproducts dan eksponen (ruang fungsi), objek awal dan terminal.
• tambahan
• kategori monad, aljabar, dan Kleisli

Catatan kuliah saya sendiri di Midlands Graduate School mencakup semua topik ini kecuali yang terakhir (monad). Ada banyak sumber daya lain yang tersedia untuk monad hari ini. Jadi itu bukan kerugian besar.

Semakin banyak matematika yang Anda tahu, semakin mudah untuk belajar teori kategori. Karena teori kategori adalah teori umum dari struktur matematika, akan sangat membantu untuk mengetahui beberapa contoh untuk menghargai apa arti definisi tersebut. (Ketika saya belajar teori kategori, saya harus membuat contoh sendiri menggunakan pengetahuan saya tentang bahasa pemrograman semantik, karena buku teks standar hanya memiliki contoh matematika, yang saya tidak tahu apa-apa tentang itu.) Lalu datanglah buku brilian oleh Lambek dan Scott disebut " Pengantar logika kategorikal"yang menghubungkan teori kategori dengan sistem ketik (apa yang mereka sebut" logika "). Sekarang dimungkinkan untuk memahami teori kategori hanya dengan menghubungkannya dengan mengetik sistem bahkan tanpa mengetahui banyak contoh. Banyak sumber daya yang saya sebutkan di atas menggunakan ini pendekatan untuk menjelaskan teori kategori.

Saya akan mencoba dan membuatnya singkat dan manis. Ada korespondensi informal antara program Haskell dan kelas kategori tertentu, yang dapat dibuat lebih formal dengan beberapa pekerjaan. Korespondensi ini dikenal sebagai korespondensi Curry-Howard-Lambek dan berhubungan:

1. Jenis Haskell dengan objek kategori
2. $A\rightarrow B$ $f\colon A\rightarrow B$
3. Tipe data aljabar dengan objek awal
4. Ketik konstruktor dengan functors
5. dll

Daftar ini terus dan terus, tetapi satu poin penting adalah bahwa Anda dapat mendefinisikan hal-hal seperti monad dan aljabar dalam teori kategori dan menghasilkan gagasan yang keduanya berguna bagi ahli matematika tetapi juga meresap dalam praktik pemrograman Haskell.

Saya tidak yakin buku mana yang direkomendasikan, karena saya belum menemukan buku pengantar yang sepenuhnya memuaskan tentang kategori untuk ilmuwan komputer. Anda dapat mencoba Kategori, Jenis, dan Struktur oleh Asperti dan Longo. Idenya adalah untuk mempelajari definisi dasar hingga tambahan, dan kemudian mungkin mencoba dan membaca beberapa blog luar biasa untuk mencoba dan memahami konsep-konsep ini.

Echoing saran @AJed, saya sarankan untuk mengubah pernyataan Anda

I want to learn category theory so I can become better at Haskell.

di atas kepalanya: pelajari Haskell, bangun dari intuisi pemrograman Anda. Setelah Anda menjadi guru FP, mungkin lebih mudah untuk mengambil teori kategori (jika Anda masih peduli).

Teori kategori adalah sederhana untuk seseorang dengan pendidikan matematika luas (kelompok, cincin, modul, ruang vektor, topologi dll). Karena tidak memiliki latar belakang ini, teori kategori hampir tidak dapat ditembus. Keindahan teori kategori adalah bahwa ia menyatukan banyak hal yang tampaknya tidak berhubungan (mis. Adjoint kiri dari fungsi-fungsi yang pelupa termasuk kelompok bebas, aljabar universal yang menyelimuti, pemadatan Stone-Cech, penghapusan kelompok, ...), dan dengan demikian mengurangi kerumitan. Tetapi jika Anda tidak terbiasa dengan banyak contoh yang menyatukan teori kategori, teori kategori hanyalah lapisan kompleksitas tambahan yang membuat hidup Anda lebih sulit.

Dalam pengalaman saya, belajar lebih mudah dengan membangun hal-hal yang sudah diketahui. Sebagai pengembang perangkat lunak, Anda tahu banyak tentang pemrograman, dan pemrograman Haskell tidak jauh berbeda dari pemrograman lain, jadi rekomendasi saya adalah mendekati Haskell dari sudut pandang pemrograman pragmatis, mengabaikan teori kategori. Sedikit teori kategori yang ada di Haskell, misalnya beberapa dukungan untuk monad, jauh lebih mudah bagi seorang programmer untuk memahami tanpa mengambil jalan memutar melalui teori kategori. Lagipula, monad hanyalah komposisi umum (dan Anda akan menggunakan monad dalam praktik pemrograman Anda - walaupun tanpa Anda sadari), dan Haskell tidak benar-benar mendukung monad secara nyata, karena monad tidak menegakkan hukum monadik.

Jawaban singkat: tidak [tapi ini hanya pendapat]

Jangan pergi ke Kategori Teori atau domain teoretis lainnya untuk menjadi baik di Haskell. Pelajari teknik pemrograman fungsional, seperti rekursi ekor, peta, perkecil, dan lainnya. Baca kode sebanyak yang Anda bisa. Terapkan ide sebanyak mungkin. Jika Anda memiliki masalah, baca dan baca.

Jika Anda ingin referensi teoretis yang baik untuk mempelajari Haskell dan paradigma pemrograman fungsional lainnya, maka lihat: Pengantar Pemrograman Fungsional Melalui Lambda Calculus, Greg Michaelson (tersedia online). ... Ada buku serupa lainnya.

Berikut ini adalah posting blog (panjang), yang memberikan motivasi tentang bagaimana ide-ide teori kategori relevan untuk pemrograman praktis: http://cdsmith.wordpress.com/2012/04/18/why-do-monads-matter/

Teori kategori adalah cabang matematika yang sangat canggih dan menguasainya akan menyatukan sebagian besar pembelajaran Anda sebelumnya dengan menjadikannya contoh objek abstrak yang sama. Jadi ini sangat berguna dan sangat intuitif. Tetapi luas dan luas, dan Anda akan menemukan diri Anda dalam banyak konsep baru yang bahkan tidak akan tahu mana yang cocok untuk kebutuhan Anda dan mana yang harus Anda lewatkan. Jadi pendekatan Anda yang disengaja membutuhkan pilihan di antara konsep-konsep, jika tidak menguasai dalam konsep itu pasti membutuhkan waktu yang lama dan benar-benar bukan domain belajar mandiri.

Ngomong-ngomong, saya menyarankan titik awal yang sangat baik untuk tujuan Anda berada di sini .