Menyalahgunakan aljabar tipe data aljabar - mengapa ini bekerja?

Ekspresi 'aljabar' untuk tipe data aljabar terlihat sangat sugestif bagi seseorang dengan latar belakang dalam matematika. Biarkan saya mencoba menjelaskan apa yang saya maksud.

Setelah mendefinisikan tipe dasar

• Produk •
• Persatuan +
• Singleton X
• Satuan 1

dan menggunakan singkatan X²untuk X•Xdan 2Xuntuk X+Xsebagainya, kita kemudian dapat mendefinisikan ekspresi aljabar untuk eg daftar terkait

data List a = Nil | Cons a (List a) ↔ L = 1 + X • L

dan pohon biner:

data Tree a = Nil | Branch a (Tree a) (Tree a) ↔ T = 1 + X • T²

Sekarang, insting pertama saya sebagai ahli matematika adalah menjadi gila dengan ungkapan-ungkapan ini, dan mencoba untuk memecahkan untuk Ldan T. Saya bisa melakukan ini melalui penggantian berulang kali, tetapi tampaknya lebih mudah untuk menyalahgunakan notasi itu secara mengerikan dan berpura-pura saya dapat mengaturnya kembali sesuka hati. Misalnya, untuk daftar tertaut:

L = 1 + X • L

(1 - X) • L = 1

L = 1 / (1 - X) = 1 + X + X² + X³ + ...

di mana saya telah menggunakan ekspansi rangkaian daya 1 / (1 - X)dengan cara yang sama sekali tidak dapat dibenarkan untuk memperoleh hasil yang menarik, yaitu bahwa suatu Ltipe adalah baik Nil, atau mengandung 1 elemen, atau mengandung 2 elemen, atau 3, dll.

Semakin menarik jika kita melakukannya untuk pohon biner:

T = 1 + X • T²

X • T² - T + 1 = 0

T = (1 - √(1 - 4 • X)) / (2 • X)

T = 1 + X + 2 • X² + 5 • X³ + 14 • X⁴ + ...

lagi, menggunakan ekspansi seri daya (dilakukan dengan Wolfram Alpha ). Ini mengungkapkan fakta yang tidak jelas (bagi saya) bahwa hanya ada satu pohon biner dengan 1 elemen, 2 pohon biner dengan dua elemen (elemen kedua bisa di cabang kiri atau kanan), 5 pohon biner dengan tiga elemen dll .

Jadi pertanyaan saya adalah - apa yang saya lakukan di sini? Operasi ini tampaknya tidak dapat dibenarkan (apa sebenarnya akar kuadrat dari tipe data aljabar?) Tetapi mereka mengarah pada hasil yang masuk akal. apakah hasil bagi dari dua tipe data aljabar memiliki arti dalam ilmu komputer, atau hanya tipuan notasi?

Dan, mungkin yang lebih menarik, apakah mungkin untuk memperluas ide-ide ini? Apakah ada teori aljabar jenis yang memungkinkan, misalnya, fungsi acak pada jenis, atau apakah jenis memerlukan representasi rangkaian daya? Jika Anda dapat menentukan kelas fungsi, lalu apakah komposisi fungsi memiliki makna?

Penafian: Banyak dari ini tidak benar-benar berfungsi dengan benar ketika Anda menghitung ⊥, jadi saya akan dengan terang-terangan mengabaikannya demi kesederhanaan.

Beberapa poin awal:

• Perhatikan bahwa "penyatuan" mungkin bukan istilah terbaik untuk A + B di sini - itu secara khusus merupakan penyatuan yang terpisah dari kedua jenis, karena kedua belah pihak dibedakan walaupun jenisnya sama. Untuk apa nilainya, istilah yang lebih umum hanyalah "tipe jumlah".

• Jenis singleton adalah, secara efektif, semua tipe unit. Mereka berperilaku identik di bawah manipulasi aljabar dan, yang lebih penting, jumlah informasi yang ada masih dipertahankan.

• Anda mungkin menginginkan tipe nol juga. Haskell menyatakan itu sebagai Void. Tidak ada nilai yang tipenya nol, sama seperti ada satu nilai yang tipenya satu.

Masih ada satu operasi besar yang hilang di sini, tetapi saya akan segera kembali ke sana.

Seperti yang mungkin Anda perhatikan, Haskell cenderung meminjam konsep dari Kategori Teori, dan semua hal di atas memiliki interpretasi yang sangat mudah:

• Diberikan objek A dan B dalam Hask , produk mereka A × B adalah tipe unik (hingga isomorfisme) yang memungkinkan dua proyeksi pertama : A × B → A dan snd : A × B → B, di mana diberikan semua tipe C dan fungsi f : C → A, g : C → B Anda dapat menentukan pasangan f &&& g : C → A × B sedemikian rupa sehingga pertama ∘ (f &&& g) = f dan juga untuk g . Parametrisitas menjamin sifat universal secara otomatis dan pilihan nama saya yang kurang halus akan memberi Anda ide. The (&&&)Operator didefinisikan dalam Control.Arrow, dengan cara.

• Dua hal di atas adalah coproduct A + B dengan injeksi inl : A → A + B dan inr : B → A + B, di mana diberikan semua jenis C dan fungsi f : A → C, g : B → C, Anda dapat mendefinisikan copairing f ||| g : A + B → C sedemikian rupa sehingga persamaan yang jelas berlaku. Sekali lagi, parametrik menjamin sebagian besar bagian yang rumit secara otomatis. Dalam hal ini, suntikan standar hanya Leftdan Rightdan copairing adalah fungsi either.

