حكاية النصف خواتم

مرحبا يا هبر! أوجه انتباهكم إلى ترجمة لمقال "قصة عن Semirings" بقلم لوكا جاكوبوفيتش.

تساءلت يوما لماذا يسمى مجموع الأنواع مجموع الأنواع. أو ربما كنت تريد دائمًا معرفة سبب كتابة المشغل <*> بهذه الطريقة؟ وما علاقة هذا بنصف الحلقات؟ المهتمين يرجى السؤال عن خفض!

هذه المقالة هي ترجمة لنشر مدونة Typelevel كتبها Luke Jakobovic. للحصول على أفضل تصور ، يحتاج المرء على الأقل إلى معرفة سطحية بلغة سكالا ونظامها الإيكولوجي (بما في ذلك مكتبة القطط) ومعرفة بالمفاهيم الأساسية للجبر التجريدي: نصف مجموعة ، monoid ، إلخ.

الهياكل الجبرية

الكثير منا يعرف عن monoids و semigroups وحتى استخدامها. هذه الهياكل لها خصائص تتيح لك تطبيقها مباشرة للحصول على مستوى أعلى من التجريد (إذا كنت لا تعرف عنها ، فيمكنك قراءة الوثائق من مكتبة القطط ). ومع ذلك ، في بعض الأحيان يحتوي نوع البيانات على أكثر من monoid أو semigroup. مثال واضح هو الأنواع العددية المختلفة ، حيث الضرب والإضافة يشكلان أحاديتين كاملتين.

في الجبر المجرد ، هناك فئة منفصلة من الهياكل مع اثنين من أحاديات التفاعل بطريقة معينة. هذه الفئة هي حلقات نصف. نظرًا لأن الأحاديات تستخدم غالبًا لوصف الأنواع العددية ، يتم تقسيمها عادةً إلى مضاعفات ومضافات. كما في حالة الأرقام ، تحدد قوانين الفصل النصي أن الضرب يتم توزيعه عن طريق الجمع ، وضرب أي عدد بالوحدة بالجمع - الصفر - يعطي صفرًا.

هناك عدة طرق لتقديم هذا كأنواع الكتابة والمكتبات المختلفة تقوم بذلك بطريقتها الخاصة ، ولكن دعونا ننظر في كيفية القيام بذلك في مشروع الجبر . الأساس في ذلك هو AdditiveSemigroup و MultiplicativeSemigroup .

[ ملاحظة: نظرًا لأن اسم "type class" لم يتجذر باللغة الروسية ، فسيتم استخدام إصدار اللغة الإنجليزية الخاص به لاحقًا - type class ]

 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 } 

[ ملاحظة: يتيح لك التعليق التوضيحيtypeclass من مشروع simulacrum إنشاء الأساليب المستخدمة بشكل متكرر لفئات الكتابة ولا يؤثر على المكون المنطقي للرمز ]

في هذه الحالة ، يكون semiring ( Semiring ) عبارة عن Semiring المضافة ( AdditiveMonoid ) ، مقترنة مع monoid MultiplicativeMonoid ( MultiplicativeMonoid ) ومجهزة بالقوانين الإضافية التالية:

1. مبدلة المضافة: $$$x + y = y + x$
2. التوزيع على اليمين: $$$(x + y) \ times z = (x \ times z) + (y \ times z)$
3. التوزيع على اليسار: $$$x \ times (y + z) = (x \ times y) + (x \ times z)$
4. وجود صفر على اليمين: $$$س \ مرات صفر = صفر دولا$
5. وجود صفر على اليسار: $$$صفر \ مرات x = صفر دولا$

لتعيين الفصل المقابل من فئة النوع ، اجمع AdditiveMonoid و MultiplicativeMonoid :

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

الآن بعد أن أصبح لدينا Semiring ، يمكننا استخدامه مع أنواع رقمية متنوعة: Int ، Long ، BigDecimal ، وما إلى ذلك ، ولكن هل يستحق كل المقالة حقًا عن حلقات نصفية؟ اتضح أن العديد من الأشياء الأخرى هي أيضًا حلقات نصفية ، بما في ذلك القيم المنطقية والمجموعات وحتى الرسوم المتحركة .

أود أن أشير إلى أنه من الممكن تشكيل تجانس شبه دائري من أنواع كثيرة إلى العدد الإجمالي للممثلين المحتملين لهذه الأنواع. ماذا يعني هذا؟ حسنًا ، كن صبوراً ، وسأحاول شرح ما أقصده.

الأرقام الأساسية

