Kisah Setengah Lingkaran

Halo, Habr! Saya membawa kepada Anda terjemahan dari artikel "A tale on Semirings" oleh Luka Jacobowitz.

Pernah bertanya-tanya mengapa jumlah jenis disebut jumlah jenis. Atau mungkin Anda selalu ingin tahu mengapa operator <*> ditulis dengan cara ini? Dan apa hubungannya ini dengan setengah dering? Tertarik silakan meminta potongan!

Artikel ini adalah terjemahan dari posting blog Typelevel oleh Luke Jakobovic. Untuk persepsi terbaiknya, seseorang memerlukan setidaknya pengetahuan yang dangkal dengan bahasa Scala dan ekosistemnya (termasuk perpustakaan kucing) dan pengetahuan tentang konsep dasar aljabar abstrak: semigroup, monoid, dll.

Struktur aljabar

Banyak dari kita tahu tentang monoids dan semi-grup dan bahkan menggunakannya. Struktur ini memiliki properti yang memungkinkan Anda untuk menerapkannya secara langsung untuk mendapatkan tingkat abstraksi yang lebih tinggi (jika Anda tidak mengetahuinya, Anda dapat membaca dokumentasi dari perpustakaan kucing ). Namun, terkadang tipe data memiliki lebih dari satu monoid atau semi grup. Contoh yang jelas adalah berbagai jenis numerik, di mana perkalian dan penambahan membentuk dua monoids lengkap.

Dalam aljabar abstrak, ada kelas struktur yang terpisah dengan dua monoids berinteraksi dengan cara tertentu. Kelas ini setengah berdering. Karena monoids sering digunakan untuk menggambarkan tipe numerik, mereka biasanya dibagi menjadi multiplikatif dan aditif. Seperti dalam kasus angka, hukum semiring menentukan bahwa perkalian adalah distributif dengan penambahan, dan perkalian dari nomor apa pun dengan persatuan dengan penambahan - nol - memberikan nol.

Ada berbagai cara untuk menyajikan ini sebagai kelas tipe dan pustaka yang berbeda melakukannya dengan caranya sendiri, tetapi mari kita lihat bagaimana ini dilakukan dalam proyek aljabar . Basis di dalamnya adalah AdditiveSemigroup dan MultiplicativeSemigroup .

[ Catatan: karena nama "tipe kelas" tidak berakar dalam bahasa Rusia, versi bahasa Inggrisnya akan digunakan nanti - ketik kelas ]

 import simulacrum._ @typeclass trait AdditiveSemigroup[A] { def +(x: A)(y: A): A } @typeclass trait AdditiveMonoid[A] extends AdditiveSemigroup[A] { def zero: A } @typeclass trait MultiplicativeSemigroup[A] { def *(x: A)(y: A): A } @typeclass trait MultiplicativeMonoid[A] extends MultiplicativeSemigroup[A] { def one: A } 

[ Catatan: Penjelasan @typeclass dari proyek simulacrum memungkinkan Anda untuk secara otomatis menghasilkan metode yang digunakan untuk kelas tipe dan tidak mempengaruhi komponen logis dari kode ]

Dalam hal ini, semiring ( Semiring ) adalah monoid aditif ( AdditiveMonoid ), dikombinasikan dengan monoid multiplikatif ( MultiplicativeMonoid ) dan dilengkapi dengan undang-undang tambahan berikut:

1. Komutatif aditif: $$$x + y = y + x$
2. Distribusi di sebelah kanan: $$$(x + y) \ kali z = (x \ kali z) + (y \ kali z)$
3. Distribusi di sebelah kiri: $$$x \ kali (y + z) = (x \ kali y) + (x \ kali z)$
4. Kehadiran nol di sebelah kanan: $$$x \ kali nol = nol$
5. Kehadiran nol di sebelah kiri: $$$nol \ kali x = nol$

Untuk mengatur semiring yang sesuai dari kelas tipe, gabungkan AdditiveMonoid dan MultiplicativeMonoid :

 @typeclass trait Semiring[A] extends MultiplicativeMonoid[A] with AdditiveMonoid[A] 

Sekarang kita memiliki Semiring , kita dapat menggunakannya dengan berbagai jenis numerik: Int , Long , BigDecimal , dll., Tetapi apakah itu benar-benar layak untuk seluruh artikel tentang setengah dering? Ternyata banyak hal lain juga setengah cincin, termasuk nilai-nilai logis, set, dan bahkan animasi .