Banyak properti dari jenis produk dan jumlah dapat diturunkan dari di atas. Perhatikan bahwa semua tipe singleton adalah objek terminal Hask dan semua tipe kosong adalah objek awal.

Kembali ke operasi yang hilang tersebut, dalam kategori tertutup kartesian Anda memiliki objek eksponensial yang sesuai dengan panah dari kategori. Panah kami adalah fungsi, benda kami jenis dengan jenis *, dan jenis A -> Bmemang berperilaku sebagai B ^A dalam konteks aljabar manipulasi jenis. Jika tidak jelas mengapa ini berlaku, pertimbangkan jenisnya Bool -> A. Dengan hanya dua input yang mungkin, fungsi tipe itu isomorfik untuk dua nilai tipe A, yaitu (A, A). Karena Maybe Bool -> Akami memiliki tiga kemungkinan input, dan sebagainya. Juga, perhatikan bahwa jika kita ulangi definisi copairing di atas untuk menggunakan notasi aljabar, kita mendapatkan identitas C ^A × C ^B = C^{A + B}.

Adapun mengapa ini semua masuk akal - dan khususnya mengapa penggunaan ekspansi seri daya Anda dibenarkan - perhatikan bahwa sebagian besar di atas mengacu pada "penghuni" dari suatu jenis (yaitu, nilai yang berbeda memiliki jenis itu) secara berurutan untuk menunjukkan perilaku aljabar. Untuk membuat perspektif itu eksplisit:

• Jenis produk (A, B)mewakili nilai masing-masing dari Adan B, diambil secara independen. Jadi untuk nilai tetap apa pun a :: A, ada satu nilai tipe (A, B)untuk setiap penghuni B. Ini tentu saja merupakan produk kartesius, dan jumlah penghuni dari jenis produk adalah produk dari jumlah penghuni faktor-faktor tersebut.

• Jenis penjumlahan Either A Bmewakili nilai dari salah satu Aatau B, dengan cabang kiri dan kanan dibedakan. Seperti disebutkan sebelumnya, ini adalah persatuan yang terpisah, dan jumlah penghuni dari jumlah penjumlahan adalah jumlah dari jumlah penghuni dari puncak.

• Tipe eksponensial B -> Amewakili pemetaan dari nilai tipe Bke nilai tipe A. Untuk argumen tetap apa pun b :: B, nilai apa pun Adapat ditetapkan untuknya; nilai tipe B -> Amengambil satu pemetaan tersebut untuk setiap masukan, yang setara dengan produk dari sebanyak salinan Asebagai Bmemiliki penduduk, maka eksponensial tersebut.

Meskipun pada mulanya tergoda untuk memperlakukan tipe sebagai set, itu tidak benar-benar berfungsi dengan baik dalam konteks ini - kita memiliki penyatuan terputus-putus dan bukan penyatuan standar set, tidak ada interpretasi yang jelas tentang persimpangan atau banyak operasi set lainnya, dan kami biasanya tidak peduli tentang mengatur keanggotaan (menyerahkannya ke pemeriksa tipe).

Di sisi lain, konstruksi di atas menghabiskan banyak waktu berbicara tentang menghitung penduduk, dan menghitung nilai yang mungkin dari suatu tipe adalah konsep yang berguna di sini. Itu dengan cepat membawa kita ke kombinatorik enumeratif , dan jika Anda membaca artikel Wikipedia yang terhubung, Anda akan menemukan bahwa salah satu hal pertama yang dilakukannya adalah mendefinisikan "pasangan" dan "serikat" dalam arti yang sama persis dengan jenis produk dan jumlah dengan cara menghasilkan fungsi , lalu melakukan hal yang sama untuk "urutan" yang identik dengan daftar Haskell menggunakan teknik yang persis sama dengan yang Anda lakukan.

Sunting: Oh, dan inilah bonus cepat yang menurut saya menunjukkan intinya. Anda menyebutkan dalam komentar bahwa untuk jenis pohon T = 1 + T^2Anda dapat memperoleh identitas T^6 = 1, yang jelas salah. Namun demikian, T^7 = T memang berlaku, dan suatu penambangan antara pohon dan tujuh tupel pohon dapat dibangun secara langsung, lih. "Tujuh Pohon dalam Satu" karya Andreas Blass .

Sunting × 2: Mengenai masalah konstruksi "turunan dari jenis" yang disebutkan dalam jawaban lain, Anda juga dapat menikmati makalah ini dari penulis yang sama yang membangun gagasan lebih jauh, termasuk gagasan tentang pembagian dan hal menarik lainnya.

Pohon biner didefinisikan oleh persamaan T=1+XT^2dalam semiring tipe. Dengan konstruksi, T=(1-sqrt(1-4X))/(2X)didefinisikan oleh persamaan yang sama dalam semiring bilangan kompleks. Jadi mengingat bahwa kita sedang menyelesaikan persamaan yang sama di kelas struktur aljabar yang sama, seharusnya tidak mengejutkan bahwa kita melihat beberapa kesamaan.

