Pertanyaan Skema rekursi untuk boneka?


Saya mencari beberapa penjelasan yang sangat sederhana, mudah dipahami dari skema rekursi dan skema corecursion (catamorphisms, anamorphisms, hylomorphisms dll) yang tidak memerlukan banyak link berikut, atau membuka buku teks teori kategori. Saya yakin saya telah menemukan kembali banyak skema ini secara tidak sadar dan "menerapkan" mereka di kepala saya selama proses pengkodean (saya yakin banyak dari kita memiliki), tetapi saya tidak tahu apa skema rekursi (co) saya gunakan disebut. (OK, saya berbohong. Saya baru saja membaca tentang beberapa dari mereka, yang mendorong pertanyaan ini. Tapi sebelum hari ini, saya tidak tahu.)

Saya pikir difusi dari konsep-konsep ini dalam komunitas pemrograman telah dihalangi oleh penjelasan yang mengerikan dan contoh yang cenderung muncul - misalnya di Wikipedia, tetapi juga di tempat lain.

Itu juga mungkin terhalang oleh nama mereka. Saya pikir ada beberapa alternatif, kurang nama matematis (sesuatu tentang pisang dan kawat berduri?) Tetapi saya tidak tahu apa nama cutsier untuk skema rekursi yang saya gunakan juga.

Saya pikir itu akan membantu untuk menggunakan contoh dengan tipe data yang mewakili masalah dunia nyata sederhana, daripada tipe data abstrak seperti pohon biner.


76
2017-08-04 13:03


asal


Jawaban:


Sangat longgar berbicara, catamorfisme hanyalah sedikit generalisasi fold, dan anamorphism adalah sedikit generalisasi unfold. (Dan hylomorphism hanyalah sebuah pembukaan diikuti oleh lipatan.). Mereka disajikan dalam bentuk yang lebih ketat biasanya, untuk membuat koneksi ke teori kategori lebih jelas. Bentuk yang lebih padat memungkinkan kita membedakan data (produk berhingga dari aljabar awal) dan codata (kemungkinan produk tak terbatas dari batubara akhir). Perbedaan ini memungkinkan kami menjamin bahwa lipatan tidak pernah dipanggil pada daftar tak terbatas. Alasan lain untuk cara lucu bahwa catamorphisms dan anamorphisms umumnya ditulis adalah bahwa dengan beroperasi di atas F-algebras dan F-coalgebras (dihasilkan dari functor) kita dapat menulisnya sekali dan untuk semua, daripada sekali lagi di atas daftar, sekali di atas pohon biner, dll. Ini pada gilirannya membantu memperjelas secara tepat Mengapa mereka semua sama saja.

Tetapi dari sudut pandang intuisi murni, Anda dapat menganggap cata dan ana sebagai pereduksi dan produksi, dan itu saja.

Edit: sedikit lagi

Sebuah metamorfisme (Gibbons) seperti hylo luar-dalam - lipatannya yang diikuti oleh sebuah terungkap. Jadi Anda dapat menggunakannya untuk meruntuhkan aliran dan membangun yang baru dengan struktur yang berpotensi berbeda.

Ekmett memposting "panduan lapangan" yang bagus ke berbagai skema dalam literatur: http://comonad.com/reader/2009/recursion-schemes/

Namun, sementara penjelasan "intuitif" sangat mudah, kode yang terhubung kurang begitu, dan posting blog pada beberapa di antaranya mungkin sedikit di sisi yang kompleks / melarang.

Yang mengatakan, kecuali mungkin untuk histomorphisms saya tidak berpikir sisa kebun binatang adalah sesuatu yang pasti ingin Anda pikirkan secara langsung sebagian besar waktu. Jika Anda "mendapatkan" hylo dan meta, Anda dapat mengekspresikan hampir apa pun hanya dari mereka. Biasanya morfisme lain lebih restriktif, tidak kurang (tetapi karena itu memberi Anda lebih banyak properti "gratis").


