Havîna par ez beşdar bûm - bernameyek ji bo xwendekarên ji Google. Her sal, organîzator gelek projeyên Çavkaniya Vekirî hilbijêrin, di nav de ji rêxistinên navdar ên wekî и . Google xwendekarên ji çar aliyên cîhanê vedixwîne ku li ser van projeyan bixebitin.
Wekî beşdarî Google Summer of Code 2019, min di nav pirtûkxaneyê de projeyek kir bi rêxistinê re , ku zimanê Haskell pêşve dike - yek ji navdartirîn zimanên bernamesaziya fonksiyonel. Alga pirtûkxaneyek e ku temsîl dike temsîla ji bo grafikên li Haskell. Ji bo nimûne, di nav de tê bikaranîn - pirtûkxaneyek Github ku darên semantîkî, grafikên bang û girêdanê li ser bingeha kodê ava dike û dikare wan bide ber hev. Projeya min ew bû ku ji bo wê nûnertiyê ji bo grafikên dupartî û algorîtmayan nûnertiyek ewledar a tîpan lê zêde bikim.
Di vê postê de ez ê li ser pêkanîna algorîtmayek ji bo kontrolkirina grafiyek ji bo dupartîbûnê li Haskell biaxivim. Her çend algorîtma yek ji bingehîn e jî, pêkanîna wê bi şêwazek fonksiyonel bi rengek xweşik ji min re gelek dubare kir û pir xebatek hewce kir. Wekî encamek, ez li ser pêkanîna bi transformatorên monadê rûniştim.
Li ser xwe
Navê min Vasily Alferov e, ez xwendekarê pola çaran im li St. Petersburg HSE. Berê di blogê de min nivîsand и . Niha ez li ser stajyerê me li Norwêcê, ku ez li ser nêzîkatiyên pirsgirêkê dixebitim . Berjewendiyên min algorîtmayên parameterkirî û bernameya fonksiyonel in.
Di derbarê pêkanîna algorîtmayê de
Pêşniyar
Xwendekarên ku beşdarî bernameyê dibin bi tundî têne teşwîq kirin ku blogê bikin. Wan ji min re platformek ji bo blogê peyda kirin . Ev gotar wergerek e , ji aliyê min ve di meha Tîrmehê de li wir bi Îngilîzî, bi pêşgotineke kurt hatiye nivîsandin.
Daxwaza vekişînê ya bi koda pirsê re dikare were dîtin .
Hûn dikarin li ser encamên xebata min bixwînin (bi Îngilîzî) .
Ev post texmîn dike ku xwendevan bi têgehên bingehîn ên di bernamesaziya fonksiyonel de nas e, her çend ez ê hewl bidim ku gava dem were hemî şertên ku hatine bikar anîn bi bîr bînim.
Kontrolkirina grafikan ji bo dupartîbûnê
Algorîtmayek ji bo kontrolkirina grafiyek ji bo dupartîbûnê bi gelemperî di qursek li ser algorîtmayan de wekî yek ji algorîtmayên grafîkî yên herî hêsan tê dayîn. Fikra wî rasterast e: Pêşî em bi rengekî risteyan di parça çepê an rastê de datînin, û gava ku keviya nakok were dîtin, em destnîşan dikin ku graf ne dupartî ye.
Piçek hûrgulî: Pêşîn em di beşa çepê de hin vertex danîn. Eşkere ye ku hemî cîranên vê vertexê divê di loba rastê de bin. Wekî din, hemî cîranên cîranên vê vertexê divê di lobêya çepê de bin, û hwd. Em danasîna pareyan li risteyan didomînin heya ku hîn di beşê vekêşana vekêşana ku me pê re dest pê kiriye de berz hebin ku me cîran jê re nedaye. Dûv re em vê çalakiyê ji bo hemî pêkhateyên girêdayî dubare dikin.
Ger di navbera risteyên ku dikevin heman dabeşkirinê de qeraxek hebe, ne dijwar e ku meriv di grafê de çerxek xerîb bibîne, ku di grafek dupartî de bi berfirehî tê zanîn (û pir eşkere) ne gengaz e. Wekî din, me dabeşek rast heye, ku tê vê wateyê ku graf dupartî ye.
Bi gelemperî, ev algorîtma bi kar tê pêkanîn an . Di zimanên mecbûrî de, lêgerîna yekem-kûr bi gelemperî tête bikar anîn ji ber ku ew hinekî hêsan e û ne hewceyî strukturên daneya zêde ye. Min di heman demê de lêgerîna pêşîn-kûrahî hilbijart ji ber ku ew kevneşoptir e.
Bi vî awayî, em gihîştin plana jêrîn. Em bi karanîna lêgerîna yekem-kûrahî ve lûtkeyên grafîkê dişopînin û parveyan ji wan re vediqetînin, dema ku em li ser peravê diherikin hejmara parvekirinê diguhezînin. Ger em hewl bidin ku pareyek bi vekêşek ku ji berê ve parveyek jê hatî veqetandin veqetînin, em dikarin bi ewlehî bibêjin ku graf ne dupartî ye. Wexta ku ji hemî risteyan parek tê veqetandin û me li hemî keviyan nihêrî, me dabeşek baş heye.
Paqijiya hesaban
Li Heskîfê em texmîn dikin ku hemî hesab in pak. Lêbelê, ger ev bi rastî wusa bûya, me çu rê tune ku em tiştek li ser ekranê çap bikin. Qet, pak hesabên ew qas tembel in ku yek tune pak sedemên hesabkirina tiştekî. Hemî hesabên ku di bernameyê de diqewimin bi rengek bi zorê têne kirin "nepaqij" monad IO.
Monad rêyek e ku meriv bi hesaban re temsîl dike bandorên li Heskîfê. Ravekirina ka ew çawa dixebitin li derveyî çarçoweya vê postê ye. Danasînek baş û zelal dikare bi Englishngilîzî were xwendin .
Li vir ez dixwazim destnîşan bikim ku dema ku hin monad, wekî IO, bi sêrbaziya berhevkarê têne bicîh kirin, hema hemî yên din di nermalavê de têne bicîh kirin û hemî hesabên di wan de paqij in.
Gelek bandor hene û her yek monadek xwe heye. Ev teoriyek pir xurt û xweşik e: hemî monad heman navbeynkariyê pêk tînin. Em ê li ser sê monadên jêrîn biaxivin:
- An ea hesabek e ku nirxek tîpa a vedigerîne an jî îstîsnayek ji tîpa e derdixe. Tevgera vê monadê pir dişibihe îstîsnayên di zimanên fermanî de: xeletî dikarin werin girtin an derbas bibin. Cûdahiya sereke ev e ku monad bi tevahî bi mantiqî di pirtûkxaneya standard a Haskell de tête bicîh kirin, dema ku zimanên mecbûrî bi gelemperî mekanîzmayên pergala xebitandinê bikar tînin.
- Dewleta sa hesabek e ku nirxek celeb a vedigerîne û gihîştina rewşa guhêrbar a celeb s heye.
- Dibe ku a. The Maybe monad hesabek ku dikare di her kêliyê de bi vegerandina Tiştek were qut kirin diyar dike. Lêbelê, em ê li ser pêkanîna çîna MonadPlus ji bo celebê Maybe biaxivin, ku bandora berevajî îfade dike: ew hesabek e ku bi vegerandina nirxek taybetî di her kêliyê de dikare were qut kirin.
Pêkanîna algorîtmayê
Du cureyên daneyê yên me hene, Graf a û Bigraph ab, ya yekem grafikên bi vertîkên ku bi nirxên tîpa a ve hatine nîşankirin, û ya duyemîn grafikên dupartî yên bi berikên milê çepê yên ku bi nirxên celeb a û rast hatine nîşankirin temsîl dike. -berikên alî yên ku bi nirxên cureya b hatine nîşankirin.
Ev celeb ji pirtûkxaneya Alga ne. Alga ji bo grafikên dupartî yên nederhênerî nûneriyek nîne. Min cureyên bi vî rengî ji bo zelaliyê çêkir.
Di heman demê de em ê hewceyê fonksiyonên alîkar ên bi îmzeyên jêrîn jî bibin:
-- Список соседей данной вершины.
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)Meriv hêsan e ku meriv bibîne ku heke di dema lêgerîna yekem-kûrahî de me qeraxek nakokî dît, çerxa xerîb li ser stûna vegerê ye. Ji ber vê yekê, ji bo vegerandina wê, pêdivî ye ku em her tiştî ji stûna vegerê heya bûyera yekem a vertîka paşîn qut bikin.
Em lêgerîna yekem-kûrahiyê bi domandina rêzek hevgirtî ya hejmarên parvekirinê ji bo her vertexê pêk tînin. Staka vegerandinê dê bixweber bi pêkanîna çîna Functor ya monadê ya ku me hilbijartiye were domandin: em ê tenê hewce bikin ku hemî lûtkeyan ji rêyê têxin nav encama ku ji fonksiyona vegerê vedigere.
Ramana min a yekem ev bû ku ez monadê an an jî bikar bînim, ku dixuye ku tam bandorên ku em hewce ne bicîh tîne. Pêkanîna yekem ku min nivîsand pir nêzî vê vebijarkê bû. Bi rastî, min li yek xalek pênc pêkanînên cûda hebûn û di dawiyê de li ser yeka din rûnişt.
Pêşîn, em hewce ne ku rêzek hevgirtî ya nasnameyên parvekirinê biparêzin - ev tiştek di derbarê Dewletê de ye. Ya duyemîn, dema ku pevçûnek tê dîtin divê em karibin rawestin. Ev dikare bibe Monad ji bo An, an MonadPlus ji bo Dibe. Cûdahiya sereke ev e ku An dikare nirxek vegerîne heke hesab nehatibe rawestandin, û Dibe ku di vê rewşê de tenê agahdariya li ser vê yekê vegerîne. Ji ber ku em ji bo serketinê ne hewceyî nirxek cihê ne (ew jixwe li Dewletê hatî hilanîn), em Belkî hildibijêrin. Û di dema ku em hewce ne ku bandorên du monadan bi hev re bikin, ew derdikevin , ku bi rastî van bandoran li hev dikin.
Çima min celebek wusa tevlihev hilbijart? Du sedem. Ya yekem, pêkanîn pir dişibihe mecbûriyetê. Ya duyemîn, pêdivî ye ku em di bûyera pevçûnê de dema ku ji vegerê vedigerin nirxa vegerê manîpule bikin da ku lûleya xerîb, ya ku di monadeya Maybe de pir hêsantir e were kirin.
Bi vî awayî em vê pêkanînê distînin.
{-# 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)
Bloka ku derê bingehîn a algorîtmê ye. Ez ê hewl bidim rave bikim ka çi di hundurê wê de diqewime.
- inVertex beşa lêgerîna kûrahî-yekemîn e ku em ji bo cara yekem serdana vertexê dikin. Li vir em jimareyek parvekirinê ji vertexê re destnîşan dikin û onEdge li ser hemî cîranan dimeşînin. Ev jî cihê ku em stûna bangê vedigirin e: heke msum nirxek vegerand, em vertex v-yê li wir dikişînin.
- onEdge ew beşê ye ku em lê digerin. Ji bo her perdeyek du caran tê gotin. Li vir em kontrol dikin ka verteksa li aliyê din hatiye serdan kirin, û ger na serdana wê bikin. Ger were serdan, em kontrol dikin ka derî nakokî ye. Ger wusa be, em nirxê vedigerînin - jortirîn stûna vegerê, ku wê hingê dê hemî berikên din piştî vegerê werin danîn.
- processVertex ji bo her vertexê kontrol dike ka ew hatiye serdan an na û heke na li Vertex-ê dimeşîne.
- dfs processVertex li ser hemî risteyan dimeşîne.
Navê pêger.
Dîroka peyva INLINE
Peyva INLINE ne di pêkanîna yekem a algorîtmê de bû; ew paşê xuya bû. Dema ku min hewl da ku bicîhkirinek çêtir bibînim, min dît ku guhertoya ne-INLINE li ser hin grafîkan bi baldarî hêdîtir bû. Bifikirin ku ji hêla semantîkî ve divê fonksiyon bi heman rengî bixebitin, ev yek ez pir şaş kirim. Zêdetir jî, li ser makîneyek din a bi guhertoyek cûda ya GHC-ê cûdahiyek berbiçav tune.
Piştî ku ez hefteyek xwendina derketina GHC Core derbas kir, min karî bi yek rêzek eşkere ya INLINE re pirsgirêk çareser bikim. Di hin xalan de di navbera GHC 8.4.4 û GHC 8.6.5 de optimîzator bi serê xwe kirina vê yekê rawestand.
Min hêvî nedikir ku di bernameya Haskell de bi qirêjiyek weha re rû bi rû bim. Lêbelê, îro jî, optimîzator carinan xeletiyan dikin, û karê me ye ku em nîşanan bidin wan. Mînakî, li vir em dizanin ku fonksiyon divê were xêz kirin ji ber ku ew di guhertoya fermanî de tê xêz kirin, û ev sedemek e ku meriv şîretek bide berhevkar.
Paşê çi qewimî?
Dûv re min algorîtmaya Hopcroft-Karp bi monadên din re bicîh kir, û ew dawiya bernameyê bû.
Bi saya Google Summer of Code, min di bernamesaziya fonksiyonel de ezmûnek pratîkî bi dest xist, ku ne tenê ji min re bû alîkar ku havîna paşîn li Jane Street bibim stajyerek (ez ne bawer im ku ev cîh çiqas di nav temaşevanên zanyar Habr de jî tê zanîn, lê ew yek e ji çend hindik ên ku hûn dikarin havînê beşdarî bernamesaziya fonksiyonel bibin), lê di heman demê de min bi cîhana ecêb a sepandina vê paradîgmayê di pratîkê de, ku ji ezmûna min a di zimanên kevneşopî de pir cûda ye, da nasandin.
Source: www.habr.com