لنبدأ مع ما هو المقصود عموما من قبل عدد الكاردينال. يتوافق كل نوع مع عدد القيم التي يمكن أن يتخذها ممثلو هذا النوع. على سبيل المثال ، يحتوي النوع Boolean على رقم أساسي $$ لأنه يحتوي على اثنين فقط من القيم الممكنة: true false .

لذلك ، في Boolean - $$ ، ولكن كم عدد الأنواع الأخرى؟ Byte - $$$2 ^ 8$ ، Short - $$$2 ^ {16}$ في Int - $$$2 ^ {32}$ Long $$$2 ^ {64}$ . ماذا عن الأوتار؟ String عبارة عن نوع غير محدود رسميًا وله نظريًا عددًا لا حصر له من القيم (في الممارسة العملية ، بالطبع ، ليس لدينا ذاكرة لانهائية ، وبالتالي فإن الرقم المحدد يعتمد على تكوين الكمبيوتر).

لأي أنواع أخرى يمكننا تحديد رقم الكاردينال الخاص بهم؟ مثالان بسيطان إلى حد ما: Unit ، التي لها ممثل واحد تمامًا ، ولا Nothing ، وهو الحد الأدنى لجميع الأنواع الممكنة في سكالا ، وبالتالي $$$0$ القيم الممكنة. وهذا يعني أنه لا يمكنك أبدًا إنشاء قيمة لـ Nothing ، والتي تتوافق مع رقم أساسي $$$0$ .

عظيم ، الآن يمكنك محاولة التعبير عن هذا في التعليمات البرمجية. يمكننا إنشاء فئة كتابة يمكنها أن تعطينا العدد الإجمالي لقيم النوع المقابل.

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

حاول الآن إنشاء مثيلات متعددة لهذه الفئة:

 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 } 

[ ملاحظة: يمكن أيضًا اعتبار القيم المحددة كقيمة implicit val ]

دعنا نجربهم في REPL :

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

رائع ، لكن الأمر بسيط للغاية ، ماذا عن ADT ؟ هل يمكننا التعامل معهم بهذه الطريقة؟ اتضح أننا نستطيع ، نحن بحاجة فقط إلى فهم كيفية التعامل مع أبسط المنتجات وأنواع الأنواع. للبدء ، فكر في أبسط منتج للأنواع: (Boolean, Byte)

كم عدد ممثلي هذا النوع؟ نحن نعلم أن Boolean لهم $$ و Byte $$ . وبالتالي ، أرقام من $$$-128 دولا$ إلى $$ جنبا إلى جنب مع true أو false . اتضح $$ قيم فريدة.

$$ يشبه $$ مضروبة $$ ، لذلك ربما تحتاج فقط إلى ضرب عدد قيم النوع الأول بعدد قيم الثانية؟ إذا قمت بالتحقق من ذلك مع بقية الأمثلة ، فتأكد من أن هذا صحيح. دعنا نتخيل هذا كمثال لفئة الكتابة:

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

الآن النظر في مثال على مجموعة من الأنواع: Either[Boolean, Byte] . في هذه الحالة ، يكون الجواب أكثر وضوحًا ، نظرًا لأن قيمة هذا النوع (في الواقع) يمكن أن تكون إما Boolean أو Byte ، لذلك يكفي إضافة الأرقام الأساسية ببساطة. لذلك يجب أن يكون Either[Boolean, Byte ] $$ الممثلين.

دعنا نعبر عنها بنفس الطريقة في الكود ونؤكد النتائج في 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 

وبالتالي ، تتم إضافة الأرقام الأساسية لمجموع الأنواع ، وبالنسبة للمنتج يتم ضربها. هذا منطقي بالنظر إلى أسمائهم.

ماذا عن التجانس الذي تمت مناقشته سابقًا؟ التجانس هو تخطيط الحفاظ على الهيكل بين بنائين جباريين من نفس النوع (في هذه الحالة ، semirings).

هذا يعني أن لأي $$$x$ . $$$ذ$ والتماثل $$$و$ لدينا:

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

قد تبدو التعبيرات الأخيرة مجردة تمامًا ، لكنها مرتبطة مباشرة بما فعلناه للتو. إذا قمنا "بإضافة" نوعين من Byte و Boolean ، Boolean على Either[Byte, Boolean] ، وإذا طبقنا التماثلية cardinality لذلك ، فإننا نحصل على $$ . هذا يعادل تطبيق cardinality على Byte و Boolean بشكل منفصل ، تليها إضافة النتائج.

بالطبع ، ينطبق الشيء نفسه على الضرب والمنتج من الأنواع. ومع ذلك ، لا نزال نفتقر إلى شيء للنصف الصحيح ، حيث ذكرنا الجمع والضرب فقط ، ولكن ليس العناصر الفردية المقابلة.