Tangkapannya adalah ketika kita berargumen tentang polinomial dalam semiring bilangan kompleks, kita biasanya menggunakan fakta bahwa bilangan kompleks membentuk cincin atau bahkan bidang sehingga kita menemukan diri kita menggunakan operasi seperti pengurangan yang tidak berlaku untuk semiring. Tetapi kita sering dapat menghilangkan pengurangan dari argumen kita jika kita memiliki aturan yang memungkinkan kita untuk membatalkan dari kedua sisi persamaan. Ini adalah jenis hal yang dibuktikan oleh Fiore dan Leinster yang menunjukkan bahwa banyak argumen tentang cincin dapat ditransfer ke semiring.

Ini berarti bahwa banyak pengetahuan matematika Anda tentang cincin dapat ditransfer dengan andal ke berbagai jenis. Akibatnya, beberapa argumen yang melibatkan bilangan kompleks atau rangkaian daya (di ring seri daya formal) dapat terbawa ke tipe dengan cara yang sangat ketat.

Namun ada lebih banyak cerita dari ini. Itu satu hal untuk membuktikan dua jenis sama (katakanlah) dengan menunjukkan dua seri kekuatan sama. Tetapi Anda juga dapat menyimpulkan informasi tentang jenis-jenis dengan memeriksa persyaratan dalam seri daya. Saya tidak yakin apa pernyataan formal di sini seharusnya. (Saya sarankan Brent Yorgey ini kertas pada spesies kombinasi untuk beberapa pekerjaan yang erat terkait tetapi spesies yang tidak sama dengan jenis.)

Apa yang saya temukan benar-benar mengejutkan adalah bahwa apa yang Anda temukan dapat diperluas ke kalkulus. Teorema tentang kalkulus dapat ditransfer ke semiring tipe. Bahkan, bahkan argumen tentang perbedaan hingga dapat ditransfer dan Anda menemukan bahwa teorema klasik dari analisis numerik memiliki interpretasi dalam teori tipe.

Selamat bersenang-senang!

Tampaknya semua yang Anda lakukan adalah memperluas hubungan perulangan.

L = 1 + X • L
L = 1 + X • (1 + X • (1 + X • (1 + X • ...)))
  = 1 + X + X^2 + X^3 + X^4 ...

T = 1 + X • T^2
L = 1 + X • (1 + X • (1 + X • (1 + X • ...^2)^2)^2)^2
  = 1 + X + 2 • X^2 + 5 • X^3 + 14 • X^4 + ...

Dan karena aturan untuk operasi pada tipe berfungsi seperti aturan untuk operasi aritmatika, Anda dapat menggunakan cara aljabar untuk membantu Anda mengetahui bagaimana memperluas hubungan perulangan (karena tidak jelas).

Saya tidak punya jawaban yang lengkap, tetapi manipulasi ini cenderung 'hanya berfungsi'. Sebuah makalah yang relevan mungkin Objek dari Kategori sebagai Bilangan Kompleks oleh Fiore dan Leinster - Saya menemukan yang sementara membaca blog sigfpe tentang topik terkait ; sisa dari blog itu adalah tambang emas untuk ide-ide serupa dan layak untuk dicoba!

Anda juga dapat membedakan tipe data, yang akan memberi Anda ritsleting yang sesuai untuk tipe data!

Aljabar Proses Berkomunikasi (ACP) berurusan dengan jenis ekspresi yang sama untuk proses. Ia menawarkan penambahan dan penggandaan sebagai operator untuk pilihan dan urutan, dengan elemen netral yang terkait. Berdasarkan ini ada operator untuk konstruksi lain, seperti paralelisme dan gangguan. Lihat http://en.wikipedia.org/wiki/Algebra_of_Communicating_Processes . Ada juga sebuah makalah online bernama "Sejarah Singkat Aljabar Proses".

Saya sedang berupaya memperluas bahasa pemrograman dengan ACP. April lalu saya mempresentasikan makalah penelitian di Scala Days 2012, tersedia di http://code.google.com/p/subscript/

Pada konferensi tersebut saya mendemonstrasikan debugger yang menjalankan spesifikasi tas rekursif paralel:

Tas = A; (Tas & a)

di mana A dan berdiri untuk tindakan input dan output; titik koma dan ampersand berarti urutan dan paralelisme. Lihat video di SkillsMatter, dapat dijangkau dari tautan sebelumnya.

Spesifikasi tas lebih sebanding dengan

L = 1 + X • L

akan menjadi

B = 1 + X&B

ACP mendefinisikan paralelisme dalam hal pilihan dan urutan menggunakan aksioma; lihat artikel Wikipedia. Saya ingin tahu untuk apa analogi tas itu

L = 1 / (1-X)

Pemrograman gaya ACP berguna untuk parser teks dan pengontrol GUI. Spesifikasi seperti

searchCommand = diklik (searchButton) + kunci (Enter)

cancelCommand = diklik (cancelButton) + kunci (Escape)

dapat ditulis lebih ringkas dengan membuat dua penyempurnaan "diklik" dan "kunci" tersirat (seperti yang dimungkinkan oleh Scala dengan fungsi). Maka kita dapat menulis:

searchCommand = searchButton + Enter

cancelCommand = cancelButton + Escape

Sisi kanan sekarang berisi operan yang merupakan data, bukan proses. Pada tingkat ini tidak perlu untuk mengetahui penyempurnaan implisit apa yang akan mengubah operan ini menjadi proses; mereka tidak perlu disaring menjadi tindakan input; tindakan keluaran juga akan berlaku, misalnya dalam spesifikasi robot uji.

Proses mendapatkan data cara ini sebagai teman; jadi saya koin istilah "item aljabar".