Saya ingin mencatat bahwa adalah mungkin untuk membentuk homomorfisme semi-cincin dari banyak tipe menjadi jumlah total perwakilan yang mungkin dari tipe-tipe ini. Apa artinya ini? Yah, bersabarlah, dan saya akan mencoba menjelaskan apa yang saya maksud.

Nomor kardinal

Mari kita mulai dengan apa yang secara umum dimaksud dengan nomor kardinal. Setiap tipe sesuai dengan jumlah nilai yang bisa diambil oleh perwakilan tipe ini. Misalnya, tipe Boolean memiliki nomor kardinal $$$2$ karena hanya memiliki dua nilai yang mungkin: true dan false .

Jadi, di Boolean - $$$2$ , tapi berapa banyak tipe lainnya? Byte - $$$2 ^ 8$ , Short - $$$2 ^ {16}$ , di Int - $$$2 ^ {32}$ dan Long $$$2 ^ {64}$ . Bagaimana dengan string? String adalah tipe yang secara formal tidak terbatas dan secara teoretis memiliki jumlah nilai yang tak terbatas (dalam praktiknya, tentu saja, kita tidak memiliki memori yang tak terbatas, sehingga jumlah spesifik akan bergantung pada konfigurasi komputer).

Untuk tipe apa lagi yang dapat kita tentukan nomor kardinalnya? Dua contoh yang cukup sederhana: Unit , yang memiliki tepat satu perwakilan, dan Nothing , yang merupakan batas bawah dari semua jenis yang mungkin di Scala dan karenanya memiliki $$$0$ nilai yang mungkin. Artinya, Anda tidak pernah dapat membuat nilai Nothing , yang sesuai dengan nomor kardinal $$$0$ .

Hebat, sekarang Anda dapat mencoba untuk mengekspresikannya dalam kode. Kita bisa membuat kelas tipe yang bisa memberi kita jumlah total nilai dari tipe yang sesuai.

 trait Cardinality[A] { def cardinality: BigInt } object Cardinality { def of[A: Cardinality]: BigInt = apply[A].cardinality def apply[A: Cardinality]: Cardinality[A] = implicitly } 

Sekarang cobalah untuk membuat beberapa contoh kelas ini:

 implicit def booleanCardinality = new Cardinality[Boolean] { def cardinality: BigInt = BigInt(2) } implicit def longCardinality = new Cardinality[Long] { def cardinality: BigInt = BigInt(2).pow(64) } implicit def intCardinality = new Cardinality[Int] { def cardinality: BigInt = BigInt(2).pow(32) } implicit def shortCardinality = new Cardinality[Short] { def cardinality: BigInt = BigInt(2).pow(16) } implicit def byteCardinality = new Cardinality[Byte] { def cardinality: BigInt = BigInt(2).pow(8) } implicit def unitCardinality = new Cardinality[Unit] { def cardinality: BigInt = 1 } implicit def nothingCardinality = new Cardinality[Nothing] { def cardinality: BigInt = 0 } 

[ Catatan: nilai yang diberikan juga dapat dinyatakan sebagai implicit val ]

Mari kita coba di REPL :

 scala> Cardinality.of[Int] res11: BigInt = 4294967296 scala> Cardinality.of[Unit] res12: BigInt = 1 scala> Cardinality.of[Long] res13: BigInt = 18446744073709551616 

Bagus, tapi semuanya sangat sederhana, bagaimana dengan ADT ? Bisakah kita menanganinya dengan cara ini? Ternyata kita bisa, kita hanya perlu memahami bagaimana menangani jumlah dan produk jenis yang paling sederhana. Untuk memulai, pertimbangkan produk jenis paling sederhana: (Boolean, Byte)

Berapa banyak perwakilan dari tipe ini? Kita tahu bahwa Boolean $$$2$ dan Byte $$$256$ . Jadi, angka dari $$$-128$ sebelumnya $$$127$ dikombinasikan dengan true atau false . Ternyata $$$512$ nilai-nilai unik.

$$$512$ Sepertinya $$$256$ kali $$$2$ , jadi mungkin Anda hanya perlu mengalikan jumlah nilai dari tipe pertama dengan jumlah nilai yang kedua? Jika Anda memeriksa ini dengan sisa contoh, pastikan ini benar. Mari kita bayangkan ini sebagai turunan dari kelas tipe:

 implicit def tupleCardinality[A: Cardinality, B: Cardinality] = new Cardinality[(A, B)] { def cardinality: BigInt = Cardinality[A].cardinality * Cardinality[B].cardinality } 

