Menjelaskan fungsi aplikatif dalam istilah kategorikal - fungsi monoid

Saya ingin memahami Applicativedalam hal teori kategori.

The dokumentasi untuk Applicativemengatakan bahwa itu functor longgar monoidal kuat .

Pertama, Wikipedia halaman tentang functors monoidal mengatakan bahwa functor monoidal adalah baik longgar atau kuat . Jadi menurut saya salah satu sumber salah, atau mereka menggunakan istilah secara berbeda. Adakah yang bisa menjelaskannya?

Kedua, apa kategori monoid yang merupakan fungsi monoid Applicative? Saya berasumsi bahwa functors adalah endo-functors pada kategori Haskell standar (objek = tipe, morfisme = fungsi), tetapi saya tidak tahu apa struktur monoid pada kategori ini.

Terimakasih atas bantuannya.

lo.logic type-theory functional-programming ct.category-theory Petr Pudlák
sumber

Jawaban:

Sebenarnya ada dua penggunaan kata "kekuatan" dalam permainan di sini.

Seorang endofunctor yang kuat atas kategori monoid adalah yang datang dengan transformasi alami , memuaskan beberapa kondisi koherensi berkenaan dengan associator yang akan saya bahas. Kondisi ini terkadang juga diucapkan " memiliki kekuatan". $F : C \to C$ $(C, \otimes, I)$ $\sigma : A \otimes F(B) \to F(A \otimes B)$ $F$
Sebuah longgar monoidal functor adalah functor antara dua kategori monoidal dan dengan transformasi alam dan , sekali lagi memenuhi kondisi koherensi sehubungan dengan associators. $F : C \to D$ $(C, \otimes, I)$ $(D, \oplus, J)$ $\phi : F(A) \oplus F(B) \to F(A \otimes B)$ $i : J \to F(I)$
Fungsi monoid yang kuat adalah fungsi di mana dan adalah isomorfisme alami. Yaitu, , dengan dan kebalikannya yang menggambarkan isomorfisme. $F : C \to D$ $\phi$ $i$ $F(A \otimes B) \simeq F(A) \oplus F(B)$ $\phi$

Functor aplikatif, dalam arti program Haskell, adalah endofunctor longgar lemah dengan kekuatan , dengan struktur monoid yang dimaksud adalah produk Cartesian. Jadi ini adalah mengapa Anda mendapatkan istilah yang terdengar paradoks "kuat lemah fungsi monoid".

Selain itu, dalam kategori tertutup Cartesian, memiliki kekuatan setara dengan keberadaan transformasi alami . Artinya, memiliki kekuatan berarti bahwa tindakan functorial dapat didefinisikan sebagai fungsi tingkat tinggi dalam bahasa pemrograman. $F$ $\mathrm{map} : (A \Rightarrow B) \to (F(A) \Rightarrow F(B))$

Akhirnya, jika Anda tertarik pada teori jenis fungsi aplikatif gaya Haskell, saya baru saja membuat blog tentang hal itu.

Neel Krishnaswami
sumber

Terima kasih atas jawabannya. Apakah saya memahaminya dengan benar bahwa semua instance Functormemiliki kekuatan (produk WRT), hanya karena mereka didefinisikan menggunakan fmapdi dalam bahasa? Juga, apa yang membingungkan saya bahwa definisi Anda tentang dan terbalik dibandingkan dengan posting blog Anda dan artikel Wikipedia - apakah ini salah ketik? Saya mencoba mendefinisikan menggunakan sebagai , yang jelas perlu .

ϕ

$\phi$

i

$i$ pureipure' = \v -> fmap (\() -> v) (i ())i :: (Applicative f) => () -> f ()

Petr Pudlák

Saya memiliki kesalahan ketik dalam jawaban ini - sekarang diperbaiki. Dan ya, semua contoh Functorkuat (wrt produk).

Neel Krishnaswami

Bisakah Anda juga menjelaskan di mana Monad berdiri? Jika saya mengerti benar itu adalah endofunctor monoid juga.

egdmitry

@ agdmitry Monoidal , bukan monadal . Ini berarti kita berurusan dengan endofunctor dari kategori monoid (dalam hal ini menjadi monoid relatif terhadap produk kartesius, yaitu pasangan).

Hask

$\operatorname{Hask}$

kirelagin

Bolehkah saya mengusulkan untuk menggunakan kata kuat untuk menghindari benturan notasi dengan "kuat"? Ini adalah variasi dialek "kuat" dari bahasa Skotlandia (jadi sangat tepat di sini), yang pertama kali digunakan dalam Alkitab Wycliffe.

Fosco

Untuk memahami Applicative, seperti yang diinduksi oleh monad, saya ingin menunjukkan konstruksi berikut:

Lemma Yoneda menyiratkan bahwa ada isomorfisme antara dan . Dalam kategori tipe Haskell, ini adalah pemetaan dari tipe Mengevaluasi , lalu menerapkan peta panah functors ke fungsi yang dihasilkan - jika komponen transformasi alami masuk akal sebagai panah - dan mengabstraksi lagi, kami memperoleh pemetaan tipe Sekarang jika functor datang dengan 'join' monadik, pemetaan dari ke $FA$ $\mathrm{nat}(\mathrm{Hom}(A,B),FB)$

a \mapsto (g \mapsto F (g) (a))

$a\mapsto\left(g\mapsto F(g)(a)\right)$

F A \to B^{A} \to F B .

$FA\to B^A\to FB.$

F A

$FA$

F A

$FA$

F A \to F B^{A} \to F F B .

$FA\to F\,B^A\to FFB.$

F F B

$FFB$

F B

$FB$ , dan jika kita beralih di sekitar abstraksi lambda dan dengan demikian dua slot argumen pertama, kita dapat memperoleh fungsi tipe yang ditunjukkan oleh <*>. (Ini juga yang Anda dapatkan melalui di Haskell.)

F B^{A} \to F A \to F B,

$F\,B^A\to FA\to FB,$

L i f t M 2 i d

$\mathrm{LiftM2\ id}$

Nikolaj-K
sumber