Seri kalkulus dan Maclaurin dengan tipe

Berikut ini adalah tambahan kecil lainnya - wawasan kombinatorial mengapa koefisien dalam ekspansi seri harus 'bekerja', khususnya berfokus pada seri yang dapat diturunkan menggunakan pendekatan Taylor-Maclaurin dari kalkulus. NB: ekspansi seri contoh yang Anda berikan dari tipe daftar yang dimanipulasi adalah seri Maclaurin.

Karena jawaban dan komentar lain berhubungan dengan perilaku ekspresi tipe aljabar (jumlah, produk, dan eksponen), jawaban ini akan menghilangkan detail dan fokus pada tipe 'kalkulus'.

Anda mungkin melihat koma terbalik melakukan angkat berat dalam jawaban ini. Ada dua alasan:

• kami dalam bisnis memberikan interpretasi dari satu domain ke entitas dari yang lain dan tampaknya tepat untuk membatasi pengertian asing seperti itu dengan cara ini.
• beberapa gagasan akan dapat diformalkan dengan lebih ketat, tetapi bentuk dan ide-ide tampak lebih penting (dan mengambil lebih sedikit ruang untuk menulis) daripada rinciannya.

Definisi seri Maclaurin

The Seri Maclaurin dari fungsi f : ℝ → ℝdidefinisikan sebagai

f(0) + f'(0)X + (1/2)f''(0)X² + ... + (1/n!)f⁽ⁿ⁾(0)Xⁿ + ...

dimana f⁽ⁿ⁾artinya nturunan th dari f.

Agar dapat memahami seri Maclaurin sebagaimana ditafsirkan dengan tipe, kita perlu memahami bagaimana kita dapat menafsirkan tiga hal dalam konteks tipe:

• turunan (mungkin berganda)
• menerapkan fungsi ke 0
• istilah seperti (1/n!)

dan ternyata konsep-konsep dari analisis ini memiliki mitra yang cocok di dunia tipe.

Apa yang saya maksud dengan 'mitra yang cocok'? Itu harus memiliki aroma isomorfisme - jika kita bisa menjaga kebenaran di kedua arah, fakta yang diturunkan dalam satu konteks dapat ditransfer ke yang lain.

Kalkulus dengan tipe

Jadi apa arti turunan dari ekspresi tipe? Ternyata untuk kelas ekspresi dan fungsi tipe besar dan berperilaku baik ('terdiferensiasi'), ada operasi alami yang berperilaku serupa untuk menjadi interpretasi yang cocok!

Untuk merusak lucunya, operasi analog dengan diferensiasi adalah membuat 'konteks satu lubang'. Ini adalah tempat yang sangat baik untuk memperluas pada titik khusus ini lebih jauh tetapi konsep dasar dari konteks satu-lubang ( da/dx) adalah bahwa ia mewakili hasil mengekstraksi subitem tunggal dari tipe tertentu ( x) dari istilah (tipe a), mempertahankan semua informasi lain, termasuk yang diperlukan untuk menentukan lokasi asli subitem. Misalnya, satu cara untuk mewakili konteks satu lubang untuk daftar adalah dengan dua daftar: satu untuk item yang datang sebelum yang diekstraksi, dan satu untuk item yang datang setelahnya.

Motivasi untuk mengidentifikasi operasi ini dengan diferensiasi berasal dari pengamatan berikut. Kami menulis da/dxdengan maksud tipe konteks satu lubang untuk tipe adengan lubang tipe x.

d1/dx = 0
dx/dx = 1
d(a + b)/dx = da/dx + db/dx
d(a × b)/dx = a × db/dx + b × da/dx
d(g(f(x))/dx = d(g(y))/dy[f(x)/a] × df(x)/dx

Di sini, 1dan 0mewakili jenis dengan tepat satu dan tepat nol penghuni, masing-masing, dan +dan ×mewakili jumlah dan jenis produk seperti biasa. fdan gdigunakan untuk merepresentasikan fungsi tipe, atau tipe ekspresi ekspresi, dan [f(x)/a]berarti operasi penggantian f(x)untuk setiap aekspresi sebelumnya.

Ini dapat ditulis dalam gaya point-free, menulis f'berarti fungsi turunan dari fungsi tipe f, dengan demikian:

(x ↦ 1)' = x ↦ 0
(x ↦ x)' = x ↦ 1
(f + g)' = f' + g'
(f × g)' = f × g' + g × f'
(g ∘ f)' = (g' ∘ f) × f'

yang mungkin lebih disukai.

NB, persamaan dapat dibuat dengan tepat dan tepat jika kita mendefinisikan turunan menggunakan kelas isomorfisme tipe dan fungsi.

Sekarang, kami perhatikan secara khusus bahwa aturan dalam kalkulus yang berkaitan dengan operasi aljabar penambahan, perkalian dan komposisi (sering disebut aturan Sum, Produk dan Rantai) dicerminkan dengan tepat oleh operasi 'membuat lubang'. Selanjutnya, kasus dasar 'membuat lubang' dalam ekspresi atau istilah yang konstanx itu sendiri juga berperilaku sebagai diferensiasi, jadi dengan induksi kita mendapatkan perilaku seperti diferensiasi untuk semua ekspresi tipe aljabar.