Sekarang perhatikan contoh dari sejumlah jenis: Either[Boolean, Byte] . Dalam hal ini, jawabannya bahkan lebih jelas, karena nilai jenis ini (pada kenyataannya) dapat berupa Boolean atau Byte , sehingga cukup dengan hanya menambahkan nomor kardinal. Jadi Either[Boolean, Byte ] seharusnya memilikinya $$$256 + 2 = $ 25$ perwakilan.

Mari kita ungkapkan dengan cara yang sama dalam kode dan konfirmasikan hasilnya dalam REPL:

 implicit def eitherCardinality[A: Cardinality, B: Cardinality] = new Cardinality[Either[A, B]] { def cardinality: BigInt = Cardinality[A].cardinality + Cardinality[B].cardinality } scala> Cardinality.of[(Boolean, Byte)] res14: BigInt = 512 scala> Cardinality.of[Either[Boolean, Byte]] res15: BigInt = 258 scala> Cardinality.of[Either[Int, (Boolean, Unit)]] res16: BigInt = 4294967298 

Akibatnya, untuk jumlah jenis nomor kardinal ditambahkan, dan untuk produk dikalikan. Ini logis mengingat nama mereka.

Jadi bagaimana dengan homomorfisme yang dibahas sebelumnya? Homomorfisme adalah pemetaan pelestarian struktur antara dua struktur aljabar dari jenis yang sama (dalam hal ini, semiring).

Ini berarti untuk apa saja $$$x$ , $$$y$ dan homomorfisme $$$f$ kami memiliki:

1. $$$f (x \ kali y) = f (x) \ kali f (y)$
2. $$$f (x + y) = f (x) + f (y)$

Ekspresi yang terakhir mungkin tampak cukup abstrak, tetapi mereka terkait langsung dengan apa yang baru saja kita lakukan. Jika kita "menambahkan" dua jenis Byte dan Boolean , maka kita mendapatkan Either[Byte, Boolean] , dan jika kita menerapkan kardomority homomorfisme padanya, kita mendapatkan $$$258$ . Ini setara dengan menerapkan cardinality ke Byte dan Boolean secara terpisah, diikuti dengan menjumlahkan hasilnya.

Tentu saja, hal yang sama berlaku untuk perkalian dan produk jenis. Namun demikian, kami masih kekurangan sesuatu untuk setengah-cincin yang benar, karena kami hanya menyebutkan penambahan dan perkalian, tetapi bukan elemen individu yang sesuai.

Seperti yang telah kita lihat, tipe Unit satu perwakilan, dan tipe Nothing tidak Nothing . Bisakah kita menggunakan dua tipe ini untuk membentuk setengah cincin?

Ayo kita coba! Jika Unit adalah unit perkalian, maka produk dari jenis apa pun dengan Unit harus setara dengan jenis pertama. Secara alami, ini dilakukan, karena kita dapat dengan mudah memetakan sesuatu dari debit (Int, Unit) ke Int dan sebaliknya tanpa kehilangan, sehingga jumlah kardinal tetap tidak berubah.

 scala> Cardinality.of[Int] res17: BigInt = 4294967296 scala> Cardinality.of[(Unit, Int)] res18: BigInt = 4294967296 scala> Cardinality.of[(Unit, (Unit, Int))] res19: BigInt = 4294967296 

Bagaimana dengan Nothing ? Karena ini adalah unit tambahan, jumlah jenis apa pun dengan Nothing harus sama dengan jenis yang sama. Apakah Either[Nothing, A] cocok dengan A ? Ya! Karena Nothing memiliki makna, Either[Nothing, A] hanya bisa menjadi Right dan, sebagai akibatnya, hanya A , jadi jenis ini setara.

Kita juga perlu memeriksa kebenaran nol dengan perkalian: angka apa pun yang dikalikan dengan kesatuan dengan menambahkan zero harus cocok dengan zero . Karena Nothing merupakan unit tambahan kami, produk dari jenis seperti (Int, Nothing) harus setara dengan Nothing . Ini dilakukan karena kami tidak dapat membuat nilai tipe Nothing dan, sebagai hasilnya, tuple berisi nilai tersebut.

Mari kita periksa bagaimana ini berhubungan dengan nomor kardinal.

Unit penambahan:

 scala> Cardinality.of[Either[Nothing, Boolean]] res0: BigInt = 2 scala> Cardinality.of[Either[Nothing, (Byte, Boolean)]] res1: BigInt = 258 

Penyerapan oleh nol:

 scala> Cardinality.of[(Nothing, Boolean)] res0: BigInt = 0 scala> Cardinality.of[(Nothing, Long)] res1: BigInt = 0 

