O'tgan yozda men qatnashganman - Google'dan talabalar uchun dastur. Tashkilotchilar har yili bir nechta Ochiq manba loyihalarini, shu jumladan taniqli tashkilotlardan tanlab olishadi и . Google butun dunyodan talabalarni ushbu loyihalar ustida ishlashga taklif qiladi.
Google Summer of Code 2019 ishtirokchisi sifatida men kutubxonada loyihani amalga oshirdim tashkilot bilan , Haskell tilini rivojlantirmoqda - eng mashhur funktsional dasturlash tillaridan biri. Alga - ifodalovchi kutubxona Haskellda grafiklar uchun tasvir. U, masalan, ichida ishlatiladi — kod asosida semantik daraxtlar, chaqiruv va qaramlik grafiklarini yaratuvchi va ularni solishtirishi mumkin bo'lgan Github kutubxonasi. Mening loyiham ikki tomonlama grafiklar va ushbu taqdimot uchun algoritmlar uchun xavfsiz turdagi tasvirni qo'shish edi.
Ushbu postda men Xaskellda ikki tomonlamalik grafigini tekshirish algoritmini amalga oshirishim haqida gapiraman. Algoritm eng asosiylaridan biri bo'lsa-da, uni funktsional uslubda chiroyli tarzda amalga oshirish men uchun bir nechta iteratsiyalarni talab qildi va juda ko'p mehnat talab qildi. Natijada, men monad transformatorlari bilan amalga oshirishga qaror qildim.
Men haqimda
Mening ismim Vasiliy Alferov, men Sankt-Peterburg HSE ning to'rtinchi kurs talabasiman. Avvalroq blogda yozgan edim и . Hozir men stajirovkadaman Norvegiyada, men muammoga yondashuvlar ustida ishlayapman . Mening qiziqishlarimga parametrlashtirilgan algoritmlar va funktsional dasturlash kiradi.
Algoritmni amalga oshirish haqida
muqaddima
Dasturda ishtirok etayotgan talabalarga blog yuritish tavsiya etiladi. Ular menga blog uchun platforma taqdim etishdi . Ushbu maqola tarjimadir , u erda iyul oyida men tomonidan ingliz tilida qisqa so'zboshi bilan yozilgan.
Ko'rib chiqilayotgan kod bilan Pull so'rovini topish mumkin .
Mening ishim natijalari haqida o'qishingiz mumkin (ingliz tilida) .
Ushbu post o'quvchini funktsional dasturlashning asosiy tushunchalari bilan tanishtirish uchun mo'ljallangan, garchi vaqti kelganda ishlatiladigan barcha atamalarni eslashga harakat qilaman.
Grafiklarni ikki tomonlamalik uchun tekshirish
Grafikning ikki tomonlamaligini tekshirish algoritmi, odatda, eng oddiy grafik algoritmlaridan biri sifatida algoritmlar kursida beriladi. Uning fikri to'g'ridan-to'g'ri: birinchi navbatda biz chap yoki o'ng ulushga qandaydir tarzda cho'qqilarni qo'yamiz va qarama-qarshi tomon topilsa, biz grafik ikki tomonlama emasligini tasdiqlaymiz.
Bir oz ko'proq tafsilot: avval biz chap qismga bir oz cho'qqi qo'yamiz. Shubhasiz, bu tepalikning barcha qo'shnilari o'ng lobda yotishi kerak. Bundan tashqari, bu vertexning qo'shnilarining barcha qo'shnilari chap lobda yotishi kerak va hokazo. Biz boshlagan cho'qqining bog'langan komponentida qo'shnilarni belgilamagan cho'qqilar mavjud ekan, biz cho'qqilarga ulushlarni belgilashda davom etamiz. Keyin barcha ulangan komponentlar uchun ushbu amalni takrorlaymiz.
Agar bir xil bo'limga tushadigan cho'qqilar orasida chekka mavjud bo'lsa, grafikda g'alati tsiklni topish qiyin emas, bu ikki tomonlama grafikda keng tarqalgan (va aniq) mumkin emas. Aks holda, bizda to'g'ri bo'lim bor, ya'ni grafik ikki tomonlama.
Odatda, bu algoritm yordamida amalga oshiriladi yoki . Imperativ tillarda, odatda, bir oz soddaroq va qo'shimcha ma'lumotlar tuzilmalarini talab qilmagani uchun chuqurlikdan birinchi qidiruv qo'llaniladi. Men chuqurroq qidiruvni ham tanladim, chunki u an'anaviyroq.
Shunday qilib, biz quyidagi sxemaga keldik. Biz grafikning cho'qqilarini chuqurlik bo'yicha birinchi qidiruv yordamida kesib o'tamiz va ularga ulushlarni tayinlaymiz, chekka bo'ylab harakatlanayotganda ulush sonini o'zgartiramiz. Agar biz ulush tayinlangan cho'qqiga ulushni belgilashga harakat qilsak, biz ishonch bilan aytishimiz mumkinki, grafik ikki tomonlama emas. Barcha cho'qqilarga ulush berilganda va biz barcha qirralarni ko'rib chiqdik, bizda yaxshi bo'lim bor.
Hisob-kitoblarning tozaligi
Haskellda biz barcha hisob-kitoblarni shunday deb hisoblaymiz toza. Biroq, agar bu haqiqatan ham shunday bo'lganida, ekranga hech narsa chop etishning imkoni bo'lmaydi. Umuman, toza hisob-kitoblar shunchalik dangasaki, bittasi yo'q toza biror narsani hisoblash uchun sabablar. Dasturda sodir bo'lgan barcha hisob-kitoblar qandaydir tarzda majburan amalga oshiriladi "nopok" monad IO.
Monadlar hisob-kitoblarni ifodalash usulidir effektlar Haskell shahrida. Ularning qanday ishlashini tushuntirish bu post doirasidan tashqarida. Yaxshi va aniq tavsifni ingliz tilida o'qish mumkin .
Bu erda shuni ta'kidlashni istardimki, ba'zi monadlar, masalan, IO, kompilyator sehrlari orqali amalga oshirilgan bo'lsa, deyarli barcha boshqalar dasturiy ta'minotda amalga oshiriladi va ulardagi barcha hisoblar sof.
Effektlar juda ko'p va ularning har biri o'z monadiga ega. Bu juda kuchli va chiroyli nazariya: barcha monadlar bir xil interfeysni amalga oshiradilar. Biz quyidagi uchta monad haqida gapiramiz:
- Yoki ea a tipidagi qiymatni qaytaradigan yoki e tipidagi istisnolarni chiqaradigan hisob-kitobdir. Ushbu monadning xatti-harakati imperativ tillardagi istisnolarni boshqarishga juda o'xshaydi: xatolar ushlanishi yoki uzatilishi mumkin. Asosiy farq shundaki, monad to'liq mantiqiy ravishda Haskelldagi standart kutubxonada amalga oshiriladi, imperativ tillar odatda operatsion tizim mexanizmlaridan foydalanadi.
- Sa holati a tipidagi qiymatni qaytaradigan va s tipidagi o'zgaruvchan holatga kirish huquqiga ega hisob-kitobdir.
- Balki a. Balki monadasi istalgan vaqtda Hech narsa qaytarish orqali to'xtatilishi mumkin bo'lgan hisoblashni ifodalaydi. Biroq, qarama-qarshi effektni ifodalovchi Balki turi uchun MonadPlus sinfini amalga oshirish haqida gapiramiz: bu ma'lum bir qiymatni qaytarish orqali istalgan vaqtda to'xtatilishi mumkin bo'lgan hisob.
Algoritmni amalga oshirish
Bizda ikkita ma'lumot turi mavjud, Graph a va Bigraph ab, ulardan birinchisi a tipidagi qiymatlar bilan belgilangan uchlari bo'lgan grafiklarni, ikkinchisi esa a va o'ng tipidagi qiymatlar bilan belgilangan chap tomonli uchlari bo'lgan ikki tomonlama grafiklarni ifodalaydi. -b tipidagi qiymatlar bilan belgilangan yon cho'qqilar.
Bular Alga kutubxonasidagi turlar emas. Alga yo'naltirilmagan ikki tomonlama grafiklar uchun tasvirga ega emas. Aniqlik uchun men shunga o'xshash turlarni qildim.
Shuningdek, bizga quyidagi imzolar bilan yordamchi funksiyalar kerak bo‘ladi:
-- Список соседей данной вершины.
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)Ko'rish oson, agar chuqurlikdagi birinchi qidiruv paytida biz qarama-qarshi tomonni topsak, g'alati tsikl rekursiya stekining tepasida joylashgan. Shunday qilib, uni qayta tiklash uchun biz rekursiya to'plamidan oxirgi cho'qqining birinchi paydo bo'lishigacha bo'lgan hamma narsani kesib tashlashimiz kerak.
Biz har bir cho'qqi uchun ulush raqamlarining assotsiativ qatorini saqlab, birinchi navbatda chuqur qidiruvni amalga oshiramiz. Biz tanlagan monadning Functor sinfini amalga oshirish orqali rekursion stek avtomatik tarzda saqlanadi: biz faqat rekursiv funktsiyadan qaytarilgan natijaga yo'lning barcha uchlarini qo'yishimiz kerak bo'ladi.
Mening birinchi g'oyam "Either monad" dan foydalanish edi, bu bizga kerakli effektlarni amalga oshiradi. Men yozgan birinchi dastur bu variantga juda yaqin edi. Aslida, men bir vaqtning o'zida besh xil dasturga ega bo'ldim va oxir-oqibat boshqasiga qaror qildim.
Birinchidan, biz ulush identifikatorlarining assotsiativ qatorini saqlashimiz kerak - bu Davlatga tegishli. Ikkinchidan, mojaro aniqlanganda biz to'xtashimiz kerak. Bu "Yoki" uchun "Monad" yoki "Balki" uchun MonadPlus bo'lishi mumkin. Asosiy farq shundaki, agar hisoblash to'xtatilmagan bo'lsa, Yoki bir qiymatni qaytarishi mumkin va Balki bu holatda faqat bu haqda ma'lumotni qaytaradi. Muvaffaqiyat uchun alohida qiymat kerak emasligi sababli (u allaqachon shtatda saqlangan), biz Balki ni tanlaymiz. Va ikkita monadning ta'sirini birlashtirishimiz kerak bo'lgan paytda, ular paydo bo'ladi , bu ta'sirlarni aniq birlashtiradi.
Nega men bunday murakkab turni tanladim? Ikkita sabab. Birinchidan, amalga oshirish imperativga juda o'xshash bo'lib chiqadi. Ikkinchidan, toq siklni tiklash uchun rekursiyadan qaytganimizda ziddiyat yuzaga kelganda qaytish qiymatini manipulyatsiya qilishimiz kerak, bu may monadida qilish ancha oson.
Shunday qilib, biz ushbu amaliyotni qo'lga kiritamiz.
{-# 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)
Qaerda blok algoritmning yadrosidir. Men uning ichida nima bo'layotganini tushuntirishga harakat qilaman.
- inVertex - bu cho'qqiga birinchi marta tashrif buyuradigan chuqurlikdagi birinchi qidiruv qismi. Bu erda biz tepaga ulush raqamini tayinlaymiz va barcha qo'shnilarda onEdge-ni ishga tushiramiz. Bu erda biz qo'ng'iroqlar to'plamini qayta tiklaymiz: agar msum qiymatni qaytarsa, biz u erga v vertexini suramiz.
- onEdge - biz chekkaga tashrif buyuradigan qism. Har bir chekka uchun ikki marta chaqiriladi. Bu erda biz boshqa tarafdagi tepaga tashrif buyurilganligini tekshiramiz va agar bo'lmasa, tashrif buyuramiz. Agar tashrif buyurilgan bo'lsa, biz chekkaning ziddiyatli yoki yo'qligini tekshiramiz. Agar shunday bo'lsa, biz qiymatni qaytaramiz - rekursiya to'plamining eng yuqori qismi, bu erda boshqa barcha tepaliklar qaytib kelganda joylashtiriladi.
- processVertex har bir tepaga tashrif buyurilganligini tekshiradi va agar bo'lmasa, inVertex-ni ishga tushiradi.
- dfs barcha uchlarda processVertex-ni ishga tushiradi.
Ana xolos.
INLINE so'zining tarixi
INLINE so'zi algoritmning birinchi amalga oshirilishida bo'lmagan, u keyinroq paydo bo'lgan. Yaxshiroq dasturni topishga harakat qilganimda, ba'zi grafiklarda INLINE bo'lmagan versiya sezilarli darajada sekinroq ekanligini aniqladim. Semantik jihatdan funktsiyalar bir xil ishlashi kerakligini hisobga olsak, bu meni juda hayratda qoldirdi. Hatto g'alati, GHC ning boshqa versiyasiga ega bo'lgan boshqa mashinada sezilarli farq yo'q edi.
GHC Core chiqishini o'qishga bir hafta sarflaganimdan so'ng, men muammoni bir qator aniq INLINE bilan hal qila oldim. GHC 8.4.4 va GHC 8.6.5 oralig'ida optimallashtiruvchi buni o'z-o'zidan to'xtatdi.
Men Haskell dasturlashda bunday axloqsizlikka duch kelishni kutmagan edim. Biroq, bugungi kunda ham optimallashtiruvchilar ba'zan xato qilishadi va ularga maslahat berish bizning vazifamizdir. Misol uchun, bu erda funktsiya inline bo'lishi kerakligini bilamiz, chunki u imperativ versiyada joylashtirilgan va bu kompilyatorga maslahat berish uchun sababdir.
Keyin nima bo'ldi?
Keyin men Hopcroft-Karp algoritmini boshqa monadlar bilan amalga oshirdim va bu dasturning oxiri edi.
Google Summer of Code tufayli men funktsional dasturlash bo‘yicha amaliy tajribaga ega bo‘ldim, bu nafaqat keyingi yozda Jeyn-stritda amaliyot o‘tashimga yordam berdi (bu joy hatto Xabrning bilimdon auditoriyasi orasida qanchalik mashhur ekanligiga amin emasman, lekin u bitta Siz yozda funktsional dasturlash bilan shug'ullanishingiz mumkin bo'lgan bir nechtasi), balki meni ushbu paradigmani amaliyotda qo'llashning ajoyib dunyosi bilan tanishtirdi, bu mening an'anaviy tillardagi tajribamdan sezilarli darajada farq qiladi.
Manba: www.habr.com