Sekarang kita dapat menafsirkan diferensiasi, apa arti nturunan dari ekspresi tipe dⁿe/dxⁿ? Ini adalah jenis yang mewakili nkonteks -place: istilah yang, ketika 'diisi' dengan nhal jenis xmenghasilkan sebuah e. Ada pengamatan kunci lain terkait dengan ' (1/n!)' datang nanti.

Bagian invarian dari functor tipe: menerapkan fungsi ke 0

Kami sudah memiliki interpretasi untuk 0di dunia tipe: tipe kosong tanpa anggota. Apa artinya, dari sudut pandang kombinatorial, untuk menerapkan fungsi tipe padanya? Dalam istilah yang lebih konkret, seandainya ffungsi tipe, seperti apa f(0)? Yah, kami tentu saja tidak memiliki akses ke jenis apa pun 0, sehingga konstruksi f(x)yang membutuhkan xtidak tersedia. Yang tersisa adalah istilah-istilah yang dapat diakses tanpa kehadiran mereka, yang dapat kita sebut sebagai bagian 'invarian' atau 'konstan'.

Untuk contoh eksplisit, ambil Maybefunctor, yang dapat direpresentasikan secara aljabar sebagai x ↦ 1 + x. Ketika kita menerapkan ini 0, kita mendapatkan 1 + 0- itu seperti 1: satu-satunya nilai yang mungkin adalah Nonenilainya. Untuk daftar, sama halnya, kita mendapatkan istilah yang sesuai dengan daftar kosong.

Ketika kita mengembalikannya dan menginterpretasikan tipe f(0)sebagai angka, dapat dianggap sebagai hitungan berapa banyak istilah tipe f(x)(untuk setiap x) dapat diperoleh tanpa akses ke x: yaitu, jumlah istilah 'seperti kosong' .

Menyatukannya: penafsiran lengkap dari seri Maclaurin

Saya khawatir saya tidak bisa memikirkan interpretasi langsung yang tepat (1/n!)sebagai tipe.

Namun, jika kita mempertimbangkan jenis f⁽ⁿ⁾(0)yang dijelaskan di atas, kita melihat bahwa itu dapat diartikan sebagai jenis nkonteks-tempat untuk istilah jenis f(x)yang belum mengandung x - yaitu, ketika kita 'mengintegrasikan' mereka nkali , istilah yang dihasilkan memiliki tepat n x , tidak lebih, tidak kurang. Maka penafsiran tipe f⁽ⁿ⁾(0)sebagai angka (seperti dalam koefisien dari seri Maclaurin f) hanyalah hitungan dari berapa banyak nkonteks tempat kosong yang ada. Kita hampir sampai!

Tapi di mana (1/n!)akhirnya? Meneliti proses tipe 'diferensiasi' menunjukkan kepada kita bahwa, ketika diterapkan beberapa kali, ia mempertahankan 'urutan' di mana subterms diekstraksi. Sebagai contoh, perhatikan istilah (x₀, x₁)tipe x × xdan operasi 'membuat lubang' di dalamnya dua kali. Kami mendapatkan kedua urutan

(x₀, x₁)  ↝  (_₀, x₁)  ↝  (_₀, _₁)
(x₀, x₁)  ↝  (x₀, _₀)  ↝  (_₁, _₀)
(where _ represents a 'hole')

meskipun keduanya berasal dari istilah yang sama, karena ada 2! = 2cara untuk mengambil dua elemen dari dua, menjaga ketertiban. Secara umum, adan! cara untuk mengambil nelemen n. Jadi untuk mendapatkan hitungan jumlah konfigurasi tipe functor yang memiliki nelemen, kita harus menghitung tipe f⁽ⁿ⁾(0)dan membaginya dengan n!, persis seperti dalam koefisien dari seri Maclaurin.

Jadi membagi itu n!ternyata bisa ditafsirkan hanya sebagai dirinya sendiri.

Pikiran terakhir: definisi dan analisis 'rekursif'

Pertama, beberapa pengamatan:

• jika suatu fungsi f: ℝ → ℝ memiliki turunan, turunan ini unik
• sama halnya, jika fungsi f: ℝ → ℝ bersifat analitik, ia memiliki tepat satu seri polinomial yang sesuai

Karena kita memiliki aturan rantai, kita dapat menggunakan diferensiasi implisit , jika kita memformalkan turunan tipe sebagai kelas isomorfisme. Tapi diferensiasi implisit tidak memerlukan manuver alien seperti pengurangan atau pembagian! Jadi kita bisa menggunakannya untuk menganalisis definisi tipe rekursif. Untuk mengambil contoh daftar Anda, kami punya

L(X) ≅ 1 + X × L(X)
L'(X) = X × L'(X) + L(X)

dan kemudian kita bisa mengevaluasi

L'(0) = L(0) = 1

untuk mendapatkan koefisien X¹dalam seri Maclaurin.

Tetapi karena kami yakin bahwa ungkapan ini memang benar-benar 'dapat dibedakan', jika hanya secara implisit, dan karena kami memiliki korespondensi dengan fungsi ℝ → ℝ, di mana turunannya tentu unik, kami dapat yakin bahwa bahkan jika kami memperoleh nilai menggunakan ' operasi ilegal, hasilnya valid.

Sekarang, sama halnya, untuk menggunakan pengamatan kedua, karena korespondensi (apakah itu homomorfisme?) Dengan fungsi ℝ → ℝ, kita tahu bahwa, asalkan kita puas bahwa suatu fungsi memiliki seri Maclaurin, jika kita dapat menemukan seri di semua , prinsip-prinsip yang diuraikan di atas dapat diterapkan untuk membuatnya keras.

