محاولة تكوين غير قابل للتكوين: مخططات الالتحام

مقدمة

في Haskell ، من المعتاد العمل مع المؤثرات كمدافعين تكون كائناتهم بعض التعبيرات التي نهتم بها في الوقت الحالي.

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

قبل المتابعة ، ستستخدم المقالة عدة تعريفات:

type (:=) ta = ta -- |   type (:.) tua = t (ua) -- |   type (~>) tu = forall a . ta -> ua -- |   

على سبيل المثال: قائمة:. ربما: = أ - هذا التعبير سهل التخيل ، هذه قائمة بالقيم التي يكون وجودها محل تساؤل.

علاوة على ذلك ، على سبيل المثال ، سوف نستخدم أربعة أنواع شائعة: القارئ ، الولاية ، إما ، ربما .

التراكيب والمحولات

إن الطريقة الأكثر وضوحًا لتطبيق أكثر من تأثير على تعبير ما هي ببساطة تضمين أحدهما في الآخر ، وهذا هو التكوين المعتاد للمُعامِل. في التراكيب ، لا يكون للتأثيرات تأثير على بعضها البعض (ما لم يتم استخدام طرق قابلة للتنقل عليها). ومن أجل دمج العديد من الآثار في واحد ، يتم استخدام المحولات. كل طريقة لها مزاياها وعيوبها:

المؤلفات:

• لا توجد أنواع إضافية مطلوبة لبنائها
• لا توجد طريقة عامة لدمج التأثيرات مع فئات Functor / Applicative / Monad
• كل شيء يتكون بشكل رائع حتى يصل الأمر إلى monads

المحولات:

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

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

مخططات الإرساء

إذا ألقينا نظرة فاحصة على أنواع المحولات الأحادية ، فيمكننا تحديد بعض الأنماط:

 newtype ReaderT rma = ReaderT { runReaderT :: r -> ma } newtype MaybeT ma = MaybeT { runMaybeT :: m (Maybe a) } newtype ExceptT ema = ExceptT { runExceptT :: m (Either ea)) } newtype StateT sma = StateT { runStateT :: s -> m (a,s) } 

تصف المحولات حالة خاصة حول كيفية ربط التأثير الحالي المحدد وغير المحدد.

دع t يكون محددًا وأنك غير محدد ، فحاول:

 Reader: r -> ua ===> (->) r :. u := a ===> t :. u := a -- t ~ (->) r Maybe: u (Maybe a) ===> u :. Maybe := a ===> u :. t := a -- t ~ Maybe Either: u (Either ea) ===> u :. Either e := a ===> u :. t := a -- t ~ Either e 

بعض الآثار معقدة للغاية ويمكن تعريفها من خلال تكوين تأثيرات أخرى أبسط:

 State: s -> u (a, s) ===> (->) s :. (,) s := a ==> t :. u :. t' := a -- t ~ (->) s, t' ~ (,) s newtype State sa = State ((->) s :. (,) s := a) 

إذا ألقينا نظرة فاحصة على الأمثلة الثلاثة الأولى ، فيمكننا ملاحظة أنماط شائعة: في Reader ، يختفي تأثير معين بتأثير غير مسمى (يأخذه بين قوسين ، يصبح كائنًا من المُشغِّل) ، ثم مع إما إما وربما يكون هو عكس ذلك - هناك تأثير غير محدد يختتم بنوع معين. في حالة الحالة ، نضع المشغل بين اثنين من الآثار المحددة الأكثر بساطة.

دعنا نحاول التعبير عن هذه الأنماط في الأنواع:

 newtype TU tua = TU (t :. u := a) newtype UT tua = UT (u :. t := a) newtype TUT tut' a = TUT (t :. u :. t' := a) 

لقد حددنا مخططات الالتحام - وهذا هو تكوين من functor في غلاف يشير إلى موقف تأثير محدد وغير محدد.

في الواقع ، طرق المحولات التي تبدأ أسماؤها بالتشغيل ببساطة تزيل غلاف المحول ، وتعيد تكوين المحولات. نحن تصف هذه الفئة من الأنواع:

 class Composition t where type Primary ta :: * run :: ta -> Primary ta 

