Мінулым летам я ўдзельнічаў у - праграме для студэнтаў ад кампаніі Google. Штогод арганізатары адбіраюць некалькі Open Source-праектаў, у тым ліку ад такіх вядомых арганізацый, як и . Для працы над гэтымі праектамі Google запрашае студэнтаў з усяго свету.
Як удзельнік Google Summer of Code 2019 я рабіў праект у рамках бібліятэкі з арганізацыяй , якая займаецца развіццём мовы Хаскель - адной з самых вядомых функцыянальных моў праграмавання. Alga – бібліятэка, якая прадстаўляе прадстаўленне для графаў у Хаскеле. Яна выкарыстоўваецца, напрыклад, у - бібліятэцы кампаніі Github, якая будуе па кодзе семантычныя дрэвы, графы выклікаў і залежнасцяў і якая ўмее іх параўноўваць. Мой праект складаўся ў даданні туды тыпабяспечнага падання для двухдольных графаў і алгарытмаў для гэтага падання.
У пасце я раскажу пра сваю рэалізацыю алгарытму праверкі графа на двухдольнасць на Хаскелле. Нягледзячы на тое, што алгарытм з'яўляецца адным з самых базавых, яго прыгожая рэалізацыя ў функцыянальным стылі заняла ў мяне некалькі ітэрацый і запатрабавала даволі шмат працы. У выніку я спыніўся на рэалізацыі з трансформерамі манад.
Пра сябе
Мяне клічуць Васіль Алфёраў, я студэнт чацвёртага курса Піцерскай Вышкі. Раней у блогу я пісаў и . Прама зараз я знаходжуся на стажыроўцы ў у Нарвегіі, дзе займаюся падыходамі да задачы . У сферу маіх інтарэсаў уваходзяць параметрызаваныя алгарытмы і функцыянальнае праграмаванне.
Аб рэалізацыі алгарытму
Прадмова
Студэнтам, якія ўдзельнічаюць у праграме, настойліва рэкамендуецца весці блог. Мне для блога падалі пляцоўку . Гэты артыкул - пераклад , напісанай мной туды ў ліпені на англійскай мове, з невялікай прадмовай.
Pull Request з кодам, пра які ідзе гаворка, можна знайсці .
Пра вынікі маёй працы можна пачытаць (на англійскай) .
Пост мяркуе знаёмства чытача з базавымі паняццямі ў функцыянальным праграмаванні, хоць я пастараюся нагадаць усе выкарыстоўваныя тэрміны, калі да іх дойдзе час.
Праверка графаў на двухдольнасць
Алгарытм праверкі графа на двухдольнасць звычайна даецца ў курсе алгарытмаў як адзін з найпростых графавых алгарытмаў. Яго ідэя прамалінейная: спачатку мы нейкім чынам кладзем вяршыні ў левую ці правую долю, а пры выяўленні канфліктнага рабра сцвярджаем, што граф не з'яўляецца двухдольным.
Крыху падрабязней: спачатку мы кладзем нейкую вяршыню ў левую долю. Відавочна, усе суседзі гэтай вяршыні павінны ляжаць у правай долі. Далей, усе суседзі суседзяў гэтай вяршыні павінны ляжаць у левай долі, і гэтак далей. Мы працягваем прызначаць вяршыням долі датуль, пакуль у кампаненце складнасці вяршыні, з якой мы пачалі, яшчэ ёсць вяршыні, якім мы не прызначылі суседзяў. Затым мы паўтараем гэта дзеянне для ўсіх кампанент складнасці.
Калі ёсць рабро паміж вяршынямі, якія патрапілі ў адну і тую ж дзель, нескладана знайсці ў графе няцотны цыкл, як шырока вядома (і досыць відавочна) немагчымы ў двухдольным графе. Інакш у нас ёсць карэктнае разбіццё на долі, а значыць, граф з'яўляецца двухдольным.
Як правіла, гэты алгарытм рэалізуюць з дапамогай або . У імператыўных мовах звычайна выкарыстоўваюць пошук у глыбіню, як крыху больш просты і які не патрабуе дадатковых структур дадзеных. Я таксама абраў пошук у глыбіню як больш традыцыйны.
Такім чынам, мы дашлі да наступнай схемы. Мы абыходзім вяршыні графа з дапамогай пошуку ў глыбіню і прызначаем ім долі, змяняючы нумар долі пры пераходзе па рабры. Калі мы спрабуем прызначыць долю вяршыні, у якой доля ўжо прызначаная, можна смела сцвярджаць, што граф не з'яўляецца двухдольным. У той момант, калі ўсім вяршыням прызначаная дзель і мы паглядзелі на ўсе рэбры, у нас ёсць добрае разбіццё.
Чысціня вылічэнняў
У Хаскеле мы мяркуем, што ўсе вылічэнні з'яўляюцца чыстымі. Аднак, калі б гэта сапраўды было так, у нас не было б магчымасці надрукаваць штосьці на экран. Наогул, чыстыя вылічэнні настолькі гультаяватыя, што не існуе ніводнай чыстай прычыны штосьці вылічаць. Усе вылічэнні, якія адбываюцца ў праграме, так ці інакш фарсіруюцца ў «нячыстай» манадзе IO.
Манады - спосаб прадстаўлення вылічэнняў з эфектамі у Хаскеле. Тлумачэнне таго, як яны працуюць, выходзіць за рамкі гэтай пасады. Добрае і зразумелае апісанне можна пачытаць на англійскай .
Тут я хачу заўважыць, што ў той час як некаторыя манады, такія, як IO, рэалізаваны праз магію кампілятара, амаль усе астатнія рэалізаваны праграмна і ўсе вылічэнні ў іх з'яўляюцца чыстымі.
Эфектаў бывае вельмі шмат і пад кожны заведзена свая манада. Гэта вельмі моцная і прыгожая тэорыя: усе манады рэалізуюць адзін і той жа інтэрфейс. Мы будзем казаць пра наступныя тры манады:
- Either ea - вылічэнне, якое вяртае значэнне тыпу a або кідае выключэнне тыпу e. Паводзіны гэтай манады вельмі падобныя да працы з выключэннямі ў імператыўных мовах: памылкі могуць быць злоўлены або перададзены далей. Асноўная розніца ў тым, што манада цалкам лагічна рэалізавана ў стандартнай бібліятэцы на тым жа Хаскеле, у той час як у імператыўных мовах звычайна выкарыстоўваюцца механізмы аперацыйнай сістэмы.
- State sa - вылічэнне, якое вяртае значэнне тыпу a і мае доступ да змяняецца стану тыпу s.
- Maybe a. Манада Maybe выказвае вылічэнне, якое можа быць у любы момант перапынена вяртаннем Nothing. Аднак мы будзем казаць пра рэалізацыю класа MonadPlus для тыпу Maybe, якая выказвае супрацьлеглы эфект: гэта вылічэнне, якое можа быць у любы момант перапынена вяртаннем канкрэтнага значэння.
Рэалізацыя алгарытму
У нас ёсць два тыпу дадзеных, Graph a і Bigraph ab, першы з якіх уяўляе графы з вяршынямі, пазначанымі значэннямі тыпу a, а другі ўяўляе двухдольныя графы з вяршынямі левай часткі, пазначанымі значэннямі тыпу a і вяршынямі правай часткі, пазначанымі значэннямі тыпу b.
Гэта не тыпы з бібліятэкі Alga. У 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, якая быццам рэалізуе якраз тыя эфекты, якія нам патрэбныя. Першая напісаная мной рэалізацыя была вельмі блізкай да гэтага варыянта. Насамрэч, у мяне было пяць розных рэалізацый у нейкі момант, і я ў выніку спыніўся на іншы.
Па-першае, нам трэба падтрымліваць асацыятыўны масіў ідэнтыфікатараў доляй – гэта нешта пра State. Па-другое, нам трэба ўмець спыняцца ў выпадку выяўлення канфлікту. Гэта можа быць ці Monad для Either, ці MonadPlus для Maybe. Асноўная розніца ў тым, што Either можа вяртаць значэнне ў выпадку, калі вылічэнне не было спынена, а Maybe вяртае ў такім выпадку толькі інфармацыю аб гэтым. Паколькі нам не трэба асобнае значэнне ў выпадку поспеху (яно ўжо захоўваецца ў State), мы выбіраем Maybe. А ў той момант, калі нам трэба камбінаваць эфекты двух манад, вылазяць , якія як раз і камбінуюць гэтыя эфекты.
Чаму я абраў такі складаны тып? Дзве прычыны. Па-першае, рэалізацыя атрымліваецца вельмі падобнай да імпэратыўнай. Па-другое, нам трэба маніпуляваць значэннем, якое вяртаецца ў выпадку канфлікту, пры вяртанні назад з рэкурсіі для аднаўлення няцотнага цыклу, а гэта значна прасцей рабіць у манадзе 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 аптымізатар перастаў гэта рабіць самастойна.
Я не чакаў сустрэць такі бруд у праграмаванні на Хаскелле. Аднак аптымізатары ўсё ж нават у наш час часам здзяйсняюць памылкі і даваць ім падказкі - наша задача. Напрыклад, тут мы ведаем, што функцыя павінна быць заінлайнаваная, бо яна заінлайнаваная ў імператыўнай версіі, і гэта нагода даць кампілятару падказку.
Што было далей?
Далей я рэалізаваў алгарытм Хокрофта-Карпа ўжо з іншымі монадамі, і на гэтым праграма скончылася.
Дзякуючы Google Summer of Code я набыў практычны досвед у функцыянальным праграмаванні, які не толькі дапамог мне прайсці на стажыроўку ў Jane Street на наступнае лета (не ўпэўнены, наколькі гэтае месца вядома нават сярод дасведчанай аўдыторыі Хабра, але яно — адно з нямногіх, дзе можна улетку займацца функцыянальным праграмаваннем), але і пазнаёміў з дзіўным светам ужывання гэтай парадыгмы на практыцы, значна адрозным ад майго досведу ў традыцыйных мовах.
Крыніца: habr.com