نقل ذئب وماعز وملفوف عبر النهر مع التأثيرات في هاسكل

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

سنحاول في هذه المقالة إيجاد حل عام لهذا النوع من الألغاز باستخدام التأثيرات الجبرية.



لنبدأ بأبسطها - طريق السفر. نظرًا لأننا لا نعرف مسبقًا العدد المضمون للخطوات التي سنحصل عليها بعد ذلك ، يمكننا بناء طريق لا نهائي ، على أي حال سنحسبه بتكاسل:

data Direction = Back | Forward

route :: [Direction]
route = iterate alter Forward

alter :: Direction -> Direction
alter Back = Forward
alter Forward = Back

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

data Character = Wolf | Goat | Cabbage deriving Eq

class Survivable a where
	survive :: a -> a -> Ordering

instance Survivable Character where
	survive Wolf Goat = GT
	survive Goat Wolf = LT
	survive Goat Cabbage = GT
	survive Cabbage Goat = LT
	survive _ _ = EQ

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

• , , . , .
• , ( , ) . type River a = ([a],[a]) c State (River a).
• - , — Maybe.

في رمز، وسوف تستخدم بلدي التجريبية المشتركة مكتبة (هناك نوعان من المواد على حبري شرح جوهرها - و الأولى و الثانية )، ولكن إذا رغبت في ذلك، والحل يمكن نقلها إلى المحولات أو MTL .



إذن ، لدينا ثلاثة تأثيرات متباينة: الحالة ، التعددية ، الجزئية. نحتاج الآن إلى تحديد كيفية ترتيبها معًا:

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

يمكن وصف حركة واحدة في اللغز بأنها سلسلة من الإجراءات:

1. احصل على طاقم الشخصيات على الشاطئ الحالي
2. اختر الشخصية التالية لنقلها
3. انقل الشخصية إلى الضفة المقابلة

step direction = bank >>= next >>= transport

لنستعرض كل خطوة بمزيد من التفصيل.



اعتمادًا على اتجاه حركة القارب ، نطبق العدسة لمصدر المغادرة على حالة النهر بالكامل ونحصل على تكوين الضفة الحالية:

bank :: (Functor t, Stateful (River a) t) => t [a]
bank = view (source direction) <$> current

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

\xs -> Nothing : (Just <$> xs) 

لكل مرشح (القارب الفارغ ( لا شيء ) مرشح أيضًا) ، نتحقق من عدم وجود شخصيات على الشاطئ المتبقي لا يمانعون في أكل بعضهم البعض:

valid :: Maybe a -> Bool
valid Nothing = and $ coexist <$> xs <*> xs
valid (Just x) = and $ coexist <$> delete x xs <*> delete x xs

coexist :: Survivable a => a -> a -> Bool
coexist x y = survive x y == EQ

وعندما نصفي مساحة اختيار الأحرف ، نرفع تأثير التعددية ونعيد كل عنصر من مساحة التحديد هذه:

next :: (Survivable a, Iterable t) => [a] -> t (Maybe a)
next xs = lift . filter valid $ Nothing : (Just <$> xs)

تبقى الخطوة الأخيرة - النقل الفعلي باستخدام العدسات: أزل الحرف من بنك الإرسال وأضف إلى بنك الوجهة:

leave, land :: River a -> River a
leave = source direction %~ delete x
land = target direction %~ (x :)

إذا كان هناك شخصية في القارب ، فإننا نغير حالة النهر ، وإلا كانت الحركة خامدة:

transport :: (Eq a, Applicative t, Stateful (River a) t) => Maybe a -> t (Maybe a)
transport (Just x) = modify @(River a) (leave . land) $> Just x where
transport Nothing = pure Nothing

سيكون من الجيد رؤية البرنامج قيد التنفيذ. لإيجاد حل ، نحتاج إلى اتخاذ سبع خطوات على الأقل على طول الطريق:

start :: River Character
start = ([Goat, Wolf, Cabbage], [])

solutions = run (traverse step $ take 7 route) start

ولدينا حلان:







يمكن الاطلاع على المصادر الكاملة هنا .