كما رأينا من قبل ، فإن النوع Unit ممثل واحد ، والنوع Nothing لا شيء. هل يمكننا استخدام هذين النوعين لتشكيل حلقة نصفية؟

لنجربها! إذا كانت Unit هي وحدة الضرب ، فيجب أن يكون المنتج من أي نوع مع Unit مكافئًا للنوع الأول. بطبيعة الحال ، يتم ذلك ، حيث يمكننا بسهولة تعيين شيء ما من التفريغ (Int, Unit) إلى Int والعكس بالعكس دون خسارة ، بحيث يبقى الرقم الأساسي دون تغيير.

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

ماذا عن Nothing ؟ نظرًا لأن هذه وحدة إضافية ، يجب أن يكون مجموع أي نوع بلا Nothing مكافئًا لنفس النوع. هل تتطابق Either[Nothing, A] مع A ؟ نعم! نظرًا لعدم وجود أي معنى ، Either[Nothing, A] يمكن Either[Nothing, A] أن يكون Right ، ونتيجة لذلك ، A فقط ، وبالتالي فإن هذه الأنواع متكافئة.

نحتاج أيضًا إلى التحقق من صحة الصفر عن طريق الضرب: أي عدد مضروب في الوحدة بإضافة zero يجب أن يتطابق مع zero . نظرًا لأن Nothing هي وحدة الإضافة لدينا ، يجب أن يكون منتج أنواع مثل (Int, Nothing) مكافئًا لـ Nothing . يتم ذلك لأننا لا نستطيع إنشاء قيمة من النوع Nothing ، ونتيجة لذلك ، هناك مجموعة تحتوي على هذه القيمة.

دعونا نتحقق من مدى ارتباط ذلك بالأرقام الرئيسية.

وحدة الإضافة:

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

الامتصاص بمقدار صفر:

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

يبقى للتحقق من التوزيع. في سياق الأنواع ، هذا يعني أن (A, Either[B, C]) يجب أن تتطابق مع Either[(A, B), (A, C)] . إذا قمت بالتحقق ، فسيكون هذان النوعان مكافئين بالفعل.

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

الهياكل الجبرية العليا

ربما يكون البعض قد سمع بالفعل عن فئة Semigroupal . ولكن لماذا يطلق عليه ذلك وكيف يرتبط Semigroup ؟ للبدء ، دعونا نلقي نظرة على Semigroupal نفسها:

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

هناك تشابه معين مع Semigroup : يتم الجمع بين قيمتين ، ويجب أن تكون العملية المناظرة مرتبطة (مماثلة لـ Semigroup ).

حتى الآن ، جيد جدًا ، لكن product اسم الوظيفة مربك بعض الشيء. إنه منطقي ، نظرًا لأننا نجمع بين A و B في tuple ، وهو منتج من الأنواع ، ولكن إذا استخدمنا المنتج ، فربما لا يكون Semigroupal تعسفيًا ، لكنه مضاعف؟ دعونا تسميته.

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

الآن ، لنرى كيف تبدو إضافة Semigroupal . بطبيعة الحال ، كل ما يتعين علينا تغييره هو نتاج أنواع للمبلغ:

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

تبدو جيدة - هل يمكننا إضافة وحدات للحصول على Monoidal ؟ بالطبع نستطيع! سيكون هذا مرة أخرى Nothing Unit للمنتج والمنتج ، على التوالي:

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

الآن لدينا هذه الفئات ، ولكن كيف يمكننا استخدامها؟ حسنًا ، أعلن بثقة أنها تستخدم بالفعل في مكتبة القطط ، ولكن بأسماء مختلفة.

ما يمكن أن يكون مثل هذه الطبقات؟ للبدء ، ألقِ نظرة على دالة sum وحاول العثور على شيء مشابه لـ AdditiveSemigroupal . نظرًا لأن نظائر هذه الفئات لأنواع الترتيب الأدنى بها عوامل تشغيل رمزية مقابلة ، فلنقم بإضافة عامل التشغيل هذا إلى AdditiveSemigroupal .

نظرًا لأن هذا هو المبلغ ، يجب أن يحتوي هذا المشغل على الأرجح على + ويشير إلى أن العملية يتم تنفيذها في بعض السياق. سيكون من المثالي استخدام شيء مثل [+] ، لكن هذا معرف غير صالح ، لذلك جرّب <+> بدلاً من ذلك.

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

توجد وظيفة <+> بالفعل في القطط كاسم مستعار لـ combineK ، والتي يمكن العثور عليها في SemigroupK ، لكنها تتصرف بشكل مختلف. يتطلب الأمر إدخال اثنين F[A] وإرجاع F[A] - ليس تمامًا كما لدينا.

