الصيف الماضي شاركت فيه - برنامج للطلاب من جوجل. كل عام، يختار المنظمون العديد من المشاريع مفتوحة المصدر، بما في ذلك من منظمات معروفة مثل и . تدعو Google الطلاب من جميع أنحاء العالم للعمل في هذه المشاريع.
كمشارك في Google Summer of Code 2019، قمت بتنفيذ مشروع داخل المكتبة مع المنظمة والتي تعمل على تطوير لغة هاسكل - إحدى أشهر لغات البرمجة الوظيفية. Alga هي مكتبة تمثل تمثيل الرسوم البيانية في هاسكل. يتم استخدامه، على سبيل المثال، في - مكتبة Github التي تبني أشجارًا دلالية ورسومًا بيانية للاستدعاء والتبعية بناءً على التعليمات البرمجية ويمكن مقارنتها. كان مشروعي هو إضافة تمثيل آمن للرسوم البيانية والخوارزميات الثنائية لهذا التمثيل.
سأتحدث في هذا المنشور عن تنفيذي لخوارزمية للتحقق من الرسم البياني للثنائية في هاسكل. على الرغم من أن الخوارزمية هي واحدة من أبسط الخوارزميات، إلا أن تنفيذها بشكل جميل وبأسلوب وظيفي استغرق مني عدة تكرارات وتطلب الكثير من العمل. ونتيجة لذلك، استقرت على التنفيذ باستخدام محولات أحادية.
معلومات عني
اسمي فاسيلي ألفيروف، أنا طالب في السنة الرابعة في مدرسة سانت بطرسبرغ للصحة والسلامة والبيئة. في وقت سابق من بلوق كتبت и . الآن أنا في فترة تدريب في في النرويج، حيث أعمل على إيجاد طرق لحل هذه المشكلة . تشمل اهتماماتي الخوارزميات ذات المعلمات والبرمجة الوظيفية.
حول تنفيذ الخوارزمية
مقدمة
يتم تشجيع الطلاب المشاركين في البرنامج بشدة على التدوين. لقد قدموا لي منصة للمدونة . هذه المقالة مترجمة ، كتبته هناك في يوليو باللغة الإنجليزية، مع مقدمة قصيرة.
يمكن العثور على طلب السحب بالرمز المعني .
يمكنك أن تقرأ عن نتائج عملي (باللغة الإنجليزية) .
تهدف هذه المقالة إلى تعريف القارئ بالمفاهيم الأساسية في البرمجة الوظيفية، على الرغم من أنني سأحاول تذكر جميع المصطلحات المستخدمة عندما يحين الوقت.
التحقق من الرسوم البيانية للثنائية
عادة ما يتم تقديم خوارزمية للتحقق من الرسم البياني للثنائية في دورة تدريبية حول الخوارزميات باعتبارها واحدة من أبسط خوارزميات الرسم البياني. فكرته واضحة ومباشرة: أولاً نضع القمم بطريقة ما في حصة اليسار أو اليمين، وعندما يتم العثور على حافة متعارضة، نؤكد أن الرسم البياني ليس ثنائيًا.
مزيد من التفاصيل: أولاً نضع بعض القمم في الحصة اليسرى. من الواضح أن جميع جيران هذه القمة يجب أن يقعوا في الفص الأيمن. علاوة على ذلك، يجب أن يقع جميع جيران جيران هذه القمة في الفص الأيسر، وهكذا. نستمر في تعيين المشاركات إلى القمم طالما لا تزال هناك رؤوس في المكون المتصل من الرأس الذي بدأنا به ولم نقم بتعيين جيران لها. ثم نكرر هذا الإجراء لجميع المكونات المتصلة.
إذا كانت هناك حافة بين القمم التي تقع في نفس القسم، فليس من الصعب العثور على دورة فردية في الرسم البياني، وهو أمر معروف على نطاق واسع (ومن الواضح تمامًا) أنه مستحيل في رسم بياني ثنائي. بخلاف ذلك، لدينا قسم صحيح، مما يعني أن الرسم البياني ثنائي.
عادة، يتم تنفيذ هذه الخوارزمية باستخدام أو . في اللغات الأمرية، عادةً ما يتم استخدام بحث العمق أولاً لأنه أبسط قليلاً ولا يتطلب هياكل بيانات إضافية. لقد اخترت أيضًا البحث العميق أولاً لأنه أكثر تقليدية.
وهكذا وصلنا إلى المخطط التالي. نحن نجتاز رؤوس الرسم البياني باستخدام بحث العمق أولاً ونخصص لها مشاركات، مع تغيير رقم المشاركة أثناء تحركنا على طول الحافة. إذا حاولنا تعيين مشاركة لرأس تم تعيين حصة له بالفعل، فيمكننا القول بأمان أن الرسم البياني ليس ثنائيًا. في اللحظة التي يتم فيها تعيين مشاركة لجميع القمم ونظرنا إلى جميع الحواف، يكون لدينا قسم جيد.
نقاء الحسابات
في هاسكل نفترض أن جميع الحسابات كذلك ينظف. ومع ذلك، إذا كان هذا هو الحال حقًا، فلن يكون لدينا أي طريقة لطباعة أي شيء على الشاشة. على الاطلاق، نظيف الحسابات كسولة جدًا لدرجة أنه لا يوجد واحدة ينظف أسباب لحساب شيء ما. يتم إجبار جميع الحسابات التي تحدث في البرنامج بطريقة أو بأخرى "غير نظيفة" موناد آيو.
Monads هي طريقة لتمثيل العمليات الحسابية تأثيرات في هاسكل. إن شرح كيفية عملهم هو خارج نطاق هذا المنشور. يمكن قراءة وصف جيد وواضح باللغة الإنجليزية .
أريد هنا أن أشير إلى أنه في حين يتم تنفيذ بعض المونادات، مثل IO، من خلال سحر المترجم، يتم تنفيذ جميع الآخرين تقريبًا في البرامج وجميع الحسابات فيها نقية.
هناك الكثير من التأثيرات ولكل منها موناد خاص بها. هذه نظرية قوية وجميلة جدًا: جميع الوحدات الأحادية تطبق نفس الواجهة. سنتحدث عن المونادات الثلاثة التالية:
- إما أن ea عبارة عن عملية حسابية تُرجع قيمة من النوع a أو تطرح استثناءً من النوع e. سلوك هذا الموناد مشابه جدًا لمعالجة الاستثناءات في اللغات الأمرية: يمكن اكتشاف الأخطاء أو تمريرها. والفرق الرئيسي هو أن الموناد يتم تنفيذه بشكل منطقي تمامًا في مكتبة هاسكل القياسية، بينما تستخدم اللغات الحتمية عادةً آليات نظام التشغيل.
- الحالة sa هي عملية حسابية تُرجع قيمة من النوع a ولها حق الوصول إلى الحالة القابلة للتغيير من النوع s.
- ربما. يعبر ربما monad عن عملية حسابية يمكن مقاطعتها في أي وقت عن طريق إرجاع لا شيء. ومع ذلك، سنتحدث عن تنفيذ فئة MonadPlus للنوع ربما، والتي تعبر عن تأثير معاكس: فهي عملية حسابية يمكن مقاطعتها في أي وقت عن طريق إرجاع قيمة معينة.
تنفيذ الخوارزمية
لدينا نوعان من البيانات، Graph a وBigraph ab، الأول منهما يمثل الرسوم البيانية ذات الرؤوس الموسومة بقيم من النوع a، والثاني يمثل الرسوم البيانية ثنائية الأطراف ذات الرؤوس اليسرى المسمى بقيم من النوع a واليمين -القمم الجانبية تحمل قيم النوع ب.
هذه ليست أنواعًا من مكتبة Alga. لا يوجد لدى Alga تمثيل للرسوم البيانية الثنائية غير الموجهة. لقد صنعت أنواعًا مثل هذه من أجل الوضوح.
سنحتاج أيضًا إلى وظائف مساعدة بالتوقيعات التالية:
-- Список соседей данной вершины.
neighbours :: Ord a => a -> Graph a -> [a]
-- Построить двудольный граф по графу и функции, для каждой вершины
-- выдающей её долю и пометку в новой доле, игнорируя конфликтные рёбра.
toBipartiteWith :: (Ord a, Ord b, Ord c) => (a -> Either b c)
-> Graph a
-> Bigraph b c
-- Список вершин в графе
vertexList :: Ord a => Graph a -> [a]
Сигнатура функции, которую мы будем писать, выглядит так:
type OddCycle a = [a]
detectParts :: Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)من السهل أن نرى أنه إذا وجدنا حافة متعارضة أثناء بحث العمق أولاً، فإن الدورة الفردية تقع أعلى مكدس العودية. وبالتالي، لاستعادتها، نحتاج إلى قطع كل شيء بدءًا من مكدس التكرار وحتى أول ظهور للقمة الأخيرة.
نقوم بتنفيذ بحث العمق أولاً من خلال الحفاظ على مجموعة ترابطية من أرقام المشاركة لكل قمة. سيتم الحفاظ على مكدس العودية تلقائيًا من خلال تنفيذ فئة Functor للموناد التي اخترناها: سنحتاج فقط إلى وضع جميع القمم من المسار في النتيجة التي تم إرجاعها من الدالة العودية.
كانت فكرتي الأولى هي استخدام أي من الموناد، والذي يبدو أنه ينفذ بالضبط التأثيرات التي نحتاجها. كان التنفيذ الأول الذي كتبته قريبًا جدًا من هذا الخيار. في الواقع، كان لدي خمسة تطبيقات مختلفة في وقت ما واستقرت في النهاية على تطبيق آخر.
أولاً، نحتاج إلى الحفاظ على مجموعة ترابطية من معرفات المشاركة - وهذا شيء يتعلق بالحالة. ثانيًا، يجب أن نكون قادرين على التوقف عند اكتشاف الصراع. يمكن أن يكون هذا إما Monad لأي منهما، أو MonadPlus لـ ربما. والفرق الرئيسي هو أنه يمكن لأي منهما إرجاع قيمة إذا لم يتم إيقاف الحساب، وربما يُرجع معلومات حول هذا فقط في هذه الحالة. نظرًا لأننا لا نحتاج إلى قيمة منفصلة لتحقيق النجاح (فهي مخزنة بالفعل في الحالة)، فإننا نختار "ربما". وفي اللحظة التي نحتاج فيها إلى الجمع بين تأثيرات اثنين من المونادات، فإنها تخرج والتي تجمع بدقة بين هذه التأثيرات.
لماذا اخترت هذا النوع المعقد؟ سببان. أولاً، تبين أن التنفيذ مشابه جدًا للأمر الحتمي. ثانيًا، نحتاج إلى معالجة قيمة الإرجاع في حالة حدوث تعارض عند العودة من التكرار لاستعادة الحلقة الفردية، وهو أمر أسهل بكثير في ربما monad.
وهكذا نحصل على هذا التنفيذ.
{-# LANGUAGE ExplicitForAll #-}
{-# LANGUAGE ScopedTypeVariables #-}
data Part = LeftPart | RightPart
otherPart :: Part -> Part
otherPart LeftPart = RightPart
otherPart RightPart = LeftPart
type PartMap a = Map.Map a Part
type OddCycle a = [a]
toEither :: Ord a => PartMap a -> a -> Either a a
toEither m v = case fromJust (v `Map.lookup` m) of
LeftPart -> Left v
RightPart -> Right v
type PartMonad a = MaybeT (State (PartMap a)) [a]
detectParts :: forall a. Ord a => Graph a -> Either (OddCycle a) (Bigraph a a)
detectParts g = case runState (runMaybeT dfs) Map.empty of
(Just c, _) -> Left $ oddCycle c
(Nothing, m) -> Right $ toBipartiteWith (toEither m) g
where
inVertex :: Part -> a -> PartMonad a
inVertex p v = ((:) v) <$> do modify $ Map.insert v p
let q = otherPart p
msum [ onEdge q u | u <- neigbours v g ]
{-# INLINE onEdge #-}
onEdge :: Part -> a -> PartMonad a
onEdge p v = do m <- get
case v `Map.lookup` m of
Nothing -> inVertex p v
Just q -> do guard (q /= p)
return [v]
processVertex :: a -> PartMonad a
processVertex v = do m <- get
guard (v `Map.notMember` m)
inVertex LeftPart v
dfs :: PartMonad a
dfs = msum [ processVertex v | v <- vertexList g ]
oddCycle :: [a] -> [a]
oddCycle c = tail (dropWhile ((/=) last c) c)
كتلة المكان هي جوهر الخوارزمية. سأحاول شرح ما يحدث بداخله.
- إن inVertex هو جزء من بحث العمق الأول حيث نزور القمة للمرة الأولى. نقوم هنا بتعيين رقم مشاركة للقمة وتشغيل onEdge على جميع الجيران. وهذا أيضًا هو المكان الذي نستعيد فيه مكدس الاستدعاءات: إذا أعاد msum قيمة، فإننا ندفع vertex v هناك.
- onEdge هو الجزء الذي نزور فيه الحافة. يتم استدعاؤه مرتين لكل حافة. نحن هنا نتحقق مما إذا كانت القمة الموجودة على الجانب الآخر قد تمت زيارتها، ونقوم بزيارتها إذا لم يكن الأمر كذلك. إذا تمت زيارتها، فإننا نتحقق مما إذا كانت الحافة متعارضة. إذا كان الأمر كذلك، فإننا نعيد القيمة - الجزء العلوي من مكدس العودية، حيث سيتم بعد ذلك وضع جميع القمم الأخرى عند العودة.
- يتحقق ProcessVertex من كل قمة ما إذا كان قد تمت زيارتها أم لا، ويعمل في Vertex عليها إذا لم يكن الأمر كذلك.
- يقوم dfs بتشغيل عملية ProcessVertex على جميع القمم.
هذا كل شيء.
تاريخ كلمة INLINE
لم تكن كلمة INLINE موجودة في التطبيق الأول للخوارزمية، بل ظهرت لاحقًا. عندما حاولت العثور على تطبيق أفضل، وجدت أن الإصدار غير المضمن كان أبطأ بشكل ملحوظ في بعض الرسوم البيانية. مع الأخذ في الاعتبار أن الوظائف يجب أن تعمل بنفس الطريقة من الناحية الدلالية، فقد فاجأني هذا كثيرًا. والأمر الأكثر غرابة هو أنه على جهاز آخر بإصدار مختلف من GHC لم يكن هناك فرق ملحوظ.
بعد قضاء أسبوع في قراءة مخرجات GHC Core، تمكنت من حل المشكلة باستخدام سطر واحد من INLINE الصريح. في مرحلة ما بين GHC 8.4.4 وGHC 8.6.5، توقف المُحسِّن عن القيام بذلك من تلقاء نفسه.
لم أكن أتوقع أن أواجه مثل هذه الأوساخ في برمجة هاسكل. ومع ذلك، حتى اليوم، يرتكب المحسنون أحيانًا أخطاء، ومن واجبنا أن نقدم لهم التلميحات. على سبيل المثال، هنا نعلم أن الدالة يجب أن تكون مضمنة لأنها مضمنة في النسخة الأمرية، وهذا سبب لإعطاء المترجم تلميحًا.
ماذا حدث بعد ذلك؟
ثم قمت بتطبيق خوارزمية Hopcroft-Karp مع monads أخرى، وكانت تلك نهاية البرنامج.
بفضل Google Summer of Code، اكتسبت خبرة عملية في البرمجة الوظيفية، الأمر الذي لم يساعدني فقط في الحصول على تدريب في Jane Street في الصيف التالي (لست متأكدًا من مدى شهرة هذا المكان حتى بين جمهور هبر المطلعين، ولكنه أيضًا أحد من بين الأماكن القليلة التي يمكنك فيها الانخراط في البرمجة الوظيفية في الصيف)، ولكنه عرّفني أيضًا على العالم الرائع لتطبيق هذا النموذج عمليًا، والذي يختلف بشكل كبير عن تجربتي في اللغات التقليدية.
المصدر: www.habr.com