Тобистони гузашта ман дар он иштирок доштам - барнома барои донишҷӯён аз Google. Ҳар сол созмондиҳандагон якчанд лоиҳаҳои кушодаасосро интихоб мекунанд, аз ҷумла аз созмонҳои маъруф ба монанди и . Google донишҷӯёнро аз тамоми ҷаҳон даъват мекунад, ки дар ин лоиҳаҳо кор кунанд.
Ҳамчун иштирокчии Google Summer of Code 2019, ман як лоиҳаро дар дохили китобхона иҷро кардам бо ташкилот , ки забони Ҳаскеллро таҳия мекунад - яке аз маъруфтарин забонҳои барномасозии функсионалӣ. Алга китобхонаест, ки намояндагон намояндагӣ барои графикҳо дар Haskell. Он, масалан, дар - китобхонаи Github, ки дарахтони семантикӣ, графикҳои занг ва вобастагӣ дар асоси код месозад ва метавонад онҳоро муқоиса кунад. Лоиҳаи ман аз он иборат буд, ки як намоиши бехатар барои графикҳо ва алгоритмҳои дутарафа барои ин намояндагӣ илова карда шавад.
Дар ин мақола ман дар бораи татбиқи алгоритми санҷиши графикии дутарафа дар Ҳаскелл сӯҳбат мекунам. Гарчанде ки алгоритм яке аз маъмултарин аст, татбиқи он ба таври зебо дар услуби функсионалӣ ман якчанд такрорро талаб мекард ва кори зиёдеро талаб мекард. Дар натиҷа, ман ба татбиқи бо трансформаторҳои монадӣ қарор гирифтам.
Дар бораи худам
Номи ман Василий Алферов, ман донишҷӯи соли чоруми ҲСМ Санкт-Петербург ҳастам. Пештар дар блог ман навишта будам и . Ҳоло ман дар таҷрибаомӯзӣ ҳастам дар Норвегия, ки дар он чо ман дар бораи равишхои халли проблема кор карда истодаам . Таваҷҷӯҳҳои ман аз алгоритмҳои параметрӣ ва барномасозии функсионалӣ иборатанд.
Дар бораи амалй гардондани алгоритм
Пешгуфтор
Донишҷӯёне, ки дар барнома иштирок мекунанд, сахт ташвиқ карда мешаванд, ки блогнависӣ кунанд. Онҳо ба ман платформа барои блог пешниҳод карданд . Ин мақола тарҷума аст , ки аз тарафи ман дар он ҷо моҳи июл ба забони англисӣ, бо пешгуфтори кӯтоҳ навишта шудааст.
Дархостро бо рамзи мавриди назар пайдо кардан мумкин аст .
Шумо метавонед дар бораи натиҷаҳои кори ман хонед (ба забони англисӣ) .
Ин мақола барои ошно кардани хонанда бо мафҳумҳои асосӣ дар барномасозии функсионалӣ пешбинӣ шудааст, гарчанде ки ман кӯшиш мекунам, ки ҳама истилоҳҳои истифодашударо ҳангоми фаро расидани вақт ба ёд орам.
Санҷиши графикҳо барои дутарафа
Алгоритм барои тафтиши график барои дутарафагӣ одатан дар курси алгоритмҳо ҳамчун яке аз соддатарин алгоритмҳои графикӣ дода мешавад. Идеяи ӯ одилона аст: аввал мо бо навъе қуллаҳоро ба ҳиссаи чап ё рост мегузорем ва вақте ки канори ба ҳам мухолиф пайдо мешавад, мо тасдиқ мекунем, ки график дутарафа нест.
Тафсилоти каме: аввал мо дар қисми чап каме қулла мегузорем. Аён аст, ки ҳамаи ҳамсояҳои ин вертекс бояд дар лобеи рост хобанд. Минбаъд, ҳамаи ҳамсояҳои ҳамсояҳои ин vertex бояд дар lobe чап дурӯғ, ва ғайра. Мо таъин кардани саҳмияҳоро ба қуллаҳо идома медиҳем, то он даме, ки дар ҷузъи пайвасти қуллае, ки мо бо он оғоз кардаем, ки ҳамсояҳоро ба онҳо таъин накардаем, қуллаҳо мавҷуданд. Пас мо ин амалро барои ҳамаи ҷузъҳои пайваст такрор мекунем.
Агар дар байни қуллаҳое, ки ба як қисмат афтодаанд, каноре мавҷуд бошад, дар график пайдо кардани даври тоқ, ки дар графики дутарафа ба таври васеъ маълум (ва комилан баръало) ғайриимкон аст, душвор нест. Дар акси ҳол, мо қисмати дуруст дорем, ки ин маънои онро дорад, ки график дутарафа аст.
Одатан, ин алгоритм бо истифода аз амалӣ карда мешавад ё . Дар забонҳои императивӣ, ҷустуҷӯи амиқ-аввал одатан истифода мешавад, зеро он каме соддатар аст ва сохторҳои иловагии додаҳоро талаб намекунад. Ман инчунин ҷустуҷӯи амиқро интихоб кардам, зеро он анъанавӣ аст.
Ҳамин тариқ, мо ба нақшаи зерин омадем. Мо бо истифода аз ҷустуҷӯи умқи аввал қуллаҳои графикро мегузарем ва ба онҳо саҳмияҳоро таъин мекунем ва ҳангоми ҳаракат дар канори канор шумораи саҳмро тағир медиҳем. Агар мо кӯшиш кунем, ки ҳиссаи худро ба қуллае таъин кунем, ки аллакай ҳиссаи таъиншуда дорад, мо бо боварӣ гуфта метавонем, ки график дутарафа нест. Лаҳзае, ки ба ҳама қуллаҳо як ҳиссаи таъин карда мешаванд ва мо ба ҳама кунҷҳо назар кардем, мо қисмати хуб дорем.
Тоза будани ҳисобҳо
Дар Ҳаскелл мо тахмин мезанем, ки ҳама ҳисобҳо ҳастанд тоза. Аммо, агар ин воқеан ҳамин тавр мебуд, мо имкони чоп кардани чизеро дар экран надорем. Умуман, тоза ҳисобу китоб чунон танбал аст, ки як нест тоза сабабҳои ҳисоб кардани чизе. Ҳама ҳисобҳои дар барнома рухдода ба гунае маҷбур мешаванд "наҷис" monad IO.
Монадаҳо як роҳи муаррифии ҳисобҳо бо таъсирот дар Хаскелл. Шарҳ додани он ки чӣ тавр онҳо кор мекунанд, аз доираи ин мақола берун аст. Тавсифи хуб ва равшанро бо забони англисӣ хондан мумкин аст .
Дар ин ҷо ман мехоҳам қайд намоям, ки дар ҳоле ки баъзе монадҳо, ба монанди IO, тавассути ҷодугарии компилятор амалӣ карда мешаванд, тақрибан ҳамаи дигарон дар нармафзор амалӣ карда мешаванд ва ҳама ҳисобҳо дар онҳо поканд.
Эффектҳои зиёде мавҷуданд ва ҳар яке монадҳои худро дорад. Ин як назарияи хеле қавӣ ва зебо аст: ҳама монадҳо интерфейси якхеларо амалӣ мекунанд. Мо дар бораи се монадҳои зерин сӯҳбат хоҳем кард:
- Ё ea ҳисобест, ки арзиши навъи a-ро бармегардонад ё истиснои навъи e-ро мепартояд. Рафтори ин монад ба коркарди истисно дар забонҳои императивӣ хеле монанд аст: хатогиҳоро метавон дастгир кард ё ба онҳо интиқол дод. Тафовути асосӣ дар он аст, ки монад комилан мантиқӣ дар китобхонаи стандартии Ҳаскелл амалӣ карда мешавад, дар ҳоле ки забонҳои императивӣ одатан механизмҳои системаи амалиётиро истифода мебаранд.
- Ҳолати sa ҳисобест, ки арзиши навъи a-ро бармегардонад ва ба ҳолати тағирёбандаи навъи s дастрасӣ дорад.
- Шояд а. Шояд монад ҳисобкуниро ифода мекунад, ки онро дар вақти дилхоҳ бо баргардонидани Ҳеҷ чиз қатъ кардан мумкин аст. Бо вуҷуди ин, мо дар бораи татбиқи синфи MonadPlus барои навъи Maybe сӯҳбат хоҳем кард, ки таъсири муқобилро ифода мекунад: ин ҳисобест, ки онро дар вақти дилхоҳ бо баргардонидани арзиши мушаххас қатъ кардан мумкин аст.
Амалисозии алгоритм
Мо ду намуди додаҳо дорем, Graph 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 барои Шояд бошад. Тафовути асосӣ дар он аст, ки Ё метавонад арзишро баргардонад, агар ҳисобкунӣ қатъ нашуда бошад ва Шояд дар ин ҳолат танҳо маълумотро дар бораи ин бармегардонад. Азбаски барои муваффақият ба мо арзиши алоҳида лозим нест (он аллакай дар иёлат нигоҳ дошта шудааст), мо Шояд -ро интихоб мекунем. Ва дар айни замон, ки ба мо лозим аст, ки таъсири ду монадро якҷоя кунем, онҳо берун меоянд , ки ин таъсирҳоро дақиқ муттаҳид мекунанд.
Чаро ман чунин навъи мураккабро интихоб кардам? Ду сабаб. Аввалан, татбиқи он ба императив хеле монанд аст. Дуюм, ба мо лозим аст, ки арзиши бозгаштро дар ҳолати ихтилоф ҳангоми бозгашт аз рекурсия барқарор кунем, то ҳалқаи тоқро барқарор кунем, ки иҷрои он дар шояд монад хеле осонтар аст.
Ҳамин тариқ, мо ин татбиқро ба даст меорем.
{-# 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 арзиш баргардонад, мо vertex 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, ман дар барномасозии функсионалӣ таҷрибаи амалӣ ба даст овардам, ки ин на танҳо ба ман кӯмак кард, ки тобистони оянда дар Ҷейн Стрит таҷрибаомӯзӣ гирам (ман намедонам, ки ин ҷой ҳатто дар байни аудиторияи донишманди Ҳабр то чӣ андоза маъруф аст, аммо ин як аз чанде, ки шумо метавонед тобистон ба барномасозии функсионалӣ машғул шавед), балки инчунин маро бо ҷаҳони аҷиби татбиқи ин парадигма дар амал шинос кард, ки аз таҷрибаи ман дар забонҳои анъанавӣ ба таври назаррас фарқ мекунад.
Манбаъ: will.com