Teori kategori, kompleksitas komputasi, dan koneksi kombinatorik?

17

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.

cc.complexity-theory co.combinatorics functional-programming ct.category-theory Stefan Petrov
sumber
5
dapatkah Anda memformat ulang agar ini dapat dibaca?
Lev Reyzin
11
Ada dua potensi masalah dengan ide-ide Anda. Pertama, tidak semua struktur data dapat direpresentasikan menggunakan aljabar awal. Grafik umum atau struktur pointer rumit tidak akan menjadi aljabar awal dari functor apa pun. Kedua, aturan fusi dan sebagainya umumnya hanya akan meningkatkan efisiensi kode, daripada mengubah O (-) - efisiensi algoritma (meskipun saya tahu pengecualian).
Dave Clarke
Terima kasih, Dave, saya mencoba membaca buku teori Permainan Algoritmik, dan algoritma dalam perawatan tradisional sebagian besar ditentukan secara operasional, sehingga untuk berbicara, dan bertanya-tanya apakah ada cara umum untuk mendekati mereka, dan aljabar awal dll tampak bagus untuk itu , tetapi kurangnya korespondensi antara struktur data umum dan functors adalah masalah. @ sclv: Terima kasih, saya akan melihatnya!
Stefan Petrov
Saya ingin menunjukkan bahwa ada cara lain untuk merepresentasikan grafik selain dengan struktur pointer yang rumit. Khususnya, seseorang dapat mewakilinya secara induktif, dengan serangkaian perubahan atau penambahan @DaveClarke. Saya yakin hal yang sama berlaku untuk struktur lain seperti ini, meskipun saya tidak ingin mengatakan dengan pasti karena saya bukan ahli tentang aljabar awal dan keterbatasan mereka.
Samuel Schlesinger

Jawaban:

7

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

sclv
sumber
6

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

Chad Brewbaker
sumber