Adapun pertanyaan Anda tentang komposisi fungsi, saya kira aturan rantai memberikan jawaban parsial.

Saya tidak yakin berapa banyak ADT gaya Haskell ini berlaku untuk, tetapi saya menduga itu banyak jika tidak semua. Saya telah menemukan bukti yang luar biasa dari fakta ini, tetapi margin ini terlalu kecil untuk menampungnya ...

Sekarang, tentu ini hanya satu cara untuk mengetahui apa yang terjadi di sini dan mungkin ada banyak cara lain.

Ringkasan: TL; DR

• ketik 'diferensiasi' sesuai dengan ' membuat lubang '.
• menerapkan functor untuk 0memberi kita istilah 'seperti kosong' untuk functor itu.
• Oleh karena itu, rangkaian daya Maclaurin (agak) sangat sesuai dengan penghitungan jumlah anggota tipe functor dengan sejumlah elemen tertentu.
• diferensiasi implisit membuat ini lebih kedap air.
• keunikan turunan dan keunikan seri daya berarti kita dapat memperdaya detail dan kerjanya.

Teori tipe dependen dan fungsi tipe 'arbitrer'

Jawaban pertama saya untuk pertanyaan ini adalah tinggi pada konsep dan rendah pada rincian dan tercermin pada pertanyaan, 'apa yang terjadi?'; jawaban ini akan sama tetapi terfokus pada subquestion, 'bisakah kita mendapatkan fungsi tipe sewenang-wenang?'.

Salah satu ekstensi untuk operasi aljabar jumlah dan produk adalah apa yang disebut 'operator besar', yang mewakili jumlah dan produk dari suatu urutan (atau lebih umum, jumlah dan produk dari suatu fungsi melalui suatu domain) biasanya ditulis Σdan Πmasing - masing. Lihat Notasi Sigma .

Jadi jumlahnya

a₀ + a₁X + a₂X² + ...

mungkin ditulis

Σ[i ∈ ℕ]aᵢXⁱ

di mana aada beberapa urutan bilangan real, misalnya. Produk akan diwakili serupa dengan Πbukan Σ.

Ketika Anda melihat dari jauh, ungkapan semacam ini sangat mirip dengan fungsi 'arbitrer' X; kami terbatas tentu saja untuk seri ekspresif, dan fungsi analitik yang terkait. Apakah ini kandidat untuk representasi dalam teori tipe? Pastinya!

Kelas teori tipe yang memiliki representasi langsung dari ekspresi ini adalah kelas teori tipe 'dependen': teori dengan tipe dependen. Secara alami kami memiliki istilah yang tergantung pada istilah, dan dalam bahasa seperti Haskell dengan fungsi tipe dan tipe kuantifikasi, istilah dan tipe tergantung pada tipe. Dalam pengaturan dependen, kami juga memiliki jenis tergantung pada istilah. Haskell bukanlah bahasa yang diketik secara dependen, meskipun banyak fitur tipe dependen dapat disimulasikan dengan sedikit menyiksa bahasa .

Kari-Howard dan tipe tergantung

'Curry-Howard isomorphism' memulai kehidupan sebagai pengamatan bahwa istilah dan aturan penilaian tipe kalkulus lambda yang diketikkan sesuai dengan deduksi alami (seperti yang diformulasikan oleh Gentzen) diterapkan pada logika proposisional intuitionistic, dengan tipe yang menggantikan proposisi. , dan persyaratan menggantikan bukti, meskipun keduanya secara independen ditemukan / ditemukan. Sejak itu, ia telah menjadi sumber inspirasi bagi para ahli teori tipe. Salah satu hal yang paling jelas untuk dipertimbangkan adalah apakah, dan bagaimana, korespondensi ini untuk logika proposisional dapat diperluas ke predikat atau logika tingkat tinggi. Teori tipe dependen awalnya muncul dari jalan eksplorasi ini.

Untuk pengantar isomorfisma Curry-Howard untuk kalkulus lambda yang diketik sederhana, lihat di sini . Sebagai contoh, jika kita ingin membuktikan A ∧ Bkita harus membuktikan Adan membuktikan B; bukti gabungan hanyalah sepasang bukti: satu untuk masing-masing konjungt.

Dalam deduksi alami:

Γ ⊢ A    Γ ⊢ B
Γ ⊢ A ∧ B

dan dalam kalkulus lambda yang diketik sederhana:

Γ ⊢ a : A    Γ ⊢ b : B
Γ ⊢ (a, b) : A × B

Korespondensi serupa ada untuk ∨dan menjumlahkan jenis, →dan jenis fungsi, dan berbagai aturan eliminasi.

Proposisi yang tidak dapat dibuktikan (salah secara intuitif) berhubungan dengan tipe yang tidak berpenghuni.

Dengan analogi tipe sebagai proposisi logis dalam pikiran, kita dapat mulai mempertimbangkan bagaimana memodelkan predikat di dunia tipe. Ada banyak cara di mana ini telah diformalkan (lihat pengantar untuk Teori Tipe Intuitionistik Martin-Löf untuk standar yang banyak digunakan) tetapi pendekatan abstrak biasanya mengamati bahwa suatu predikat seperti proposisi dengan variabel-variabel istilah bebas, atau, sebagai alternatif, suatu fungsi mengambil istilah untuk proposisi. Jika kita membiarkan ekspresi tipe mengandung istilah, maka perawatan dengan gaya kalkulus lambda segera muncul sebagai kemungkinan!