Tetap memverifikasi keabsahannya. Dalam konteks tipe, ini berarti bahwa (A, Either[B, C]) harus cocok dengan Either[(A, B), (A, C)] . Jika Anda memeriksa, maka kedua jenis ini akan benar-benar setara.

 scala> Cardinality.of[(Boolean, Either[Byte, Short])] res20: BigInt = 131584 scala> Cardinality.of[Either[(Boolean, Byte), (Boolean, Short)]] res21: BigInt = 131584 

Struktur aljabar tingkat tinggi

Beberapa mungkin sudah pernah mendengar tentang kelas tipe Semigroupal . Tetapi mengapa disebut demikian dan bagaimana hubungannya dengan Semigroup ? Untuk memulai, mari lihat Semigroupal itu sendiri:

 @typeclass trait Semigroupal[F[_]] { def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] } 

Ada kesamaan tertentu dengan Semigroup : dua nilai digabungkan, dan operasi yang sesuai harus asosiatif (mirip dengan Semigroup ).

Sejauh ini, sangat bagus, tetapi fungsi nama product agak membingungkan. Itu logis, karena kita menggabungkan A dan B menjadi tupel, yang merupakan produk tipe, tetapi jika kita menggunakan produk, mungkin itu bukan Semigroupal sewenang-wenang, tetapi multiplikatif? Mari kita ganti namanya.

 @typeclass trait MultiplicativeSemigroupal[F[_]] { def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] } 

Sekarang mari kita lihat seperti apa bentuk Semigroupal tambahan. Secara alami, yang harus kita ubah adalah produk tipe untuk penjumlahan:

 @typeclass trait AdditiveSemigroupal[F[_]] { def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]] } 

Kelihatannya bagus - bisakah kita menambahkan unit untuk mendapatkan Monoidal ? Tentu kita bisa! Ini lagi-lagi akan menjadi Nothing dan Unit untuk jumlah dan produk, masing-masing:

 @typeclass trait AdditiveMonoidal[F[_]] extends AdditiveSemigroupal[F] { def nothing: F[Nothing] } @typeclass trait MultiplicativeMonoidal[F[_]] extends MultiplicativeSemigroupal[F] { def unit: F[Unit] } 

Sekarang kita memiliki kelas tipe ini, tetapi bagaimana kita bisa menggunakannya? Yah, saya yakin menyatakan bahwa mereka sudah digunakan di perpustakaan kucing , tetapi dengan nama yang berbeda.

Seperti apa kelas-kelas ini? Untuk memulai, lihat fungsi sum dan cobalah untuk menemukan sesuatu yang mirip dengan AdditiveSemigroupal . Karena analog dari kelas-kelas ini untuk tipe pesanan lebih rendah memiliki operator simbolik yang sesuai, mari tambahkan operator tersebut ke AdditiveSemigroupal .

Karena ini adalah jumlah, operator ini kemungkinan besar harus mengandung + dan menunjukkan bahwa operasi sedang dilakukan dalam beberapa konteks. Akan ideal untuk menggunakan sesuatu seperti [+] , tetapi ini adalah pengidentifikasi yang tidak valid, jadi cobalah <+> sebagai gantinya.

 def <+>[A, B](fa: F[A], fb: F[B]): F[Either[A, B]] 

Fungsi <+> sudah ada pada kucing sebagai alias untuk combineK , yang dapat ditemukan di SemigroupK , tetapi berperilaku berbeda. Dibutuhkan dua F[A] untuk input dan mengembalikan F[A] - tidak persis seperti yang kita miliki.

Atau serupa? Faktanya, kedua fungsi ini bertepatan dan kita dapat mendefinisikan satu melalui yang lainnya di hadapan functor:

 def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]] def combineK[A](x: F[A], y: F[A]): F[A] = { val feaa: F[Either[A, A]] = sum(x, y) feaa.map(_.merge) } 

Karena AdditiveSemigroupal setara dengan SemigroupK , mungkinkah AdditiveMonoidal sama dengan MonoidK ? Ya, dan itu mudah ditampilkan. MonoidK dilengkapi dengan fungsi empty :

 def empty[A]: F[A] 

Fungsi ini menggunakan quantifier universal untuk A , yaitu, ia bekerja untuk setiap A , yang berarti bahwa pada kenyataannya ia tidak dapat beroperasi pada A tertentu dan karenanya setara dengan F[Nothing] di AdditiveMonoidal .

Yah, kami menemukan analog untuk kelas aditif dan sudah tahu bahwa MultiplicativeSemigroupal setara dengan cats.Semigroupal . Yang tersisa bagi kita adalah menemukan yang setara dengan MultiplicativeMonoidal .

