Минатото лето учествував во Google Summer of Code - програма за студенти од Google. Секоја година, организаторите избираат неколку проекти со отворен код, вклучително и од такви познати организации како Boost.org и Фондација Линукс. Google ги поканува студентите од целиот свет да работат на овие проекти. 

Како учесник на Google Summer of Code 2019, направив проект во библиотеката Алги со организацијата Haskell.org, кој го развива јазикот Хаскел - еден од најпознатите функционални програмски јазици. Алга е библиотека која претставува напишете безбедно претставување за графикони во Хаскел. Се користи, на пример, во семантички — библиотека Github која гради семантички дрвја, графикони за повици и зависност врз основа на код и може да ги споредува. Мојот проект беше да додадам безбедна претстава за бипартитните графикони и алгоритми за таа репрезентација. 

Во овој пост ќе зборувам за мојата имплементација на алгоритам за проверка на графикон за бипартитет во Хаскел. Иако алгоритмот е еден од најосновните, неговото прекрасно имплементирање во функционален стил ми одзеде неколку повторувања и бараше доста работа. Како резултат на тоа, се решив на имплементација со трансформатори на монади. 

Изјава

Јас се викам Василиј Алферов, студент сум четврта година во Санкт Петербург HSE. Претходно во блогот напишав за мојот проект за параметризирани алгоритми и за патувањето до ЗуриХац. Во моментов сум на стажирање во Универзитетот во Берген во Норвешка, каде што работам на пристапи кон проблемот Список за боење. Моите интереси вклучуваат параметриизирани алгоритми и функционално програмирање.

За имплементацијата на алгоритмот

предговорот

Студентите кои учествуваат во програмата силно се охрабруваат да блогираат. Ми обезбедија платформа за блогот Лето на Хаскел. Оваа статија е превод Член, напишана од мене таму во јули на англиски јазик, со краток предговор. 

Може да се најде барање за повлекување со дотичниот код тука.

Можете да прочитате за резултатите од мојата работа (на англиски) тука.

Овој пост е наменет да го запознае читателот со основните концепти во функционалното програмирање, иако ќе се обидам да се потсетам на сите употребени термини кога ќе дојде време.

Проверка на графикони за двостраност 

Алгоритам за проверка на графикон за бипартитет обично се дава во курсот за алгоритми како еден од наједноставните графички алгоритми. Неговата идеја е јасна: прво некако ставаме темиња во левиот или десниот дел, а кога ќе се најде конфликтен раб, тврдиме дека графикот не е бипартитен.

Малку повеќе детали: прво ставивме некое теме во левиот дел. Очигледно, сите соседи на ова теме мора да лежат во десниот лобус. Понатаму, сите соседи на соседите на ова теме мора да лежат во левиот лобус итн. Продолжуваме да доделуваме акции на темиња сè додека сè уште има темиња во поврзаната компонента на темето со која започнавме и на кои не сме доделиле соседи. Потоа го повторуваме ова дејство за сите поврзани компоненти.

Ако постои раб помеѓу темињата што спаѓаат во истата партиција, не е тешко да се најде непарен циклус во графикот, што е нашироко познато (и сосема очигледно) невозможно во бипартитниот граф. Во спротивно, имаме правилна партиција, што значи дека графикот е бипартит.

Вообичаено, овој алгоритам се имплементира со користење ширина прво пребарување или длабинско прво пребарување. Во императивните јазици, пребарувањето на прво место обично се користи бидејќи е малку поедноставно и не бара дополнителни структури на податоци. Исто така, избрав пребарување во длабочина бидејќи е потрадиционално.

Така, дојдовме до следната шема. Ги поминуваме темињата на графикот користејќи пребарување на прво длабочина и им доделуваме акции, менувајќи го бројот на споделувањето додека се движиме по работ. Ако се обидеме да доделиме удел на теме на кое веќе има доделен дел, можеме безбедно да кажеме дека графикот не е бипартитен. Во моментот кога на сите темиња им е доделен дел и ги разгледавме сите рабови, имаме добра партиција.

Чистота на пресметките

Во Хаскел претпоставуваме дека сите пресметки се чисти. Меѓутоа, ако навистина беше така, немаше да имаме начин да испечатиме ништо на екранот. Воопшто, чист пресметките се толку мрзливи што нема ниту една чисти причини да се пресмета нешто. Сите пресметки што се случуваат во програмата некако се принудени "нечист" монада IO.

Монадите се начин да се претстават пресметките со ефекти во Хаскел. Објаснувањето како тие работат е надвор од опсегот на овој пост. Добар и јасен опис може да се прочита на англиски јазик тука.

