Прошлог лета сам учествовао - програм за студенте из Гугла. Сваке године организатори бирају неколико пројеката отвореног кода, укључујући и такве познате организације као што су и . Гоогле позива студенте из целог света да раде на овим пројектима.
Као учесник Гоогле Суммер оф Цоде 2019, урадио сам пројекат у оквиру библиотеке са организацијом , који развија језик Хаскелл – један од најпознатијих функционалних програмских језика. Алга је библиотека која представља представљање за графове у Хаскелу. Користи се, на пример, у — Гитхуб библиотека која гради семантичка стабла, графове позива и зависности на основу кода и може да их пореди. Мој пројекат је био да додам безбедну репрезентацију за бипартитне графове и алгоритме за ту репрезентацију.
У овом посту ћу говорити о својој имплементацији алгоритма за проверу графа на бипартитност у Хаскелл-у. Иако је алгоритам један од најосновнијих, његова лепа имплементација у функционалном стилу ми је одузела неколико итерација и захтевала је доста посла. Као резултат тога, одлучио сам се на имплементацији са монадним трансформаторима.
О мени
Зовем се Василиј Алферов, студент сам четврте године ХСЕ у Санкт Петербургу. Раније у блогу који сам написао и . Тренутно сам на пракси у у Норвешкој, где радим на приступима проблему . Моја интересовања укључују параметризоване алгоритме и функционално програмирање.
О имплементацији алгоритма
Предговор
Студенти који учествују у програму се снажно охрабрују да воде блог. Обезбедили су ми платформу за блог . Овај чланак је превод , коју сам тамо написао у јулу на енглеском, са кратким предговором.
Захтев за повлачење са дотичним кодом се може пронаћи .
О резултатима мог рада можете прочитати (на енглеском) .
Овај пост има за циљ да упозна читаоца са основним концептима функционалног програмирања, мада ћу покушати да се присетим свих термина који се користе када дође време.
Провера графова на бипартитност
Алгоритам за проверу графа на бипартитност се обично даје у курсу о алгоритмима као један од најједноставнијих алгоритама графа. Његова идеја је јасна: прво некако ставимо врхове у леву или десну деоницу, а када се пронађе конфликтна ивица, тврдимо да граф није бипартитан.
Мало детаљније: прво стављамо неки врх у леви део. Очигледно, сви суседи овог темена морају лежати у десном режњу. Даље, сви суседи суседа овог темена морају лежати у левом режњу, и тако даље. Настављамо да додељујемо удео врховима све док у повезаној компоненти темена са којим смо започели још постоје врхови којима нисмо доделили суседе. Затим понављамо ову радњу за све повезане компоненте.
Ако постоји ивица између врхова који спадају у исту партицију, није тешко пронаћи непаран циклус у графу, што је опште познато (и сасвим очигледно) немогуће у бипартитном графу. У супротном, имамо исправну партицију, што значи да је граф бипартитан.
Обично се овај алгоритам имплементира помоћу или . У императивним језицима обично се користи претрага у дубину јер је мало једноставнија и не захтева додатне структуре података. Такође сам изабрао претрагу у дубину јер је традиционалније.
Тако смо дошли до следеће шеме. Прелазимо преко врхова графа користећи претрагу у дубину и додељујемо им удео, мењајући број удела док се крећемо дуж ивице. Ако покушамо да доделимо удео врху коме је већ додељен удео, можемо са сигурношћу рећи да граф није бипартитан. У тренутку када је свим врховима додељен удео и када смо погледали све ивице, имамо добру партицију.
Чистоћа прорачуна
У Хаскелу претпостављамо да су сви прорачуни чист. Међутим, да је то заиста тако, не бисмо имали начина да било шта одштампамо на екрану. Уопште, чист прорачуни су толико лењи да их нема чист разлога да се нешто израчуна. Сви прорачуни који се дешавају у програму су на неки начин присиљени "нечист" монада ИО.
Монаде су начин представљања прорачуна помоћу ефекти у Хаскелу. Објашњавање како они раде је ван оквира овог поста. Добар и јасан опис може се прочитати на енглеском .
Овде желим да истакнем да док се неке монаде, као што је ИО, имплементирају путем компајлерске магије, скоро све остале су имплементиране у софтверу и сви прорачуни у њима су чисти.
Има много ефеката и сваки има своју монаду. Ово је веома јака и лепа теорија: све монаде примењују исти интерфејс. Говорићемо о следеће три монаде:
- Или еа је прорачун који враћа вредност типа а или избацује изузетак типа е. Понашање ове монаде је веома слично руковању изузетцима у императивним језицима: грешке се могу ухватити или пренети даље. Главна разлика је у томе што је монада потпуно логично имплементирана у стандардну библиотеку у Хаскелл-у, док императивни језици обично користе механизме оперативног система.
- Стање са је прорачун који враћа вредност типа а и има приступ променљивом стању типа с.
- Можда а. Монада Маибе изражава прорачун који се може прекинути у било ком тренутку враћањем Ништа. Међутим, говорићемо о имплементацији класе МонадПлус за тип Маибе, који изражава супротан ефекат: то је прорачун који се у сваком тренутку може прекинути враћањем одређене вредности.
Имплементација алгоритма
Имамо два типа података, Граф а и Биграф аб, од којих први представља графове са врховима означеним вредностима типа а, а други представља бипартитне графове са левим врховима означеним вредностима типа а и десно -бочни врхови означени вредностима типа б.
Ово нису типови из библиотеке Алга. Алга нема репрезентацију за неусмерене бипартитне графове. Направио сам овакве типове ради јасноће.
Такође ће нам требати помоћне функције са следећим потписима:
-- Список соседей данной вершины.
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)Лако је видети да ако смо током претраге у дубину пронашли конфликтну ивицу, непарни циклус лежи на врху рекурзивног стека. Дакле, да бисмо га вратили, морамо да одсечемо све од рекурзивног стека до првог појављивања последњег темена.
Ми имплементирамо претрагу у дубину тако што одржавамо асоцијативни низ бројева удела за сваки врх. Рекурзивни стог ће се аутоматски одржавати кроз имплементацију класе Фунцтор монаде коју смо изабрали: биће нам потребно само да ставимо све врхове са путање у резултат враћен из рекурзивне функције.
Моја прва идеја је била да користим монаду Еитхер, која изгледа да имплементира управо оне ефекте који су нам потребни. Прва имплементација коју сам написао била је веома блиска овој опцији. У ствари, имао сам пет различитих имплементација у једном тренутку и на крају сам се одлучио на другу.
Прво, морамо да одржавамо асоцијативни низ идентификатора дељења – ово је нешто о држави. Друго, морамо бити у стању да зауставимо када се открије конфликт. Ово може бити или Монад за Или, или МонадПлус за Можда. Главна разлика је у томе што Еитхер може вратити вредност ако израчунавање није заустављено, а Можда враћа само информације о томе у овом случају. Пошто нам за успех није потребна посебна вредност (већ је ускладиштена у држави), бирамо Можда. И у тренутку када треба да спојимо ефекте две монаде, они излазе , који прецизно комбинују ове ефекте.
Зашто сам изабрао тако сложен тип? Два разлога. Прво, испоставило се да је имплементација веома слична императиву. Друго, морамо да манипулишемо повратном вредношћу у случају конфликта када се враћамо из рекурзије да бисмо вратили непарну петљу, што је много лакше урадити у монади Маибе.
Тако добијамо ову имплементацију.
{-# 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)
Блок вхере је језгро алгоритма. Покушаћу да објасним шта се дешава у њему.
- инВертек је део претраге у дубину где први пут посећујемо врх. Овде додељујемо број дељења врху и покрећемо онЕдге на свим суседима. Ово је такође место где враћамо стек позива: ако је мсум вратио вредност, гурамо врх в тамо.
- онЕдге је део где посећујемо ивицу. Позива се два пута за сваку ивицу. Овде проверавамо да ли је врх на другој страни посећен и посећујемо га ако није. Ако нас посетите, проверавамо да ли је ивица конфликтна. Ако јесте, враћамо вредност - сам врх рекурзивног стека, где ће сви остали врхови бити смештени по повратку.
- процессВертек проверава за сваки врх да ли је посећен и покреће инВертек на њему ако није.
- дфс покреће процессВертек на свим врховима.
То је све.
Историја речи ИНЛИНЕ
Реч ИНЛИНЕ није била у првој имплементацији алгоритма; појавила се касније. Када сам покушао да пронађем бољу имплементацију, открио сам да је верзија која није ИНЛИНЕ била приметно спорија на неким графиконима. С обзиром да би семантички функције требале да раде исто, ово ме је веома изненадило. Што је још чудније, на другој машини са другом верзијом ГХЦ-а није било приметне разлике.
Након што сам недељу дана провео читајући ГХЦ Цоре излаз, успео сам да решим проблем са једном линијом експлицитног ИНЛИНЕ. У неком тренутку између ГХЦ 8.4.4 и ГХЦ 8.6.5 оптимизатор је престао да то ради сам.
Нисам очекивао да ћу наићи на такву прљавштину у Хаскелл програмирању. Међутим, чак и данас, оптимизатори понекад праве грешке, а наш је посао да им дамо наговештаје. На пример, овде знамо да функција треба да буде уметнута јер је уметнута у императивној верзији, а то је разлог да компајлеру дамо наговештај.
Шта се потом десило?
Затим сам имплементирао Хопцрофт-Карп алгоритам са другим монадама и то је био крај програма.
Захваљујући Гоогле Суммер оф Цоде, стекао сам практично искуство у функционалном програмирању, што ми је помогло не само да следећег лета добијем праксу у улици Јане Стреет (нисам сигуран колико је ово место познато чак и међу Хабровом добром публиком, али је једно од ретких где можете да се бавите функционалним програмирањем), али и увео ме у диван свет примене ове парадигме у пракси, значајно другачији од мог искуства у традиционалним језицима.
Извор: ввв.хабр.цом