Saya telah mendengar istilah "coalgebras" beberapa kali dalam pemrograman fungsional dan lingkaran PLT, terutama ketika diskusi tentang objek, comonad, lensa, dan semacamnya. Googling istilah ini memberikan halaman-halaman yang memberikan deskripsi matematis dari struktur-struktur ini yang sangat tidak bisa saya pahami. Adakah yang bisa menjelaskan apa arti coalgebras dalam konteks pemrograman, apa signifikansinya, dan bagaimana kaitannya dengan objek dan comonad?
scala
haskell
functional-programming
category-theory
recursion-schemes
missingfaktor
sumber
sumber
Jawaban:
Aljabar
Saya pikir tempat untuk memulai adalah untuk memahami ide aljabar . Ini hanyalah generalisasi dari struktur aljabar seperti grup, cincin, monoids dan sebagainya. Sebagian besar waktu, hal-hal ini diperkenalkan dalam hal set, tetapi karena kita berada di antara teman-teman, saya akan berbicara tentang tipe Haskell sebagai gantinya. (Tapi aku tidak bisa menolak menggunakan beberapa huruf Yunani — mereka membuat semuanya terlihat lebih keren!)
Aljabar, kemudian, hanyalah tipe
τ
dengan beberapa fungsi dan identitas. Fungsi-fungsi ini mengambil jumlah argumen yang berbeda dari jenisτ
dan menghasilkanτ
: tidak terburu-buru, semuanya terlihat seperti(τ, τ,…, τ) → τ
. Mereka juga dapat memiliki "identitas" - elemenτ
yang memiliki perilaku khusus dengan beberapa fungsi.Contoh paling sederhana dari ini adalah monoid. Monoid adalah jenis apa pun
τ
dengan fungsimappend ∷ (τ, τ) → τ
dan identitasmzero ∷ τ
. Contoh lain termasuk hal-hal seperti kelompok (yang seperti monoids kecuali denganinvert ∷ τ → τ
fungsi tambahan ), cincin, kisi dan sebagainya.Semua fungsi beroperasi
τ
tetapi dapat memiliki fungsi yang berbeda. Kita bisa menuliskan ini sebagaiτⁿ → τ
, di manaτⁿ
peta ke tuplen
τ
. Dengan cara ini, masuk akal untuk memikirkan identitas sebagai diτ⁰ → τ
manaτ⁰
hanya tuple kosong()
. Jadi kita sebenarnya dapat menyederhanakan ide aljabar sekarang: itu hanya beberapa jenis dengan beberapa fungsi di atasnya.Aljabar hanyalah pola umum dalam matematika yang telah "difaktorkan", seperti yang kita lakukan dengan kode. Orang-orang memperhatikan bahwa banyak hal menarik — monoid, kelompok, kisi, dan sebagainya yang disebutkan di atas — semuanya mengikuti pola yang sama, sehingga mereka mencabutnya. Keuntungan melakukan ini sama dengan pemrograman: ia menciptakan bukti yang dapat digunakan kembali dan membuat jenis penalaran tertentu lebih mudah.
F-Algebras
Namun, kami belum cukup selesai dengan anjak piutang. Sejauh ini, kami memiliki banyak fungsi
τⁿ → τ
. Kita sebenarnya dapat melakukan trik yang rapi untuk menggabungkan semuanya menjadi satu fungsi. Secara khusus, mari kita lihat monoids: yang kita milikimappend ∷ (τ, τ) → τ
danmempty ∷ () → τ
. Kita bisa mengubahnya menjadi fungsi tunggal menggunakan tipe penjumlahan—Either
. Akan terlihat seperti ini:Kami benar-benar dapat menggunakan transformasi ini berulang kali untuk menggabungkan semua yang
τⁿ → τ
fungsi ke dalam satu, untuk setiap aljabar. (Bahkan, kita bisa melakukan ini untuk sejumlah fungsia → τ
,b → τ
dan seterusnya untuk apa puna, b,…
.)Ini memungkinkan kita berbicara tentang aljabar sebagai tipe
τ
dengan fungsi tunggal dari beberapa kekacauanEither
s ke satuτ
. Untuk monoids, kekacauan ini adalah:Either (τ, τ) ()
; untuk kelompok (yang memiliki tambahanτ → τ
operasi), itu:Either (Either (τ, τ) τ) ()
. Ini adalah tipe yang berbeda untuk setiap struktur yang berbeda. Jadi apa kesamaan semua tipe ini? Yang paling jelas adalah bahwa semuanya hanyalah jumlah produk — tipe data aljabar. Sebagai contoh, untuk monoids, kita bisa menciptakan jenis argumen monoid yang bekerja untuk setiap monoid τ:Kita dapat melakukan hal yang sama untuk grup dan cincin dan kisi dan semua struktur lain yang mungkin.
Apa lagi yang spesial dari semua tipe ini? Ya mereka semua
Functors
! Misalnya:Jadi kita bisa menggeneralisasi ide aljabar kita lebih jauh lagi. Hanya beberapa tipe
τ
dengan fungsif τ → τ
untuk beberapa functorf
. Bahkan, kita bisa menuliskan ini sebagai typeclass:Ini sering disebut "aljabar-F" karena ditentukan oleh functor
F
. Jika kita dapat menerapkan sebagian kacamata ketik, kita dapat mendefinisikan sesuatu seperticlass Monoid = Algebra MonoidArgument
.Coalgebras
Sekarang, semoga Anda memiliki pemahaman yang baik tentang apa itu aljabar dan bagaimana itu hanya generalisasi dari struktur aljabar normal. Jadi apa itu F-coalgebra? Nah, co menyiratkan bahwa itu adalah "ganda" dari aljabar — yaitu, kita mengambil aljabar dan membalik beberapa panah. Saya hanya melihat satu panah dalam definisi di atas, jadi saya akan membalikkan itu:
Dan hanya itu! Sekarang, kesimpulan ini mungkin tampak sedikit kurang ajar (heh). Ini memberi tahu Anda apa itu coalgebra, tetapi tidak benar-benar memberikan wawasan tentang manfaatnya atau mengapa kami peduli. Saya akan membahasnya sedikit, setelah saya menemukan atau menghasilkan satu atau dua contoh yang baik: P.
Kelas dan Objek
Setelah membaca sedikit, saya pikir saya punya ide bagus tentang cara menggunakan coalgebras untuk mewakili kelas dan objek. Kami memiliki tipe
C
yang berisi semua kemungkinan keadaan internal objek di kelas; kelas itu sendiri adalah suatu coalgebraC
yang menspesifikasikan metode dan properti objek.Seperti yang ditunjukkan pada contoh aljabar, jika kita memiliki banyak fungsi seperti
a → τ
danb → τ
untuk apa puna, b,…
, kita dapat menggabungkan semuanya menjadi satu fungsi menggunakanEither
, tipe penjumlahan. "Gagasan" ganda akan menggabungkan banyak fungsi tipeτ → a
,τ → b
dan seterusnya. Kita bisa melakukan ini menggunakan dual tipe penjumlahan — tipe produk. Jadi mengingat dua fungsi di atas (dipanggilf
dang
), kita dapat membuat satu seperti:Tipe
(a, a)
ini adalah functor dengan cara yang langsung, jadi tentu saja sesuai dengan gagasan kami tentang F-coalgebra. Trik khusus ini memungkinkan kita mengemas sekelompok fungsi yang berbeda — atau, untuk OOP, metode — menjadi satu fungsi tipeτ → f τ
.Elemen-elemen dari tipe kami
C
mewakili keadaan internal objek. Jika objek memiliki beberapa properti yang dapat dibaca, mereka harus dapat bergantung pada keadaan. Cara yang paling jelas untuk melakukan ini adalah membuat mereka berfungsiC
. Jadi jika kita menginginkan properti panjang (misalnyaobject.length
), kita akan memiliki fungsiC → Int
.Kami ingin metode yang dapat mengambil argumen dan memodifikasi keadaan. Untuk melakukan ini, kita perlu mengambil semua argumen dan menghasilkan yang baru
C
. Mari kita bayangkan sebuahsetPosition
metode yang mengambil sebuahx
dany
koordinat:object.setPosition(1, 2)
. Ini akan terlihat seperti ini:C → ((Int, Int) → C)
.Pola penting di sini adalah bahwa "metode" dan "properti" dari objek mengambil objek itu sendiri sebagai argumen pertama mereka. Ini seperti
self
parameter dalam Python dan seperti implisitthis
banyak bahasa lainnya. Sebuah coalgebra dasarnya hanya merangkum perilaku mengambilself
parameter: itulah yang pertamaC
diC → F C
adalah.Jadi mari kita kumpulkan semuanya. Mari kita bayangkan kelas dengan
position
properti, properti,name
dansetPosition
fungsi:Kami membutuhkan dua bagian untuk mewakili kelas ini. Pertama, kita perlu mewakili keadaan internal objek; dalam hal ini hanya memiliki dua
Int
s dan aString
. (Ini adalah tipe kitaC
.) Maka kita perlu membuat bilangan batu bara yang mewakili kelas.Kami memiliki dua properti untuk ditulis. Mereka cukup sepele:
Sekarang kita hanya perlu dapat memperbarui posisi:
Ini seperti kelas Python dengan
self
variabel eksplisitnya . Sekarang kita memiliki banyakself →
fungsi, kita harus menggabungkannya menjadi satu fungsi untuk batubara. Kita bisa melakukan ini dengan tuple sederhana:Jenis
((Int, Int), String, (Int, Int) → c)
-untuk setiapc
-adalah functor, sehinggacoop
memang memiliki bentuk yang kita inginkan:Functor f ⇒ C → f C
.Mengingat hal ini,
C
bersama dengancoop
membentuk sebuah coalgebra yang menentukan kelas yang saya berikan di atas. Anda dapat melihat bagaimana kita dapat menggunakan teknik yang sama ini untuk menentukan sejumlah metode dan properti yang dimiliki objek kita.Ini memungkinkan kami menggunakan alasan coalgebraic untuk berurusan dengan kelas. Sebagai contoh, kita dapat membawa gagasan tentang "homomorfisme F-coalgebra" untuk mewakili transformasi antar kelas. Ini adalah istilah yang menakutkan yang hanya berarti transformasi antara batubara batubara yang mempertahankan struktur. Ini membuatnya lebih mudah untuk berpikir tentang memetakan kelas ke kelas lain.
Singkatnya, F-coalgebra mewakili kelas dengan memiliki banyak properti dan metode yang semuanya bergantung pada
self
parameter yang berisi keadaan internal masing-masing objek.Kategori Lainnya
Sejauh ini, kita telah berbicara tentang algebras dan coalgebras sebagai tipe Haskell. Aljabar hanya tipe
τ
dengan fungsif τ → τ
dan aljabar hanya tipeτ
dengan fungsiτ → f τ
.Namun, tidak ada yang benar-benar mengikat ide-ide untuk Haskell per se . Bahkan, mereka biasanya diperkenalkan dalam hal set dan fungsi matematika daripada tipe dan fungsi Haskell. Memang, kita dapat menggeneralisasi konsep-konsep ini ke kategori apa pun !
Kita dapat mendefinisikan aljabar F untuk beberapa kategori
C
. Pertama, kita membutuhkan functorF : C → C
—yaitu, endofunctor . (Semua HaskellFunctor
sebenarnya adalah endofunctors dariHask → Hask
.) Kemudian, aljabar hanyalah objekA
dariC
dengan morfismeF A → A
. Sebuah batubara adalah sama kecuali denganA → F A
.Apa yang kita dapatkan dengan mempertimbangkan kategori lain? Kita dapat menggunakan ide yang sama dalam konteks yang berbeda. Seperti monad. Di Haskell, monad adalah beberapa tipe
M ∷ ★ → ★
dengan tiga operasi:The
map
Fungsi hanya bukti fakta bahwaM
adalahFunctor
. Jadi kita dapat mengatakan bahwa monad hanya berfungsi dengan dua operasi:return
danjoin
.Functors membentuk kategori sendiri, dengan morfisme di antara mereka yang disebut "transformasi alami". Transformasi alami hanyalah cara untuk mengubah satu fungsi menjadi yang lain sambil mempertahankan strukturnya. Inilah artikel yang bagus membantu menjelaskan ide itu. Itu berbicara tentang
concat
, yang hanyajoin
untuk daftar.Dengan Haskell functors, komposisi dua functors adalah functor itu sendiri. Dalam pseudocode, kita bisa menulis ini:
Ini membantu kita berpikir
join
sebagai pemetaan darif ∘ f → f
. Jenisnyajoin
adalah∀α. f (f α) → f α
. Secara intuitif, kita dapat melihat bagaimana suatu fungsi valid untuk semua tipeα
dapat dianggap sebagai suatu transformasi darif
.return
adalah transformasi serupa. Jenisnya adalah∀α. α → f α
. Ini terlihat berbeda — yang pertamaα
bukan "di" functor! Untungnya, kita bisa memperbaiki ini dengan menambahkan sebuah functor identitas sana:∀α. Identity α → f α
. Begitureturn
juga transformasiIdentity → f
.Sekarang kita dapat berpikir tentang monad hanya sebagai aljabar yang didasarkan pada beberapa fungsi
f
dengan operasif ∘ f → f
danIdentity → f
. Bukankah ini terlihat familier? Ini sangat mirip dengan monoid, yang hanya beberapa tipeτ
dengan operasiτ × τ → τ
dan() → τ
.Jadi monad seperti monoid, kecuali alih-alih memiliki tipe, kita memiliki functor. Ini adalah aljabar yang sama, hanya dalam kategori yang berbeda. (Di sinilah frasa "Monad hanya monoid dalam kategori endofunctors" berasal sejauh yang saya tahu.)
Sekarang, kami memiliki dua operasi ini:
f ∘ f → f
danIdentity → f
. Untuk mendapatkan coalgebra yang sesuai, kita cukup membalikkan panah. Ini memberi kami dua operasi baru:f → f ∘ f
danf → Identity
. Kita bisa mengubahnya menjadi tipe Haskell dengan menambahkan variabel tipe seperti di atas, memberi kita∀α. f α → f (f α)
dan∀α. f α → α
. Ini terlihat seperti definisi comonad:Jadi comonad kemudian menjadi sebuah coalgebra dalam kategori endofunctors.
sumber
(,)
dan functor identitas()
. Objek monoid dalam kategori monoid adalah objek dengan panah yang sesuai dengan aljabar monoid Anda, yang menggambarkan objek monoid dalam Hask dengan jenis produk sebagai struktur monoid. Objek monoid dalam kategori endofunctors pada C adalah monad pada C, jadi ya, pemahaman Anda benar. :]F-algebras dan F-coalgebras adalah struktur matematika yang berperan dalam penalaran tentang tipe induktif (atau tipe rekursif ).
F-aljabar
Kami akan mulai dulu dengan F-algebras. Saya akan berusaha sesederhana mungkin.
Saya kira Anda tahu apa itu tipe rekursif. Misalnya, ini adalah tipe untuk daftar bilangan bulat:
Jelas bahwa itu adalah rekursif - memang, definisi itu merujuk pada dirinya sendiri. Definisinya terdiri dari dua konstruktor data, yang memiliki tipe berikut:
Perhatikan bahwa saya telah menulis tipe
Nil
as() -> IntList
, bukan hanyaIntList
. Ini sebenarnya adalah tipe yang setara dari sudut pandang teoretis, karena()
tipe hanya memiliki satu penduduk.Jika kita menulis tanda tangan dari fungsi-fungsi ini dengan cara yang lebih teoritis, kita akan mendapatkannya
di mana
1
satu set unit (set dengan satu elemen) danA × B
operasi adalah produk silang dari dua setA
danB
(yaitu, set pasangan(a, b)
manaa
melewati semua elemenA
danb
melewati semua elemen dariB
).Disjoint penyatuan dua set
A
danB
merupakan setA | B
yang merupakan penyatuan set{(a, 1) : a in A}
dan{(b, 2) : b in B}
. Pada dasarnya itu adalah satu set semua elemen dari keduanyaA
danB
, tetapi dengan masing-masing elemen ini 'ditandai' sebagai milik salah satuA
atauB
, jadi ketika kita mengambil elemen dariA | B
kita akan segera tahu apakah elemen ini berasalA
atau dariB
.Kami dapat 'bergabung'
Nil
danCons
fungsi, sehingga mereka akan membentuk satu fungsi yang bekerja pada set1 | (Int × IntList)
:Memang, jika
Nil|Cons
fungsi diterapkan pada()
nilai (yang, jelas, milik1 | (Int × IntList)
set), maka berperilaku seolah-olah ituNil
; jikaNil|Cons
diterapkan pada nilai tipe apa pun(Int, IntList)
(nilai tersebut juga ada di set1 | (Int × IntList)
, itu berlaku sebagaiCons
.Sekarang pertimbangkan tipe data lain:
Ini memiliki konstruktor berikut:
yang juga bisa digabung menjadi satu fungsi:
Dapat dilihat bahwa kedua
joined
fungsi ini memiliki tipe yang sama: keduanya terlihat sepertidi mana
F
adalah jenis transformasi yang mengambil tipe kita dan memberikan tipe yang lebih kompleks, yang terdiri darix
dan|
operasi, penggunaanT
dan mungkin tipe lainnya. Misalnya, untukIntList
danIntTree
F
terlihat sebagai berikut:Kita dapat segera melihat bahwa semua jenis aljabar dapat ditulis dengan cara ini. Memang, itulah sebabnya mereka disebut 'aljabar': mereka terdiri dari sejumlah 'jumlah' (serikat pekerja) dan 'produk' (produk silang) dari jenis lain.
Sekarang kita dapat mendefinisikan aljabar F. Aljabar F hanyalah sepasang
(T, f)
, di manaT
ada beberapa jenis danf
merupakan fungsi dari jenisf :: F T -> T
. Dalam contoh-contoh kami F-aljabar adalah(IntList, Nil|Cons)
dan(IntTree, Leaf|Branch)
. Namun, perlu diketahui bahwa meskipun jenisf
fungsinya sama untuk masing-masing F,T
danf
dirinya sendiri dapat arbitrer. Misalnya,(String, g :: 1 | (Int x String) -> String)
atau(Double, h :: Int | (Double, Double) -> Double)
untuk beberapag
danh
juga F-aljabar untuk F. yang sesuaiSetelah itu kita dapat memperkenalkan homomorfisme aljabar F-aljabar dan kemudian memulai aljabar F-aljabar , yang memiliki sifat yang sangat berguna. Sebenarnya,
(IntList, Nil|Cons)
adalah aljabar F1 awal, dan(IntTree, Leaf|Branch)
merupakan aljabar F2 awal. Saya tidak akan menyajikan definisi yang tepat dari istilah dan properti ini karena mereka lebih kompleks dan abstrak daripada yang dibutuhkan.Meskipun demikian, fakta bahwa, katakanlah,
(IntList, Nil|Cons)
aljabar-F memungkinkan kita untuk mendefinisikanfold
fungsi seperti pada tipe ini. Seperti yang Anda ketahui, fold adalah semacam operasi yang mengubah beberapa tipe data rekursif dalam satu nilai terbatas. Misalnya, kita bisa melipat daftar bilangan bulat menjadi nilai tunggal yang merupakan jumlah semua elemen dalam daftar:Dimungkinkan untuk menggeneralisasi operasi semacam itu pada setiap tipe data rekursif.
Berikut ini adalah tanda tangan
foldr
fungsi:Perhatikan bahwa saya telah menggunakan kawat gigi untuk memisahkan dua argumen pertama dari yang terakhir. Ini bukan
foldr
fungsi nyata , tetapi isomorfis dengannya (yaitu, Anda dapat dengan mudah mendapatkan satu dari yang lain dan sebaliknya). Sebagian diterapkanfoldr
akan memiliki tanda tangan berikut:Kita dapat melihat bahwa ini adalah fungsi yang mengambil daftar bilangan bulat dan mengembalikan bilangan bulat tunggal. Mari kita definisikan fungsi seperti itu dalam hal
IntList
tipe kita .Kita melihat bahwa fungsi ini terdiri dari dua bagian: bagian pertama mendefinisikan perilaku fungsi ini pada
Nil
bagian dariIntList
, dan bagian kedua mendefinisikan perilaku fungsi padaCons
bagian.Sekarang anggaplah kita memprogram bukan dalam Haskell tetapi dalam beberapa bahasa yang memungkinkan penggunaan tipe-tipe aljabar secara langsung dalam tipe tanda tangan (yah, secara teknis Haskell memungkinkan penggunaan tipe-tipe aljabar melalui tupel dan
Either a b
tipe data, tetapi ini akan mengarah pada verbositas yang tidak perlu). Pertimbangkan fungsi:Dapat dilihat bahwa
reductor
ini adalah fungsi dari tipeF1 Int -> Int
, seperti dalam definisi aljabar F! Memang, pasangan(Int, reductor)
adalah aljabar F1.Karena
IntList
merupakan F1-aljabar awal, untuk setiap jenisT
dan untuk setiap fungsir :: F1 T -> T
terdapat fungsi, yang disebut catamorphism untukr
, yang bertobatIntList
untukT
, dan fungsi tersebut adalah unik. Memang, dalam contoh kita, katamorfismereductor
adalahsumFold
. Perhatikan bagaimanareductor
dansumFold
mirip: mereka memiliki struktur yang hampir sama! Dalamreductor
definisis
parameter, penggunaan (tipe yang sesuai denganT
) sesuai dengan penggunaan hasil perhitungansumFold xs
dalamsumFold
definisi.Hanya untuk membuatnya lebih jelas dan membantu Anda melihat polanya, berikut adalah contoh lain, dan kita kembali mulai dari fungsi lipat yang dihasilkan. Pertimbangkan
append
fungsi yang menambahkan argumen pertama ke argumen kedua:Ini tampilannya pada kita
IntList
:Sekali lagi, mari kita coba menuliskan reduktor:
appendFold
adalah katamorfismeappendReductor
yang ditransformasikanIntList
menjadiIntList
.Jadi, pada dasarnya, F-algebras memungkinkan kita untuk mendefinisikan 'lipatan' pada struktur data rekursif, yaitu operasi yang mengurangi struktur kita ke beberapa nilai.
F-coalgebras
F-coalgebras adalah istilah yang disebut 'ganda' untuk F-algebras. Mereka memungkinkan kita untuk menentukan
unfolds
tipe data rekursif, yaitu cara untuk membangun struktur rekursif dari beberapa nilai.Misalkan Anda memiliki tipe berikut:
Ini adalah aliran bilangan bulat tanpa batas. Satu-satunya konstruktor memiliki jenis berikut:
Atau, dalam hal set
Haskell memungkinkan Anda untuk mencocokkan pola pada konstruktor data, sehingga Anda dapat menentukan fungsi berikut yang bekerja pada
IntStream
s:Anda secara alami dapat 'menggabungkan' fungsi-fungsi ini menjadi satu fungsi tipe
IntStream -> Int × IntStream
:Perhatikan bagaimana hasil fungsi bertepatan dengan representasi aljabar dari
IntStream
tipe kita . Hal serupa juga dapat dilakukan untuk tipe data rekursif lainnya. Mungkin Anda sudah memperhatikan polanya. Saya mengacu pada keluarga fungsi tipedimana
T
beberapa tipe. Mulai sekarang kita akan mendefinisikanSekarang, F-coalgebra adalah pasangan
(T, g)
, di manaT
adalah tipe dang
merupakan fungsi dari tipeg :: T -> F T
. Sebagai contoh,(IntStream, head&tail)
adalah F1-coalgebra. Sekali lagi, seperti dalam F-algebras,g
danT
dapat berubah-ubah, misalnya,(String, h :: String -> Int x String)
juga merupakan F1-coalgebra untuk beberapa jam.Di antara semua F-coalgebras ada yang disebut terminal F-coalgebras , yang merupakan dwi-aljabar F-coal. Sebagai contoh,
IntStream
adalah terminal F-coalgebra. Ini berarti bahwa untuk setiap jenisT
dan untuk setiap fungsip :: T -> F1 T
terdapat fungsi, yang disebut anamorphism , yang dikonversiT
menjadiIntStream
, dan fungsi tersebut adalah unik.Pertimbangkan fungsi berikut, yang menghasilkan aliran bilangan bulat berturut-turut mulai dari yang diberikan:
Sekarang mari kita periksa fungsi
natsBuilder :: Int -> F1 Int
, yaitunatsBuilder :: Int -> Int × Int
:Sekali lagi, kita dapat melihat beberapa kesamaan antara
nats
dannatsBuilder
. Ini sangat mirip dengan koneksi yang telah kami amati dengan reduktor dan lipatan sebelumnya.nats
adalah anamorphism untuknatsBuilder
.Contoh lain, fungsi yang mengambil nilai dan fungsi dan mengembalikan aliran aplikasi berturut-turut fungsi ke nilai:
Fungsi pembangunnya adalah sebagai berikut:
Maka
iterate
merupakan anamorphism untukiterateBuilder
.Kesimpulan
Jadi, singkatnya, F-aljabar memungkinkan untuk menentukan lipatan, yaitu operasi yang mengurangi struktur rekursif menjadi nilai tunggal, dan F-coalgebra memungkinkan untuk melakukan yang sebaliknya: membangun struktur [berpotensi] tak terbatas dari nilai tunggal.
Faktanya dalam Haskell F-algebras dan F-coalgebras bertepatan. Ini adalah properti yang sangat bagus yang merupakan konsekuensi dari keberadaan nilai 'bawah' di setiap jenis. Jadi di Haskell lipatan dan lipatan dapat dibuat untuk setiap jenis rekursif. Namun, model teoritis di balik ini lebih kompleks daripada yang saya sebutkan di atas, jadi saya sengaja menghindarinya.
Semoga ini membantu.
sumber
appendReductor
terlihat agak aneh dan tidak benar-benar membantu saya melihat polanya di sana ... :) Bisakah Anda mengecek apakah itu benar? .. Seperti apa jenis reduktor pada umumnya? Dalam definisir
sana,F1
ditentukan oleh IntList, atau apakah itu F sewenang-wenang?Menelusuri makalah tutorial Sebuah tutorial tentang (co) aljabar dan (co) induksi harus memberi Anda beberapa wawasan tentang co-aljabar dalam ilmu komputer.
Di bawah ini adalah kutipan untuk meyakinkan Anda,
Pendahuluan, tentang teori Kategori. Kategori teori harus berganti nama menjadi teori functors. Karena kategori adalah apa yang harus didefinisikan seseorang untuk mendefinisikan functors. (Selain itu, functors adalah apa yang harus didefinisikan untuk mendefinisikan transformasi alami.)
Apa itu functor? Ini adalah transformasi dari satu set ke set lainnya yang menjaga struktur mereka. (Untuk lebih jelasnya ada banyak deskripsi yang bagus di internet).
Apa itu aljabar F? Ini adalah aljabar functor. Ini hanya studi tentang kepatutan universal functor.
Bagaimana itu bisa terhubung ke ilmu komputer? Program dapat dilihat sebagai kumpulan informasi terstruktur. Eksekusi program berhubungan dengan modifikasi set informasi terstruktur ini. Kedengarannya bagus bahwa eksekusi harus mempertahankan struktur program. Kemudian eksekusi dapat dilihat sebagai aplikasi functor atas set informasi ini. (Yang mendefinisikan program).
Mengapa F-co-aljabar? Program bersifat ganda karena pada dasarnya dijelaskan oleh informasi dan mereka bertindak berdasarkan itu. Maka terutama informasi yang menyusun program dan mengubahnya dapat dilihat dengan dua cara.
Kemudian pada tahap ini, saya ingin mengatakan itu,
Selama kehidupan suatu program, data dan negara berdampingan, dan mereka saling melengkapi. Mereka ganda.
sumber
Saya akan mulai dengan hal-hal yang jelas terkait dengan pemrograman dan kemudian menambahkan beberapa hal matematika, agar tetap konkrit dan serendah mungkin.
Mari mengutip beberapa ilmuwan komputer tentang koinduksi ...
http://www.cs.umd.edu/~micinski/posts/2012-09-04-on-understanding-coinduction.html
http://adam.chlipala.net/cpdt/html/Coinductive.html
http://www.alexandrasilva.org/#/talks.html
Menghubungkan konteks matematika ambient dengan tugas pemrograman biasa
Apa itu "aljabar"?
Struktur aljabar umumnya terlihat seperti:
Ini seharusnya terdengar seperti objek dengan 1. properti dan 2. metode. Atau bahkan lebih baik, seharusnya terdengar seperti tanda tangan tipe.
Contoh matematika standar termasuk monoid ⊃ grup ⊃ vektor-ruang ⊃ "aljabar". Monoids seperti automata: urutan kata kerja (misalnya,
f.g.h.h.nothing.f.g.f
). Sebuahgit
log yang selalu menambahkan sejarah dan tidak pernah menghapus itu akan menjadi monoid tapi bukan kelompok. Jika Anda menambahkan invers (mis. Angka negatif, pecahan, akar, menghapus histori yang terakumulasi, menghapus pecahan cermin yang rusak) Anda mendapatkan grup.Grup berisi hal-hal yang dapat ditambahkan atau dikurangkan bersama. Misalnya
Duration
s dapat ditambahkan bersamaan. (TapiDate
s tidak bisa.) Durasi hidup dalam ruang vektor (bukan hanya grup) karena mereka juga dapat diskalakan dengan angka luar. (Jenis tanda tangan dariscaling :: (Number,Duration) → Duration
.)Algebras ⊂ ruang vektor dapat melakukan hal lain: ada beberapa
m :: (T,T) → T
. Sebut ini "perkalian" atau tidak, karena begitu Anda meninggalkannyaIntegers
, menjadi tidak jelas apa "perkalian" (atau "eksponensial" ) seharusnya.(Inilah sebabnya mengapa orang mencari sifat universal (kategori-teoretis): untuk memberi tahu mereka apa yang harus dilakukan atau menjadi seperti :
)
Algebras → Coalgebras
Komultiplikasi lebih mudah untuk didefinisikan dengan cara yang terasa non-arbitrer, daripada multiplikasi, karena untuk pergi dari
T → (T,T)
Anda hanya dapat mengulangi elemen yang sama. ("peta diagonal" - seperti matriks / operator diagonal dalam teori spektral)Counit biasanya merupakan jejak (jumlah entri diagonal), meskipun lagi yang penting adalah apa yang dilakukan oleh counit Anda ;
trace
hanyalah jawaban yang bagus untuk matriks.Alasan untuk melihat ruang ganda , secara umum, adalah karena lebih mudah untuk berpikir di ruang itu. Misalnya kadang-kadang lebih mudah untuk memikirkan vektor normal daripada tentang pesawat normal, tetapi Anda dapat mengontrol pesawat (termasuk hyperplanes) dengan vektor (dan sekarang saya berbicara tentang vektor geometris yang sudah dikenal, seperti di tracer-ray) .
Menjinakkan (tidak) data terstruktur
Matematikawan mungkin memodelkan sesuatu yang menyenangkan seperti TQFT , sedangkan programmer harus bergulat dengannya
+ :: (Date,Duration) → Date
),Paris
≠(+48.8567,+2.3508)
! Ini bentuk, bukan titik.),Ilmuwan komputer, ketika berbicara tentang batu bara batubara, biasanya memiliki operasi tertentu, seperti produk Cartesian. Saya percaya inilah yang dimaksud orang ketika mereka berkata seperti "Algebras adalah coalgebras di Haskell". Tetapi sejauh para programmer harus memodelkan tipe data yang kompleks seperti
Place
,,Date/Time
danCustomer
— dan membuat model-model itu tampak sama seperti dunia nyata (atau setidaknya pandangan pengguna akhir tentang dunia nyata) sebanyak mungkin — saya percaya ada dua, bisa bermanfaat di luar hanya dunia set.sumber