Mengingat hanya bukti konstruktif, apa yang merupakan bukti ∀x ∈ X.P(x)? Kita dapat menganggapnya sebagai fungsi bukti, mengambil istilah ( x) menjadi bukti proposisi yang sesuai ( P(x)). Jadi anggota (bukti) dari jenis (proposisi) ∀x : X.P(x)adalah 'tergantung fungsi', yang untuk setiap xdi Xberi istilah tipe P(x).

Bagaimana dengan ∃x ∈ X.P(x)? Kita perlu setiap anggota X, xbersama dengan bukti P(x). Jadi anggota (bukti) dari jenis (proposisi) ∃x : X.P(x)adalah 'tergantung pasang': istilah dibedakan xdalam X, bersama-sama dengan istilah jenis P(x).

Notasi: Saya akan gunakan

∀x ∈ X...

untuk pernyataan aktual tentang anggota kelas X, dan

∀x : X...

untuk ekspresi tipe yang sesuai dengan kuantifikasi universal atas tipe X. Demikian juga untuk ∃.

Pertimbangan kombinasi: produk dan jumlah

Seperti halnya korespondensi Curry-Howard dengan proposisi, kami memiliki korespondensi kombinatorial dari tipe aljabar dengan angka dan fungsi, yang merupakan poin utama dari pertanyaan ini. Untungnya, ini dapat diperluas ke tipe dependen yang diuraikan di atas!

Saya akan menggunakan notasi modulus

|A|

untuk mewakili 'ukuran' suatu jenis A, untuk membuat eksplisit korespondensi yang dijabarkan dalam pertanyaan, antara jenis dan angka. Perhatikan bahwa ini adalah konsep di luar teori; Saya tidak mengklaim bahwa perlu ada operator semacam itu dalam bahasa tersebut.

Mari kita hitung anggota tipe yang mungkin (dikurangi sepenuhnya, kanonik)

∀x : X.P(x)

yang merupakan jenis fungsi dependen yang mengambil istilah xtipe Xke istilah tipe P(x). Setiap fungsi tersebut harus memiliki output untuk setiap jangka waktu X, dan output ini harus dari tipe tertentu. Untuk setiap xdi X, kemudian, ini memberikan |P(x)|'pilihan' output.

Bagian lucunya adalah

|∀x : X.P(x)| = Π[x : X]|P(x)|

yang tentu saja tidak masuk akal jika Xitu IO (), tetapi berlaku untuk jenis aljabar.

Demikian pula dengan istilah tipe

∃x : X.P(x)

adalah jenis pasangan (x, p)dengan p : P(x), sehingga diberi xdi Xkita dapat membangun sebuah pasangan yang sesuai dengan setiap anggota P(x), memberikan |P(x)|'pilihan'.

Karenanya,

|∃x : X.P(x)| = Σ[x : X]|P(x)|

dengan peringatan yang sama.

Ini membenarkan notasi umum untuk tipe dependen dalam teori menggunakan simbol Πdan Σ, dan memang banyak teori mengaburkan perbedaan antara 'untuk semua' dan 'produk' dan antara 'ada' dan 'jumlah', karena korespondensi yang disebutkan di atas.

Kami semakin dekat!

Vektor: mewakili tupel dependen

Bisakah kita sekarang menyandikan ekspresi numerik seperti

Σ[n ∈ ℕ]Xⁿ

sebagai jenis ekspresi?

Tidak terlalu. Meskipun kita dapat secara informal mempertimbangkan makna ekspresi seperti Xⁿdi Haskell, di mana Xada jenis dan nbilangan alami, ini merupakan penyalahgunaan notasi; ini adalah tipe ekspresi yang mengandung angka: jelas bukan ekspresi yang valid.

Di sisi lain, dengan tipe dependen dalam gambar, tipe yang mengandung angka justru intinya; pada kenyataannya, tupel dependen atau 'vektor' adalah contoh yang sangat sering dikutip tentang bagaimana tipe dependen dapat memberikan keamanan tingkat-tipe pragmatis untuk operasi seperti akses daftar . Vektor hanyalah daftar beserta informasi tingkat-jenis mengenai panjangnya: seperti apa yang kita inginkan untuk ekspresi tipe Xⁿ.

Untuk durasi jawaban ini, biarkan

Vec X n

menjadi jenis nvektor-panjang dari Xnilai -type.

Secara teknis di nsini, bukan bilangan asli yang sebenarnya , representasi dalam sistem bilangan alami. Kita dapat merepresentasikan bilangan asli ( Nat) dalam gaya Peano sebagai nol ( 0) atau penggantinya ( S) dari bilangan alami lain, dan bagi n ∈ ℕsaya menulis ˻n˼berarti istilah Natyang diwakilinya n. Sebagai contoh, ˻3˼adalah S (S (S 0)).

Lalu kita punya

|Vec X ˻n˼| = |X|ⁿ

untuk apa saja n ∈ ℕ.

Jenis Nat: mempromosikan istilah ℕ ke tipe

Sekarang kita bisa menyandikan ekspresi seperti

Σ[n ∈ ℕ]Xⁿ

