Saya telah mencoba membaca " Mutiara Algoritma Fungsional desain ", dan kemudian " Aljabar Pemrograman ", dan ada korespondensi yang jelas antara rekursif (dan secara polinomi) didefinisikan tipe data dan objek kombinatorial, memiliki definisi rekursif yang sama dan kemudian memimpin untuk seri kekuatan formal yang sama (atau fungsi pembangkit), seperti yang diperlihatkan dalam pengantar spesies kombinatorial (saya membaca " Spesies dan Fungsi dan Jenis, Oh My! ").
Jadi, untuk pertanyaan pertama, apakah ada cara untuk memulihkan persamaan pembangkit (rekursif) dari seri daya? Itu adalah renungan.
Saya lebih tertarik pada gagasan aljabar awal dan aljabar akhir sebagai jenis "mendefinisikan prosedur tentang struktur data". Ada beberapa aturan praktis dalam pemrograman fungsional, mengenai komposisi, produk pemetaan antara aljabar dan sejenisnya, dijelaskan misalnya dalam tutorial ini. Tampak bagi saya bahwa ini bisa menjadi cara yang cukup kuat untuk mendekati kompleksitas dan misalnya, terlihat cukup mudah untuk memulihkan teorema Guru dalam konteks seperti itu (maksud saya, Anda harus melakukan argumen yang sama, jadi tidak banyak keuntungan dalam hal ini), dan katamorfisme unik dari aljabar awal dan fakta (apakah saya salah?) bahwa aljabar antara A dan FA untuk F-polinomial functor adalah isomorfik, membuatnya tampak bagi saya bahwa pendekatan seperti itu dapat memiliki banyak manfaat dalam menganalisis kompleksitas operasi atas struktur data.
Dari sudut pandang praktis, tampak seperti aturan fusi (pada dasarnya, cara-cara untuk menyusun morfisme aljabar satu sama lain, morfisma coalgebra, dan morfisme umum) adalah teknik pengoptimalan yang sangat kuat untuk transformasi dan refactoring program. Apakah saya benar dalam berpikir bahwa pemanfaatan penuh dari aturan-aturan ini dapat menghasilkan program yang optimal (tidak ada struktur data perantara yang tidak perlu atau operasi tambahan lainnya).
Apakah saya ke sesuatu (dan apa) di sini? Apakah penerima manfaat (dari sudut pandang pembelajaran) mencoba melihat kompleksitas komputasi dengan cara ini? Apakah strukturnya, di mana kita dapat memiliki aljabar awal yang "bagus" entah bagaimana terlalu terbatas untuk beberapa masalah?
Saya sebagian besar mencoba menemukan cara untuk berpikir tentang kompleksitas dalam hal struktur ruang pencarian dan cara "ruang pencarian" dan "algoritma pencarian" berinteraksi melalui beberapa objek "baik" seperti aljabar awal dari functor dan untuk memahami apakah berguna untuk mencoba melihat hal-hal seperti ini, ketika melihat struktur yang lebih rumit.
sumber
Jawaban:
Komentar Dave Clarke cukup penting. Umumnya fusi tidak mengubah efisiensi O (-). Namun, yang menarik adalah karya Liu, Cheng, dan Hudak tentang Kausal Commutative Arrows. Program-program yang ditulis dengan mereka perlu dioptimalkan, sebagian melalui aliran fusi, ke satu loop bebas dari alokasi memori dinamis dan struktur perantara: http://haskell.cs.yale.edu/?post_type=publication&p=72
sumber
Spesies Kombinatorial Joyal, "konstruksi yang dapat diterima" Sedgwick / Falojet dari Analytic Combinatorics, dan Spesies Haskell Yorgey semuanya baik.
Power Series Power Serious oleh McIlroy dari UNIX diff fame juga harus dibaca, seperti bab tentang korosi di The Haskell Road to Logic Maths and Programming.
Karya-karya bersejarah oleh Buchi diedit oleh Saunders MacLane dan Chomsky / Schützenberger membuat hubungan antara seri daya, aljabar, pohon, dan automata negara terbatas. Metode Transfer Matriks yang dijelaskan dalam Stanley menunjukkan kepada Anda cara menghitung fungsi-fungsi pembangkit dari automata tertimbang.
Saya masih mencari cara terbaik untuk menerjemahkan antar domain (GF, automata tertimbang, aljabar, pohon, rekursi) secara efisien. Saat ini saya sedang membayar untuk SymPy karena belum ada paket simbol Haskell yang baik.
Secara pribadi, saya telah mengambil grafik iterasi dari endofuksi kemudian menghitung set dominasi min di atasnya untuk mendapatkan ikatan pencarian kotak hitam yang tepat, http://oeis.org/A186202 Tidak yakin apa jenis hasil kompleksitas yang Anda cari, tetapi teknik itu sangat kuat dalam memeriksa endofuksi apapun pada set yang terbatas.
--Original 2 Okt '14 jam 15:37 jawab--
Lihatlah tesis Brent Yorgey yang mengikuti makalah yang Anda kutip. http://www.cis.upenn.edu/%7Ebyorgey/hosted/thesis.pdf
sumber