الآن لدينا طريقة عالمية لتشغيل هذه الدوائر:

 instance Composition (TU tu) where type Primary (TU tu) a = t :. u := a run (TU x) = x instance Composition (UT tu) where type Primary (UT tu) a = u :. t := a run (UT x) = x instance Composition (TUT tu t') where type Primary (TUT tu t') a = t :. u :. t' := a run (TUT x) = x 

ماذا عن المحولات؟ هنا ستحتاج أيضًا إلى فئة من النوع يتم فيها تحديد مخطط لرسو السفن لنوع معين ، ويتم الإعلان عن طريقة التضمين لرفع التأثير غير المحدد إلى مستوى المحول والبناء لإنشاء تأثير محدد في محول:

 class Composition t => Transformer t where type Schema (t :: * -> *) (u :: * -> *) = (r :: * -> *) | r -> tu embed :: Functor u => u ~> Schema tu build :: Applicative u => t ~> Schema tu type (:>) tua = Transformer t => Schema tua 

الآن يبقى الإعلان عن الحالات ، ابدأ بـ ربما وأما :

 instance Transformer Maybe where type Schema Maybe u = UT Maybe u embed x = UT $ Just <$> x build x = UT . pure $ x instance Transformer (Either e) where type Schema (Either e) u = UT (Either e) u embed x = UT $ Right <$> x build x = UT . pure $ x 

سنقوم بإنشاء نوع خاص بنا لـ Reader ، لأنه ليس في الأساس . ويحتاج أيضًا إلى مثيل لفئة Composition ، لأنه غلاف لبرنامج functor:

 newtype Reader ea = Reader (e -> a) instance Composition (Reader e) where type Primary (Reader e) a = (->) ea run (Reader x) = x instance Transformer (Reader e) where type Schema (Reader e) u = TU ((->) e) u embed x = TU . const $ x build x = TU $ pure <$> run x 

افعل شيئًا مماثلاً مع الدولة :

 newtype State sa = State ((->) s :. (,) s := a) instance Composition (State s) where type Primary (State s) a = (->) s :. (,) s := a run (State x) = x instance Transformer (State s) where type Schema (State s) u = TUT ((->) s) u ((,) s) embed x = TUT $ \s -> (s,) <$> x build x = TUT $ pure <$> run x 

كمثال

يبقى اختبار هذا على مشاكل العالم الحقيقي - على سبيل المثال ، سنكتب برنامجًا يحسب الموضع الصحيح لأنواع مختلفة من الأقواس.

تحديد أنواع الأقواس: يمكن فتحها وإغلاقها ؛ وأيضا أنماط مختلفة:

 data Shape = Opened | Closed data Style = Round | Square | Angle | Curly 

الرموز الأخرى لبرنامجنا ليست مثيرة للاهتمام:

 data Symbol = Nevermind | Bracket Style Shape 

نحدد أيضًا قائمة بالأخطاء التي قد يواجهها برنامجنا:

 data Stumble = Deadend (Int, Style) --     | Logjam (Int, Style) --     | Mismatch (Int, Style) (Int, Style) --       

ما الآثار التي يحتاجها برنامجنا؟ نحتاج إلى الاحتفاظ بقائمة من الأقواس التي تنتظر التحقق ونحتاج إلى التوقف عند الخطأ الأول الذي تم مواجهته. نحن نصنع محول:

 State [(Int, Style)] :> Either Stumble := () 

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

 checking :: Traversable t => t (Int, Symbol) -> Either Stumble () checking struct = run (traverse proceed struct) [] >>= \case (s : _, _) -> Left . Logjam $ s where ([], _) -> Right () 

نتذكر أي شريحة مفتوحة ، مقارنة أي مغلقة مع فتح آخر تذكر:

 proceed :: (Int, Symbol) -> State [(Int, Style)] :> Either Stumble := () proceed (_, Nevermind) = pure () proceed (n, Bracket style Opened) = build . modify . (:) $ (n, style) procceed (n, Bracket closed Closed) = build get >>= \case []-> embed $ Left . Deadend $ (n, closed) ((m, opened) : ss) -> if closed /= opened then embed . Left $ Mismatch (m, opened) (n, closed) else build $ put ss where 

استنتاج

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

كود المكتبة على جيثب | وثائق الاختراق | مثال الأقواس