sebagai tipe. Ungkapan khusus ini akan memunculkan suatu tipe yang tentu saja isomorfis terhadap tipe daftar X, sebagaimana diidentifikasi dalam pertanyaan. (Tidak hanya itu, tetapi dari sudut pandang kategori-teoretis, fungsi tipe - yang merupakan functor - mengambil Xke tipe di atas secara alami isomorfik ke Daftar functor.)

Salah satu bagian terakhir dari teka-teki untuk fungsi 'sewenang-wenang' adalah cara menyandikan, untuk

f : ℕ → ℕ

ekspresi suka

Σ[n ∈ ℕ]f(n)Xⁿ

sehingga kita dapat menerapkan koefisien arbitrer ke seri daya.

Kami sudah memahami korespondensi tipe aljabar dengan angka, memungkinkan kami memetakan dari tipe ke angka dan mengetik fungsi ke fungsi numerik. Kita juga bisa pergi ke arah lain! - mengambil bilangan alami, jelas ada tipe aljabar yang dapat didefinisikan dengan banyak anggota istilah, apakah kita memiliki tipe dependen atau tidak. Kita dapat dengan mudah membuktikan ini di luar teori tipe dengan induksi. Yang kita butuhkan adalah cara untuk memetakan dari bilangan asli ke tipe, di dalam sistem.

Kesadaran yang menyenangkan adalah bahwa, begitu kita memiliki tipe dependen, bukti melalui induksi dan konstruksi oleh rekursi menjadi sangat mirip - memang mereka adalah hal yang sama dalam banyak teori. Karena kita dapat membuktikan dengan induksi bahwa ada jenis yang memenuhi kebutuhan kita, haruskah kita tidak dapat membangunnya?

Ada beberapa cara untuk merepresentasikan tipe pada level term. Di sini saya akan menggunakan notasi Haskellish imajiner *untuk alam semesta tipe, itu sendiri biasanya dianggap sebagai tipe dalam pengaturan dependen. ¹

Demikian juga, ada juga paling tidak banyak cara untuk memberi notasi ' ℕ-memasuki' karena ada teori tipe dependen. Saya akan menggunakan notasi pencocokan pola Haskellish.

Kami membutuhkan pemetaan, αdari Natke *, dengan properti

∀n ∈ ℕ.|α ˻n˼| = n.

Pseudodefinition berikut sudah mencukupi.

data Zero -- empty type
data Successor a = Z | Suc a -- Successor ≅ Maybe

α : Nat -> *
α 0 = Zero
α (S n) = Successor (α n)

Jadi kita melihat bahwa tindakan αmencerminkan perilaku penerus S, menjadikannya semacam homomorfisme. Successoradalah fungsi tipe yang 'menambah satu' ke jumlah anggota tipe; yaitu, |Successor a| = 1 + |a|untuk apa pun adengan ukuran yang ditentukan.

Misalnya α ˻4˼(yang α (S (S (S (S 0))))), adalah

Successor (Successor (Successor (Successor Zero)))

dan ketentuan dari jenis ini adalah

Z
Suc Z
Suc (Suc Z)
Suc (Suc (Suc Z))

memberikan kita tepat empat elemen: |α ˻4˼| = 4.

Demikian juga, untuk apa pun n ∈ ℕ, yang kita miliki

|α ˻n˼| = n

seperti yang dipersyaratkan.

1. Banyak teori mensyaratkan bahwa anggota *hanyalah perwakilan dari jenis, dan operasi disediakan sebagai pemetaan eksplisit dari segi jenis *ke jenis terkait. Teori-teori lain memungkinkan tipe literal itu sendiri untuk menjadi entitas tingkat-tingkat.

Fungsi 'sewenang-wenang'?

Sekarang kita memiliki alat untuk mengekspresikan rangkaian daya sepenuhnya umum sebagai tipe!

Seri

Σ[n ∈ ℕ]f(n)Xⁿ

menjadi tipenya

∃n : Nat.α (˻f˼ n) × (Vec X n)

di mana ˻f˼ : Nat → Natada beberapa representasi yang sesuai dalam bahasa fungsi f. Kita bisa melihat ini sebagai berikut.

|∃n : Nat.α (˻f˼ n) × (Vec X n)|
    = Σ[n : Nat]|α (˻f˼ n) × (Vec X n)|          (property of ∃ types)
    = Σ[n ∈ ℕ]|α (˻f˼ ˻n˼) × (Vec X ˻n˼)|        (switching Nat for ℕ)
    = Σ[n ∈ ℕ]|α ˻f(n)˼ × (Vec X ˻n˼)|           (applying ˻f˼ to ˻n˼)
    = Σ[n ∈ ℕ]|α ˻f(n)˼||Vec X ˻n˼|              (splitting product)
    = Σ[n ∈ ℕ]f(n)|X|ⁿ                           (properties of α and Vec)

Seberapa 'sewenang-wenang' ini? Kami dibatasi tidak hanya untuk koefisien integer dengan metode ini, tetapi untuk bilangan asli. Selain itu, fdapat berupa apa saja, mengingat bahasa Turing Lengkap dengan tipe dependen, kita dapat mewakili fungsi analitik apa pun dengan koefisien bilangan alami.

Saya belum menyelidiki interaksi ini dengan, misalnya, kasus yang disediakan dalam pertanyaan List X ≅ 1/(1 - X)atau apa yang mungkin dirasakan 'tipe' negatif dan non-integer dalam konteks ini.

Semoga jawaban ini bisa mengeksplorasi seberapa jauh kita bisa pergi dengan fungsi tipe sewenang-wenang.