Өткен жазда мен қатыстым - Google студенттеріне арналған бағдарлама. Ұйымдастырушылар жыл сайын бірнеше Ашық бастапқы жобаларды, соның ішінде танымал ұйымдарды таңдайды и . Google бүкіл әлемдегі студенттерді осы жобалармен жұмыс істеуге шақырады.
Google Summer of Code 2019 бағдарламасына қатысушы ретінде мен кітапханада жоба жасадым ұйыммен , Хаскелл тілін дамытатын – ең танымал функционалдық бағдарламалау тілдерінің бірі. Алға – бейнелейтін кітапхана Хаскеллде графиктер үшін ұсыну. Ол, мысалы, қолданылады — код негізінде семантикалық ағаштарды, шақыру және тәуелділік графиктерін құрастыратын және оларды салыстыра алатын Github кітапханасы. Менің жобам екі жақты графиктер мен осы көрсетілімге арналған алгоритмдер үшін қауіпсіз типті ұсынуды қосу болды.
Бұл постта мен Хаскеллдегі екі жақтылықтың графигін тексеру алгоритмін енгізу туралы айтатын боламын. Алгоритм ең қарапайымдардың бірі болса да, оны функционалды стильде әдемі енгізу маған бірнеше итерацияны қажет етті және өте көп жұмысты қажет етті. Нәтижесінде мен монадалық трансформаторлармен іске асыру туралы шешім қабылдадым.
Өзі жайлы
Менің атым Василий Алферов, мен Санкт-Петербургтегі ҚОҚМ төртінші курс студентімін. Бұрын блогымда жазған болатынмын и . Дәл қазір мен стажировкадамын Норвегияда, мен проблеманы шешудің тәсілдерімен жұмыс істеп жатырмын . Менің қызығушылықтарыма параметрленген алгоритмдер мен функционалды бағдарламалау кіреді.
Алгоритмнің орындалуы туралы
Алғы сөз
Бағдарламаға қатысатын студенттерге блог жазуға шақырылады. Олар маған блог платформасын ұсынды . Бұл мақала аударма болып табылады , мен сол жерде шілде айында ағылшын тілінде қысқаша кіріспемен жазған.
Қарастырылып отырған кодпен сұрауды табуға болады .
Сіз менің жұмысымның нәтижелері туралы оқи аласыз (ағылшын тілінде) .
Бұл пост оқырман функционалдық бағдарламалаудың негізгі ұғымдарымен таныс деп болжайды, дегенмен мен уақыты келгенде қолданылатын барлық терминдерді еске түсіруге тырысамын.
Графиктердің екі жақтылығын тексеру
Графиктің екі жақтылығын тексеру алгоритмі әдетте ең қарапайым графикалық алгоритмдердің бірі ретінде алгоритмдер курсында беріледі. Оның идеясы қарапайым: алдымен сол немесе оң үлеске төбелерді қоямыз, ал қайшылықты жиек табылған кезде, біз графиктің екі жақты емес екенін растаймыз.
Кішкене егжей-тегжейлі: алдымен сол жақ бөлікке кейбір шыңдарды қоямыз. Әлбетте, бұл шыңның барлық көршілері оң жақ лобта жатуы керек. Әрі қарай, осы шыңның көршілерінің барлық көршілері сол жақ лобта жатуы керек және т.б. Біз бастаған төбенің қосылған құрамдас бөлігінде көршілерді тағайындамаған шыңдар әлі де болса, біз төбелерге үлестерді тағайындауды жалғастырамыз. Содан кейін бұл әрекетті барлық қосылған компоненттер үшін қайталаймыз.
Егер бір бөлімге түсетін төбелер арасында жиек болса, екі жақты графикте кеңінен белгілі (және анық) мүмкін емес графта тақ циклді табу қиын емес. Әйтпесе, бізде дұрыс бөлім бар, яғни график екі жақты.
Әдетте, бұл алгоритм пайдалану арқылы жүзеге асырылады немесе . Императивті тілдерде, әдетте, бірінші тереңдікте іздеу қолданылады, себебі ол сәл қарапайым және қосымша деректер құрылымдарын қажет етпейді. Мен де тереңірек іздеуді таңдадым, себебі бұл дәстүрлі.
Осылайша, біз келесі схемаға келдік. Біз тереңдік бойынша бірінші іздеуді пайдаланып графиктің шыңдарын кесіп өтеміз және оларға үлестерді тағайындаймыз, жиек бойымен жылжыған кезде үлестің санын өзгертеміз. Егер үлесті тағайындалған шыңға үлесті тағайындауға тырыссақ, график екі жақты емес деп сенімді түрде айта аламыз. Барлық шыңдарға үлес тағайындалған кезде және біз барлық жиектерді қараған кезде, бізде жақсы бөлім бар.
Есептердің тазалығы
Хаскеллде біз барлық есептеулер бар деп есептейміз таза. Алайда, егер бұл шынымен де солай болса, экранға ештеңе басып шығаруға мүмкіндік болмас еді. Мүлде, таза есептеулер соншалықты жалқау, біреуі жоқ таза бір нәрсені есептеудің себептері. Бағдарламада орын алатын барлық есептеулер қандай да бір түрде мәжбүрлі түрде орындалады «таза емес» monad IO.
Монадалар - есептеулерді көрсету тәсілі әсерлері Хаскеллде. Олардың қалай жұмыс істейтінін түсіндіру бұл жазбаның ауқымынан тыс. Жақсы және түсінікті сипаттаманы ағылшын тілінде оқуға болады .
Бұл жерде мен кейбір монадтар, мысалы, IO, компилятор магиясы арқылы жүзеге асырылғанымен, қалғандарының барлығы дерлік бағдарламалық жасақтамада жүзеге асырылатынын және олардағы барлық есептеулер таза екенін атап өткім келеді.
Эффектілер өте көп және әрқайсысының өз монадасы бар. Бұл өте күшті және әдемі теория: барлық монадалар бірдей интерфейсті жүзеге асырады. Біз келесі үш монада туралы сөйлесетін боламыз:
- Немесе ea — a түрінің мәнін қайтаратын немесе e түріндегі ерекше жағдайды шығаратын есептеу. Бұл монаданың әрекеті императивті тілдердегі ерекше жағдайларды өңдеуге өте ұқсас: қателерді ұстауға немесе жіберуге болады. Негізгі айырмашылығы, монад Хаскеллдегі стандартты кітапханада толығымен логикалық түрде жүзеге асырылады, ал императивті тілдер әдетте операциялық жүйе механизмдерін пайдаланады.
- Күй sa – a түрінің мәнін қайтаратын және s түрінің өзгермелі күйіне рұқсаты бар есептеу.
- Мүмкін а. Мүмкін монада Ештеңе қайтару арқылы кез келген уақытта үзілуі мүмкін есептеуді білдіреді. Дегенмен, біз қарама-қарсы әсерді білдіретін Мүмкін түрі үшін MonadPlus класын жүзеге асыру туралы айтатын боламыз: бұл белгілі бір мәнді қайтару арқылы кез келген уақытта үзілуі мүмкін есептеу.
Алгоритмді жүзеге асыру
Бізде екі деректер түрі бар, Graph a және Bigraph ab, олардың біріншісі a түріндегі мәндермен белгіленген шыңдары бар графиктерді, ал екіншісі a және оң типті мәндермен белгіленген сол жақ төбелері бар екі жақты графиктерді көрсетеді. - б түріндегі мәндермен белгіленген бүйірлік шыңдар.
Бұл Алға кітапханасындағы түрлер емес. Алғаның бағытталмаған екі жақты графиктер үшін ұсынуы жоқ. Түсінікті болу үшін мен осындай түрлерді жасадым.
Сондай-ақ бізге келесі қолтаңбалары бар көмекші функциялар қажет болады:
-- Список соседей данной вершины.
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 пайдалану болды, ол бізге қажет әсерлерді жүзеге асыратын сияқты. Мен жазған бірінші іске асыру осы опцияға өте жақын болды. Шындығында, менде бір сәтте бес түрлі іске асыру болды және соңында екіншісіне тоқталды.
Біріншіден, біз үлес идентификаторларының ассоциативті массивін сақтауымыз керек - бұл мемлекетке қатысты нәрсе. Екіншіден, жанжал анықталған кезде тоқтай білуіміз керек. Бұл «Не» үшін Monad немесе «Мүмкін» үшін MonadPlus болуы мүмкін. Негізгі айырмашылық мынада: Ейде бір мәнді қайтара алады, егер есептеу тоқтатылмаған болса және Мүмкін бұл жағдайда тек осы туралы ақпаратты қайтарады. Сәттілік үшін бөлек мән қажет емес болғандықтан (ол күйде сақталған), біз Мүмкін параметрін таңдаймыз. Ал екі монаданың әсерлерін біріктіру қажет болған сәтте олар шығады , бұл әсерлерді дәл біріктіреді.
Неліктен мен мұндай күрделі типті таңдадым? Екі себеп. Біріншіден, іске асыру императивтіге өте ұқсас болып шығады. Екіншіден, тақ циклді қалпына келтіру үшін рекурсиядан қайтып оралған кезде қайшылық болған жағдайда қайтару мәнін басқару керек, бұл Мүмкін монадасында орындау әлдеқайда оңай.
Осылайша біз бұл іске асыруды аламыз.
{-# 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 мәнді қайтарса, онда біз v шыңын басамыз.
- onEdge - біз жиекке баратын бөлік. Ол әр жиек үшін екі рет шақырылады. Мұнда біз екінші жағындағы шыңның бар-жоғын тексереміз, егер жоқ болса, оған барамыз. Егер барған болсаңыз, біз жиектің қайшы келетінін тексереміз. Егер солай болса, біз мәнді қайтарамыз - рекурсиялық стектің ең жоғарғы жағы, онда барлық басқа шыңдар қайтарылған кезде орналастырылады.
- processVertex әрбір шыңның барған-бармағанын тексереді және егер жоқ болса, онда inVertex іске қосады.
- dfs барлық шыңдарда processVertex іске қосады.
Бар болғаны.
INLINE сөзінің шығу тарихы
INLINE сөзі алгоритмнің бірінші іске асырылуында болған жоқ, ол кейінірек пайда болды. Мен жақсырақ енгізуді табуға тырысқанда, кейбір графиктерде INLINE емес нұсқасы айтарлықтай баяу екенін байқадым. Семантикалық тұрғыдан функциялар бірдей жұмыс істеуі керек екенін ескере отырып, бұл мені қатты таң қалдырды. Тіпті бейтаныс, GHC-тің басқа нұсқасы бар басқа машинада айтарлықтай айырмашылық болмады.
GHC Core шығысын оқуға бір апта жұмсағаннан кейін, мен мәселені бір жол INLINE арқылы түзете алдым. GHC 8.4.4 және GHC 8.6.5 арасындағы белгілі бір уақытта оңтайландырушы мұны өздігінен тоқтатты.
Мен Хаскелл бағдарламалауында мұндай кірді кездестіремін деп ойламадым. Дегенмен, бүгінгі күні де оңтайландырушылар кейде қателіктер жібереді және оларға кеңестер беру біздің міндетіміз. Мысалы, бұл жерде функцияның сызылған болуы керек екенін білеміз, себебі ол императивті нұсқада сызылған және бұл компиляторға кеңес берудің себебі болып табылады.
Бұдан кейін не болды?
Содан кейін мен Hopcroft-Karp алгоритмін басқа монадалармен бірге жүзеге асырдым, бұл бағдарламаның аяқталуы болды.
Google Summer of Code бағдарламасының арқасында мен функционалдық бағдарламалауда практикалық тәжірибе жинадым, ол келесі жазда Джейн-стритте тағылымдамадан өтуге көмектесіп қана қойған жоқ (бұл жер тіпті Хабрдың хабардар аудиториясының арасында қаншалықты танымал екенін білмеймін, бірақ бұл бір Жазда функционалдық бағдарламалаумен айналысуға болатын бірнеше адамның бірі), сонымен қатар мені дәстүрлі тілдердегі тәжірибемнен айтарлықтай ерекшеленетін осы парадигманы тәжірибеде қолданудың тамаша әлемімен таныстырды.
Ақпарат көзі: www.habr.com