Saya sedikit curang dan mengatakan bahwa ini setara adalah Applicative . Ia menambahkan fungsi pure yang mengambil A dan mengembalikan F[A] . MultiplicativeMonoidal pada gilirannya, memiliki fungsi unit yang tidak mengambil parameter dan mengembalikan F[Unit] . Bagaimana cara berpindah dari satu ke yang lain? Jawabannya lagi menyiratkan menggunakan functor:

 def unit: F[Unit] def pure(a: A): F[A] = unit.map(_ => a) 

Applicative menggunakan functor kovarian, tetapi dalam kasus umum, kita juga dapat menggunakan struktur invarian dan contravarian. Selain itu, Applicative menyertakan <*> sebagai alias untuk kombinasi product dan map , yang terlihat seperti petunjuk lain bahwa ini adalah kelas multiplikatif dan intuisi tidak mengecewakan kita.

Sekarang pada kucing kita memiliki <+> dan <*> , tetapi adakah kelas tipe yang menggabungkan mereka, mirip dengan bagaimana Semiring menggabungkan + dan * ? Ya, dan itu disebut Alternative . Ini diwarisi dari Applicative dan MonoidK . Agar konsisten, kami akan menyebutnya Semiringal :

 @typeclass trait Semiringal[F[_]] extends MultiplicativeMonoidal[F] with AdditiveMonoidal[F] 

Hebat, sekarang kami memiliki Semiring , dan mitra untuk jenis pesanan yang lebih tinggi. Sayangnya, yang pertama tidak pada kucing , tetapi mungkin akan muncul di versi mendatang.

Jika tersedia, kita dapat menyimpulkan Semiring untuk Alternative apa pun Alternative mirip dengan menyimpulkan MonoidK untuk MonoidK atau Applicative . Juga, kita bisa mengubah Semiring kembali menjadi Alternative menggunakan Const , mirip dengan mengubah Monoid menjadi Applicative .

Sebagai kesimpulan, mari kita lihat bagaimana transformasi ini dapat ditulis:

 import Semiring.ops._ case class Const[A, B](getConst: A) implicit def constSemiringal[A: Semiring] = new Semiringal[Const[A, ?]] { def sum[B, C](fa: Const[A, B], fb: Const[A, C]): Const[A, Either[B, C]] = Const(fa.getConst + fb.getConst) def product[B, C](fa: Const[A, B], fb: Const[A, C]): Const[A, (B, C)] = Const(fa.getConst * fb.getConst) def unit: Const[A, Unit] = Const(Semiring[A].one) def nothing: Const[A, Nothing] = Const(Semiring[A].zero) } 

Kesimpulan

Cincin dan setengah cincin adalah struktur aljabar yang sangat menarik, dan bahkan jika Anda tidak memikirkannya, kemungkinan besar Anda sudah menggunakannya. Posting ini ditulis untuk menunjukkan bagaimana Applicative dan MonoidK berhubungan dengan MonoidK , mengapa tipe data aljabar membentuk setengah-cincin, dan bagaimana struktur aljabar ini menyebar dalam Scala dan bahasa pemrograman lainnya. Bagi saya pribadi, realisasi tentang bagaimana ini saling berhubungan dan membentuk simetri yang sangat menarik hanyalah sebuah ledakan otak, dan saya berharap posting ini dapat membantu menemukan persamaan yang serupa di Cats dan perpustakaan lain berdasarkan berbagai abstraksi matematis. Anda dapat menemukan materi lebih lanjut tentang topik ini di sini .

Selain itu

Dalam posting ini, saya tetap diam tentang komutatifitas dalam catatan kelas tipe. Commutativity adalah properti yang sangat penting untuk semiring dan kode harus mencerminkan properti ini. Namun, karena postingan tersebut sudah mengandung banyak definisi, menambahnya dengan beberapa kelas tipe komutatif yang tidak melakukan apa-apa selain memperkenalkan undang-undang baru tampak berlebihan dan mengalihkan perhatian dari tujuan utama postingan tersebut.

Selain itu, saya fokus pada jumlah kardinal dari hanya kelas-kelas yang kami butuhkan, tetapi untuk kelengkapan, Anda dapat menambahkan definisi Cardinality untuk hal-hal seperti A => B , Option[A] , Ior[A, B] :

1.  Cardinality.of[A => B] === Cardinality.of[B].pow(Cardinality.of[A]) 

   
   

2.  Cardinality.of[Option[A]] === Cardinality.of[A] + 1 

   
   

3.  Cardinality.of[Ior[A, B]] === Cardinality.of[A] + Cardinality.of[B] + Cardinality.of[A] * Cardinality.of[B]