39
2017-08-04 15:06



Beberapa referensi, dari kebanyakan kategori-teoritis (tetapi relevan untuk memberikan "peta wilayah" yang akan membiarkan Anda menghindari "mengklik banyak tautan") ke yang lebih sederhana & lebih lengkap:

  • Sejauh kosakata "pisang & kawat berduri" pergi, ini berasal kertas asli Meijer, Fokkinga & Patterson (dan sekuelnya oleh penulis lain), dan jumlahnya sama seperti notasi-berat sebagai alternatif yang kurang lucu: "nama" (pisang, dll) hanyalah jalan pintas ke tampilan grafis notasi ascii dari konstruksi mereka dipatok. Misalnya, katamorfisme (misalnya lipatan) diwakili dengan (| _ |), dan par-dengan-tanda kurung terlihat seperti "pisang", maka namanya. Ini adalah kertas yang paling sering disebut "tidak dapat ditembus", maka bukan hal pertama yang saya cari jika saya adalah Anda.

  • Referensi dasar untuk skema rekursi (atau lebih tepatnya, untuk pendekatan relasional untuk skema rekursi) adalah Bird & de Moor Aljabar Pemrograman (buku tidak tersedia kecuali sebagai print-on demand, tetapi ada salinan yang tersedia bekas & itu harus di perpustakaan). Ini berisi penjelasan yang lebih terperinci & terperinci tentang pemrograman bebas-titik, jika masih "akademis": buku ini memperkenalkan beberapa kosa kata kategori-teoretis, meskipun dengan cara yang berdiri sendiri. Namun, latihan (yang tidak Anda temukan di kertas) membantu.

  • Menyortir morfisme oleh Lex Augustjein, menggunakan algoritma pengurutan pada berbagai struktur data untuk menjelaskan skema rekursi. Itu cukup banyak "skema rekursif untuk dummies"dengan konstruksi:

    Presentasi ini memberikan kesempatan untuk memperkenalkan berbagai morfisme di   cara sederhana, yaitu sebagai pola rekursi yang berguna dalam pemrograman fungsional, daripada pendekatan biasa melalui teori kategori, yang cenderung tidak perlu mengintimidasi programmer rata-rata.

  • Pendekatan lain untuk membuat presentasi bebas simbol adalah Bab Jeremy Gibbons Origami Programming di The Fun of Programming, dengan beberapa tumpang tindih dengan yang sebelumnya. Bibliografi yang memberikan tur pengenalan ke topik.

    Edit: Jeremy Gibbons beri tahu saya bahwa dia telah menambahkan tautan ke bibliografi seluruh buku di halaman web buku setelah membaca pertanyaan ini. Nikmati !

Saya khawatir kedua referensi terakhir ini hanya memberikan penjelasan yang kuat tentang morfisme (cata | ana | hylo | para), tetapi harapan saya adalah bahwa ini akan cukup untuk menghancurkan formalisme aljabar yang dapat Anda temukan di lebih banyak publikasi notasi-berat. Saya tidak tahu ada penjelasan ketat non-kategori-teoretis tentang skema rekursi (co-) selain empat itu.


22
2017-08-05 23:28



Tim Williams memberikan ceramah cemerlang di Grup Pengguna London Haskell tadi malam tentang skema rekursi dengan contoh motivasi dari masing-masing yang Anda sebutkan. Lihat slide:

http://www.timphilipwilliams.com/slides.html

Ada referensi untuk semua tersangka yang biasa (lensa, pisang, kawat berduri ala carte dll) di akhir slide dan Anda juga bisa google "Origami Programming" yang merupakan intro bagus yang belum pernah saya temui sebelumnya.

dan video akan ada di sini ketika diunggah:

http://www.youtube.com/user/LondonHaskell

sunting Sebagian besar tautan yang dimaksud berada dalam jawaban huitseeker di atas.


15
2018-03-28 16:56