أو ما شابه؟ في الواقع ، تتطابق هاتان الوظيفتان ويمكننا تحديد واحدة من خلال الأخرى في وجود عامل:

 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) } 

بما أن AdditiveSemigroupal مكافئ لـ SemigroupK ، فهل من الممكن أن AdditiveMonoidal نفس MonoidK ؟ نعم ، إنه سهل العرض. MonoidK بواسطة الوظيفة empty :

 def empty[A]: F[A] 

تستخدم هذه الوظيفة محددًا عالميًا لـ A ، أي أنها تعمل من أجل أي A ، مما يعني أنه في الواقع لا يمكنها العمل على أي محدد A وبالتالي فهي مكافئة لـ F[Nothing] في AdditiveMonoidal .

حسنًا ، وجدنا نظائرها للفئات المضافة ونعرف بالفعل أن MultiplicativeSemigroupal مكافئ لـ cats.Semigroupal . كل ما تبقى بالنسبة لنا هو العثور على ما يعادل MultiplicativeMonoidal .

لقد خدعت قليلاً وأقول إن هذا المكافئ هو Applicative . يضيف وظيفة pure تأخذ A وتُرجع F[A] . MultiplicativeMonoidal بدوره ، على unit لا تأخذ أي معلمات وتُرجع F[Unit] . كيفية الانتقال من واحد إلى آخر؟ الجواب مرة أخرى يعني استخدام functor:

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

يستخدم Applicative عامل توجيه متغير ، ولكن في الحالة العامة ، يمكننا أيضًا استخدام هياكل ثابتة ومخالفة. بالإضافة إلى ذلك ، يشتمل Applicative <*> كاسم مستعار لمزيج من product map ، والذي يبدو كأنه دليل آخر على أن هذه فئة مضاعفة ولم يفشلنا الحدس.

لدينا الآن في القطط <+> و <*> ، ولكن هل هناك فئة من النوع الذي يجمعها ، على غرار طريقة Semiring يجمع + و * ؟ نعم ، ويسمى Alternative . وراثي من Applicative و MonoidK . لتكون متسقة ، سوف نسميها Semiringal :

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

عظيم ، الآن لدينا Semiring ، ونظيرتها لأنواع الطلب العالي. لسوء الحظ ، الأول ليس في القطط ، ولكن ربما سيظهر في الإصدارات المستقبلية.

إذا كانت متوفرة ، يمكننا أن نستنتج Semiring لأي Alternative غرار استنتاج Monoid لـ MonoidK أو Applicative . أيضًا ، يمكننا إعادة تحويل Semiring إلى Alternative باستخدام Const ، على غرار تحويل Monoid إلى Monoid .

في الختام ، دعونا نرى كيف يمكن كتابة هذا التحول:

 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) } 

استنتاج

تعتبر الحلقات ونصف الحلقات هياكل جبرية شيقة جدًا ، وحتى إذا لم تفكر في الأمر ، فمن المرجح أنك استخدمتها بالفعل. كُتب هذا MonoidK لإظهار مدى MonoidK و MonoidK بـ Monoid ، ولماذا تشكل أنواع البيانات الجبرية شبه الدائري ، وكيف تنتشر هذه الهياكل الجبرية في Scala ولغات البرمجة الأخرى. بالنسبة لي شخصياً ، فإن إدراك كيفية الترابط بين هذه الأشكال وتشكيل تناظر مثير للغاية كان مجرد انفجار دماغي ، وآمل أن يساعد هذا المنشور في العثور على أوجه تشابه مماثلة في Cats وغيرها من المكتبات بناءً على تجريدات رياضية مختلفة. يمكنك العثور على مزيد من المواد حول هذا الموضوع هنا .

إضافة

في هذا المنشور ، التزمت الصمت بشأن الانتقال في سجل فصول الكتابة. تعتبر Commutativity خاصية مهمة جدًا للفصل الدراسي ويجب أن تعكس الشفرة هذه الخاصية. ومع ذلك ، نظرًا لأن المنشور يحتوي بالفعل على العديد من التعريفات ، فإن إضافته إلى العديد من فئات الكتابة التبادلية التي لا تفعل شيئًا سوى إدخال قوانين جديدة تبدو زائدة عن الحاجة وتشتت الانتباه عن الغرض الرئيسي من المنشور.

علاوة على ذلك ، ركزت على الأرقام الأساسية لتلك الفئات التي نحتاجها فقط ، ولكن من أجل الاكتمال ، يمكنك إضافة تعريفات أساسية لأشياء مثل 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]