Овде сакам да истакнам дека додека некои монади, како што е IO, се имплементираат преку компајлер магија, скоро сите други се имплементирани во софтвер и сите пресметки во нив се чисти.

Има многу ефекти и секој има своја монада. Ова е многу силна и убава теорија: сите монади го спроведуваат истиот интерфејс. Ќе зборуваме за следните три монади:

• Или ea е пресметка која враќа вредност од типот a или фрла исклучок од типот e. Однесувањето на оваа монада е многу слично на справувањето со исклучоци во императивните јазици: грешките може да се фатат или да се пренесат. Главната разлика е во тоа што монадата е целосно логично имплементирана во стандардната библиотека во Хаскел, додека императивните јазици обично користат механизми на оперативниот систем.
• Состојбата sa е пресметка која враќа вредност од типот a и има пристап до променлива состојба од типот s.
• Можеби а. Монадата Можеби изразува пресметување што може да се прекине во секое време со враќање на Ништо. Сепак, ќе зборуваме за имплементација на класата MonadPlus за типот Maybe, која го изразува спротивниот ефект: тоа е пресметка што може да се прекине во секое време со враќање на одредена вредност.

Имплементација на алгоритмот

Имаме два типа податоци, График a и Bigraph ab, од кои првиот претставува графикони со темиња означени со вредности од типот a, а вториот претставува бипартитни графикони со темиња од левата страна означени со вредности од типот a и десно. - странични темиња означени со вредности од типот b.

Ова не се типови од библиотеката Алга. Алга нема претстава за ненасочени бипартитни графици. Ги направив ваквите типови за јасност.

Ќе ни требаат и помошни функции со следните потписи:

-- Список соседей данной вершины.
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 за Можеби. Главната разлика е во тоа што Или може да врати вредност ако пресметката не е прекината, а Можеби враќа само информации за ова во овој случај. Бидејќи не ни треба посебна вредност за успех (таа е веќе зачувана во State), избираме Можеби. И во моментот кога треба да ги споиме ефектите на две монади, тие излегуваат монадски трансформатори, кои прецизно ги комбинираат овие ефекти.

Зошто избрав толку сложен тип? Две причини. Прво, имплементацијата се покажува како многу слична на императив. Второ, треба да манипулираме со повратната вредност во случај на конфликт кога се враќаме од рекурзија за да ја вратиме непарната јамка, што е многу полесно да се направи во монадата Можеби.

Така ја добиваме оваа имплементација.

{-# 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 таму.
• oneEdge е делот каде што го посетуваме работ. Се повикува двапати за секој раб. Овде проверуваме дали темето од другата страна е посетено, а ако не е посетено. Ако е посетено, проверуваме дали работ е конфликтен. Ако е така, ја враќаме вредноста - самиот врв на рекурзивниот оџак, каде што сите други темиња ќе бидат поставени по враќањето.
• processVertex проверува за секое теме дали е посетено и работи во Vertex на него ако не.
• dfs работи processVertex на сите темиња.

Тоа е се.

Историја на зборот INLINE

Зборот INLINE не беше во првата имплементација на алгоритмот; тој се појави подоцна. Кога се обидов да најдам подобра имплементација, открив дека не-INLINE верзијата е значително побавна на некои графикони. Имајќи предвид дека семантички функциите треба да работат исто, ова многу ме изненади. Уште почудно, на друга машина со различна верзија на GHC немаше забележителна разлика.

Откако поминав една недела читајќи го излезот на GHC Core, успеав да го поправам проблемот со една линија експлицитна INLINE. Во одреден момент помеѓу GHC 8.4.4 и GHC 8.6.5, оптимизаторот престана да го прави тоа сам.

Не очекував да наидам на таква нечистотија во програмирањето Хаскел. Сепак, дури и денес, оптимизаторите понекогаш прават грешки и наша задача е да им дадеме совети. На пример, овде знаеме дека функцијата треба да биде вметната затоа што е вметната во императивната верзија, и ова е причина да му дадеме навестување на компајлерот.

Што се случи следно?

Потоа го имплементирав алгоритмот Хопкрофт-Карп со други монади и тоа беше крајот на програмата.

Благодарение на Google Summer of Code, стекнав практично искуство во функционално програмирање, што не само што ми помогна да добијам стажирање на улицата Јане следното лето (не сум сигурен колку ова место е познато дури и меѓу упатената публика на Хабр, но тоа е едно од ретките каде што можете да летувате за да се вклучите во функционално програмирање), но исто така ме воведе во прекрасниот свет на примена на оваа парадигма во пракса, значително различен од моето искуство во традиционалните јазици.

Извор: www.habr.com