تابستان گذشته من در آن شرکت کردم - برنامه ای برای دانش آموزان از Google. هر سال، برگزارکنندگان چندین پروژه منبع باز را انتخاب می کنند، از جمله از سازمان های معروفی مانند и . گوگل از دانشجویان سراسر جهان دعوت می کند تا روی این پروژه ها کار کنند.
به عنوان یک شرکت کننده در Google Summer of Code 2019، پروژه ای را در کتابخانه انجام دادم با سازمان ، که در حال توسعه زبان Haskell - یکی از معروف ترین زبان های برنامه نویسی کاربردی است. جلبک یک کتابخانه است که نشان می دهد نمایش برای نمودارها در Haskell. استفاده می شود، به عنوان مثال، در - یک کتابخانه Github که درخت های معنایی، نمودارهای فراخوانی و وابستگی را بر اساس کد ایجاد می کند و می تواند آنها را با هم مقایسه کند. پروژه من اضافه کردن یک نمایش ایمن برای نمودارهای دوبخشی و الگوریتم هایی برای آن نمایش بود.
در این پست در مورد پیاده سازی الگوریتمی برای بررسی یک نمودار برای دوبخشی بودن در Haskell صحبت خواهم کرد. اگرچه این الگوریتم یکی از اساسی‌ترین الگوریتم‌ها است، پیاده‌سازی آن به زیبایی در یک سبک عملکردی چندین بار تکرار شد و به کار بسیار زیادی نیاز داشت. در نتیجه، من روی یک پیاده سازی با ترانسفورماتورهای موناد قرار گرفتم.
درباره خودم
نام من واسیلی آلفروف است، من دانشجوی سال چهارم در HSE سنت پترزبورگ هستم. قبلا در وبلاگ نوشتم и . در حال حاضر در دوره کارآموزی هستم در نروژ، جایی که من در حال کار بر روی رویکردهای مشکل هستم . علایق من شامل الگوریتم های پارامتری و برنامه نویسی تابعی است.
درباره اجرای الگوریتم
پیش گفتار
دانشجویان شرکت کننده در این برنامه به شدت تشویق می شوند که به وبلاگ بپردازند. آنها برای من بستری برای وبلاگ فراهم کردند . این مقاله یک ترجمه است نوشته شده توسط من در ماه ژوئیه به زبان انگلیسی، با مقدمه ای کوتاه.
Pull Request با کد مورد نظر را می توان یافت .
می توانید نتایج کار من را بخوانید (به زبان انگلیسی) .
این پست برای آشنایی خواننده با مفاهیم اولیه در برنامه نویسی تابعی در نظر گرفته شده است، اگرچه من سعی می کنم در زمان مناسب تمام اصطلاحات استفاده شده را یادآوری کنم.
بررسی نمودارها برای دوبخشی بودن
الگوریتمی برای بررسی دو بخشی بودن نمودار معمولاً در درس الگوریتم ها به عنوان یکی از ساده ترین الگوریتم های گراف ارائه می شود. ایده او ساده است: ابتدا به نحوی رئوس را در سهم چپ یا راست قرار می دهیم، و هنگامی که یک یال متضاد پیدا می شود، ادعا می کنیم که نمودار دو بخشی نیست.
کمی جزئیات بیشتر: ابتدا مقداری راس در قسمت سمت چپ قرار می دهیم. بدیهی است که همه همسایگان این راس باید در لوب سمت راست قرار گیرند. علاوه بر این، همه همسایگان همسایگان این راس باید در لوب چپ قرار داشته باشند و غیره. تا زمانی که هنوز رئوس هایی در جزء متصل رئوس که با آن شروع کرده ایم وجود دارد که همسایه هایی را به آن اختصاص نداده ایم، به تخصیص اشتراک به رئوس ادامه می دهیم. سپس این عمل را برای تمام اجزای متصل تکرار می کنیم.
اگر یک لبه بین رئوس وجود داشته باشد که در یک پارتیشن قرار می‌گیرند، یافتن یک چرخه فرد در نمودار دشوار نیست، که به طور گسترده (و کاملاً واضح است) در یک گراف دو بخشی غیرممکن است. در غیر این صورت یک پارتیشن صحیح داریم، یعنی گراف دو بخشی است.
به طور معمول، این الگوریتم با استفاده از یا . در زبان‌های امری، جستجوی عمقی معمولاً استفاده می‌شود، زیرا کمی ساده‌تر است و به ساختارهای داده اضافی نیاز ندارد. من همچنین جستجوی ابتدا عمق را انتخاب کردم زیرا سنتی تر است.
بدین ترتیب به طرح زیر رسیدیم. رئوس نمودار را با استفاده از جست‌وجوی عمقی طی می‌کنیم و اشتراک‌هایی را به آنها اختصاص می‌دهیم، و با حرکت در لبه، تعداد سهم را تغییر می‌دهیم. اگر بخواهیم سهمی را به رأسی اختصاص دهیم که قبلاً سهمی دارد، می‌توانیم با خیال راحت بگوییم که نمودار دو بخشی نیست. لحظه ای که به همه رئوس یک اشتراک اختصاص داده می شود و ما به تمام لبه ها نگاه می کنیم، یک پارتیشن خوب داریم.
خلوص محاسبات
در Haskell فرض می کنیم که همه محاسبات انجام می شود تمیز. با این حال، اگر واقعاً چنین بود، ما هیچ راهی برای چاپ چیزی روی صفحه نمایش نداشتیم. اصلا، پاک کن محاسبات آنقدر تنبل هستند که یکی وجود ندارد تمیز دلایلی برای محاسبه چیزی تمام محاسباتی که در برنامه اتفاق می افتد به نحوی مجبور می شوند "نجس" monad IO.
مونادها راهی برای نمایش محاسبات هستند اثرات در هاسکل توضیح نحوه کار آنها خارج از حوصله این پست است. توضیحات خوب و واضح را می توان به زبان انگلیسی خواند .
در اینجا می‌خواهم به این نکته اشاره کنم که در حالی که برخی از مونادها مانند IO از طریق جادوی کامپایلر پیاده‌سازی می‌شوند، تقریباً بقیه در نرم‌افزار پیاده‌سازی می‌شوند و تمامی محاسبات در آنها خالص هستند.
افکت های زیادی وجود دارد و هر کدام موناد خاص خود را دارند. این یک نظریه بسیار قوی و زیبا است: همه مونادها یک رابط را پیاده سازی می کنند. ما در مورد سه موناد زیر صحبت خواهیم کرد:
- یا ea محاسبه‌ای است که مقداری از نوع a را برمی‌گرداند یا استثنایی از نوع e را ایجاد می‌کند. رفتار این موناد بسیار شبیه به کار با استثنا در زبان های امری است: خطاها می توانند کشف شوند یا منتقل شوند. تفاوت اصلی این است که موناد کاملاً منطقی در کتابخانه استاندارد Haskell پیاده سازی شده است، در حالی که زبان های ضروری معمولاً از مکانیسم های سیستم عامل استفاده می کنند.
- حالت sa محاسباتی است که مقداری از نوع a را برمی گرداند و به حالت قابل تغییر نوع s دسترسی دارد.
- شاید یک. ممکن است موناد محاسبه‌ای را بیان می‌کند که می‌تواند در هر زمان با برگرداندن Nothing قطع شود. با این حال، ما در مورد پیاده سازی کلاس MonadPlus برای نوع Maybe صحبت خواهیم کرد که اثر معکوس را بیان می کند: این یک محاسبه است که می تواند در هر زمان با برگرداندن یک مقدار خاص قطع شود.
پیاده سازی الگوریتم
ما دو نوع داده داریم، Graph a و Bigraph ab، که اولی نمودارهایی با رئوس برچسب‌گذاری شده با مقادیر نوع a را نشان می‌دهد، و دومی نشان‌دهنده گراف‌های دوبخشی با رئوس سمت چپ هستند که با مقادیر نوع a و راست برچسب‌گذاری شده‌اند. - رئوس سمتی که با مقادیر نوع b برچسب گذاری شده اند.
اینها انواعی از کتابخانه 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 موناد انتخابی ما حفظ می شود: ما فقط باید تمام رئوس مسیر را در نتیجه بازگشتی از تابع بازگشتی قرار دهیم.
اولین ایده من استفاده از Either monad بود که به نظر می‌رسد دقیقاً افکت‌هایی را که ما نیاز داریم پیاده‌سازی می‌کند. اولین پیاده سازی که نوشتم خیلی به این گزینه نزدیک بود. در واقع، من در یک نقطه پنج پیاده سازی مختلف داشتم و در نهایت روی یکی دیگر مستقر شدم.
اول، ما باید یک آرایه انجمنی از شناسه‌های سهام را حفظ کنیم - این چیزی در مورد State است. ثانیاً، ما باید بتوانیم زمانی که یک درگیری شناسایی می شود، متوقف شویم. این می تواند موناد برای هر یک یا موناد پلاس برای شاید باشد. تفاوت اصلی این است که اگر محاسبه متوقف نشده باشد هر دو می توانند مقداری را برگردانند و شاید در این مورد فقط اطلاعات مربوط به آن را برمی گرداند. از آنجایی که برای موفقیت به یک مقدار جداگانه نیاز نداریم (این مقدار قبلاً در State ذخیره شده است)، شاید گزینه ممکن را انتخاب می کنیم. و در لحظه ای که ما نیاز به ترکیب اثرات دو موناد داریم، آنها بیرون می آیند ، که دقیقاً این اثرات را با هم ترکیب می کنند.
چرا چنین نوع پیچیده ای را انتخاب کردم؟ دو دلیل اولاً، به نظر می رسد که پیاده سازی بسیار شبیه به امری است. دوم، ما باید مقدار بازگشتی را در صورت تداخل هنگام بازگشت از بازگشت دستکاری کنیم تا حلقه فرد را بازیابی کنیم، که انجام این کار در موناد Maybe بسیار ساده‌تر است.
بنابراین ما این پیاده سازی را دریافت می کنیم.
{-# 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)
بلوک Where هسته اصلی الگوریتم است. من سعی خواهم کرد آنچه را که در داخل آن اتفاق می افتد توضیح دهم.
- inVertex بخشی از جستجوی عمقی است که برای اولین بار از راس بازدید می کنیم. در اینجا یک شماره اشتراک به راس اختصاص می دهیم و onEdge را روی همه همسایگان اجرا می کنیم. همچنین در اینجاست که پشته تماس را بازیابی می کنیم: اگر msum مقداری را برگرداند، راس v را به آنجا فشار می دهیم.
- onEdge قسمتی است که از لبه بازدید می کنیم. برای هر لبه دو بار فراخوانی می شود. در اینجا بررسی می کنیم که آیا راس طرف مقابل بازدید شده است یا خیر، و در غیر این صورت از آن بازدید می کنیم. در صورت بازدید، بررسی می کنیم که آیا لبه تداخل دارد یا خیر. اگر اینطور باشد، مقدار را برمی گردانیم - همان بالای پشته بازگشتی، جایی که تمام رئوس دیگر پس از بازگشت قرار می گیرند.
- processVertex برای هر رأس بررسی می کند که آیا بازدید شده است یا خیر و در غیر این صورت inVertex را روی آن اجرا می کند.
- dfs روی تمام رئوس، processVertex را اجرا می کند.
که تمام است.
تاریخچه کلمه INLINE
کلمه INLINE در اولین اجرای الگوریتم نبود، بعداً ظاهر شد. وقتی سعی کردم پیاده سازی بهتری پیدا کنم، متوجه شدم که نسخه غیر INLINE در برخی از نمودارها به طور قابل توجهی کندتر است. با توجه به اینکه از نظر معنایی توابع باید یکسان عمل کنند، این من را بسیار شگفت زده کرد. حتی عجیب تر، در دستگاه دیگری با نسخه متفاوت GHC تفاوت قابل توجهی وجود نداشت.
پس از صرف یک هفته برای خواندن خروجی GHC Core، توانستم با یک خط INLINE صریح مشکل را برطرف کنم. در نقطه ای بین GHC 8.4.4 و GHC 8.6.5، بهینه ساز این کار را به تنهایی متوقف کرد.
من انتظار نداشتم در برنامه نویسی Haskell با چنین کثیفی روبرو شوم. با این حال، حتی امروزه، بهینه‌سازها گاهی اوقات اشتباه می‌کنند و وظیفه ما این است که به آنها نکاتی را ارائه دهیم. به عنوان مثال، در اینجا می دانیم که تابع باید درون خطی باشد زیرا در نسخه دستوری درون خطی شده است و این دلیلی است برای ارائه یک اشاره به کامپایلر.
چه اتفاقی افتاد؟
سپس الگوریتم هاپکرافت-کارپ را با مونادهای دیگر پیاده‌سازی کردم و این پایان برنامه بود.
به لطف Google Summer of Code، تجربه عملی در برنامه نویسی عملکردی به دست آوردم، که نه تنها به من کمک کرد تابستان سال بعد در خیابان جین کارآموزی کنم (مطمئن نیستم که این مکان حتی در بین مخاطبان آگاه Habr چقدر شناخته شده است، اما یکی از آنهاست. از معدود مواردی که می توانید تابستان را در برنامه نویسی کاربردی شرکت کنید)، اما همچنین مرا با دنیای شگفت انگیز به کارگیری این پارادایم در عمل آشنا کرد، که به طور قابل توجهی با تجربه من در زبان های سنتی متفاوت است.
منبع: www.habr.com