PagÄjuÅ”ajÄ vasarÄ piedalÄ«jos - programma studentiem no Google. Katru gadu organizatori atlasa vairÄkus Open Source projektus, tostarp no tÄdÄm pazÄ«stamÄm organizÄcijÄm kÄ Šø . Google aicina studentus no visas pasaules strÄdÄt pie Å”iem projektiem.
KÄ Google Summer of Code 2019 dalÄ«bnieks es bibliotÄkÄ Ä«stenoju projektu ar organizÄciju , kas izstrÄdÄ Haskell valodu - vienu no slavenÄkajÄm funkcionÄlÄs programmÄÅ”anas valodÄm. Alga ir bibliotÄka, kas pÄrstÄv grafu attÄlojums HaskellÄ. To izmanto, piemÄram, in ā Github bibliotÄka, kas veido semantiskos kokus, zvanu un atkarÄ«bas grafikus, pamatojoties uz kodu, un var tos salÄ«dzinÄt. Mans projekts bija pievienot tipam droÅ”u attÄlojumu divpusÄjiem grafikiem un algoritmiem Å”im attÄlojumam.
Å ajÄ ierakstÄ es runÄÅ”u par algoritma ievieÅ”anu, lai pÄrbaudÄ«tu diagrammas divpusÄjo attiecÄ«bu Haskell. Lai gan algoritms ir viens no visvienkÄrÅ”Äkajiem, tÄ smuki ievieÅ”ana funkcionÄlÄ stilÄ man prasÄ«ja vairÄkas iterÄcijas un prasÄ«ja diezgan daudz darba. RezultÄtÄ es izvÄlÄjos ievieÅ”anu ar monÄdes transformatoriem.
Par sevi
Mani sauc Vasilijs Alferovs, esmu SanktpÄterburgas HSE ceturtÄ kursa students. IepriekÅ” emuÄrÄ es rakstÄ«ju Šø . Å obrÄ«d esmu praksÄ plkst NorvÄÄ£ijÄ, kur es strÄdÄju pie problÄmas pieejÄm . Manas intereses ietver parametrizÄtus algoritmus un funkcionÄlo programmÄÅ”anu.
Par algoritma ievieŔanu
priekÅ”vÄrds
Studenti, kas piedalÄs programmÄ, tiek ļoti aicinÄti rakstÄ«t emuÄrus. ViÅi man nodroÅ”inÄja platformu emuÄram . Å is raksts ir tulkojums , ko es tur jÅ«lijÄ uzrakstÄ«ju angļu valodÄ, ar Ä«su priekÅ”vÄrdu.
Pull Request ar attiecīgo kodu var atrast .
Par mana darba rezultÄtiem varat lasÄ«t (angļu valodÄ) .
Å is ieraksts ir paredzÄts, lai iepazÄ«stinÄtu lasÄ«tÄju ar funkcionÄlÄs programmÄÅ”anas pamatjÄdzieniem, lai gan es mÄÄ£inÄÅ”u atsaukt atmiÅÄ visus lietotos terminus, kad pienÄks laiks.
Grafiku divpusÄ«bas pÄrbaude
Algoritms grafa divpusÄ«bas pÄrbaudei parasti tiek dots kursÄ par algoritmiem kÄ viens no vienkÄrÅ”Äkajiem grafu algoritmiem. ViÅa ideja ir vienkÄrÅ”a: vispirms mÄs kaut kÄdÄ veidÄ ievietojam virsotnes kreisajÄ vai labajÄ daļÄ, un, kad tiek atrasta pretrunÄ«ga mala, mÄs apgalvojam, ka grafs nav divpusÄjs.
Nedaudz sÄ«kÄk: vispirms kreisajÄ daÄ¼Ä ievietojam kÄdu virsotni. AcÄ«mredzot visiem Ŕīs virsotnes kaimiÅiem jÄatrodas labajÄ daivÄ. TurklÄt visiem Ŕīs virsotnes kaimiÅu kaimiÅiem jÄatrodas kreisajÄ daivÄ utt. MÄs turpinÄm pieŔķirt virsotnÄm daļas, kamÄr savienotajÄ virsotnes komponentÄ, ar kuru sÄkÄm, joprojÄm ir virsotnes, kurÄm neesam pieŔķīruÅ”i kaimiÅus. PÄc tam mÄs atkÄrtojam Å”o darbÄ«bu visiem pievienotajiem komponentiem.
Ja starp virsotnÄm, kas ietilpst vienÄ nodalÄ«jumÄ, ir mala, grafÄ nav grÅ«ti atrast nepÄra ciklu, kas ir plaÅ”i pazÄ«stams (un diezgan acÄ«mredzami) divpusÄjÄ grafÄ. PretÄjÄ gadÄ«jumÄ mums ir pareizs nodalÄ«jums, kas nozÄ«mÄ, ka grafiks ir divpusÄjs.
Parasti Å”is algoritms tiek Ä«stenots, izmantojot vai . ObligÄtajÄs valodÄs parasti tiek izmantota pirmÄ dziļuma meklÄÅ”ana, jo tÄ ir nedaudz vienkÄrÅ”Äka un neprasa papildu datu struktÅ«ras. Es arÄ« izvÄlÄjos dziļuma meklÄÅ”anu, jo tÄ ir tradicionÄlÄka.
TÄdÄjÄdi mÄs nonÄcÄm pie Å”Ädas shÄmas. MÄs ŔķÄrsojam diagrammas virsotnes, izmantojot dziļuma meklÄÅ”anu, un pieŔķiram tÄm daļas, mainot daļas numuru, virzoties gar malu. Ja mÄs mÄÄ£inÄm pieŔķirt daļu virsotnei, kurai jau ir pieŔķirta daļa, mÄs varam droÅ”i teikt, ka grafs nav divpusÄjs. BrÄ«dÄ«, kad visÄm virsotnÄm ir pieŔķirta daļa un mÄs esam apskatÄ«juÅ”i visas malas, mums ir labs nodalÄ«jums.
AprÄÄ·inu tÄ«rÄ«ba
Haskell mÄs pieÅemam, ka visi aprÄÄ·ini ir tÄ«rs. TomÄr, ja tas tÄ bÅ«tu, mÄs nevarÄtu neko izdrukÄt uz ekrÄna. Pavisam, tÄ«rs aprÄÄ·ini ir tik slinki, ka nav neviena tÄ«rs iemesli kaut ko aprÄÄ·inÄt. Visi aprÄÄ·ini, kas notiek programmÄ, ir kaut kÄ spiesti "netÄ«rs" monÄde IO.
MonÄdes ir veids, kÄ attÄlot aprÄÄ·inus ietekmi HaskelÄ. IzskaidroÅ”ana, kÄ viÅi strÄdÄ, neietilpst Ŕīs ziÅas darbÄ«bas jomÄ. Labu un skaidru aprakstu var izlasÄ«t angļu valodÄ .
Å eit es gribu norÄdÄ«t, ka, lai gan dažas monÄdes, piemÄram, IO, tiek ieviestas ar kompilatoru maÄ£iju, gandrÄ«z visas pÄrÄjÄs ir ieviestas programmatÅ«rÄ un visi aprÄÄ·ini tajÄs ir tÄ«ri.
Ir daudz efektu, un katram ir sava monÄde. Å Ä« ir ļoti spÄcÄ«ga un skaista teorija: visas monÄdes Ä«steno vienu un to paÅ”u saskarni. MÄs runÄsim par Å”ÄdÄm trim monÄdÄm:
- Vai nu ea ir aprÄÄ·ins, kas atgriež a tipa vÄrtÄ«bu vai izmet e tipa izÅÄmumu. Å Ä«s monÄdes darbÄ«ba ir ļoti lÄ«dzÄ«ga izÅÄmumu apstrÄdei obligÄtajÄs valodÄs: kļūdas var tikt pieÄ·ertas vai nodotas tÄlÄk. GalvenÄ atŔķirÄ«ba ir tÄ, ka monÄde ir pilnÄ«bÄ loÄ£iski ieviesta Haskell standarta bibliotÄkÄ, savukÄrt obligÄtajÄs valodÄs parasti tiek izmantoti operÄtÄjsistÄmas mehÄnismi.
- StÄvoklis sa ir aprÄÄ·ins, kas atgriež a tipa vÄrtÄ«bu un kuram ir piekļuve mainÄ«gam s tipa stÄvoklim.
- VarbÅ«t a. VarbÅ«t monÄde izsaka aprÄÄ·inu, ko jebkurÄ brÄ«dÄ« var pÄrtraukt, atgriežot neko. TomÄr mÄs runÄsim par MonadPlus klases ievieÅ”anu Maybe tipam, kas pauž pretÄju efektu: tas ir aprÄÄ·ins, kuru jebkurÄ brÄ«dÄ« var pÄrtraukt, atgriežot noteiktu vÄrtÄ«bu.
Algoritma realizÄcija
Mums ir divi datu tipi, Graph a un Bigraph ab, no kuriem pirmais attÄlo grafikus ar virsotnÄm, kas apzÄ«mÄtas ar a tipa vÄrtÄ«bÄm, bet otrais attÄlo divpusÄjus grafikus ar kreisÄs puses virsotnÄm, kas apzÄ«mÄtas ar a tipa un labÄs puses vÄrtÄ«bÄm. - sÄnu virsotnes, kas apzÄ«mÄtas ar b tipa vÄrtÄ«bÄm.
Tie nav veidi no Algas bibliotÄkas. Alga nav attÄlojuma nevirzÄ«tiem divpusÄjiem grafikiem. SkaidrÄ«bas labad izgatavoju Å”Ädus tipus.
Mums bÅ«s nepiecieÅ”amas arÄ« palÄ«gfunkcijas ar Å”Ädiem parakstiem:
-- Š”ŠæŠøŃŠ¾Šŗ ŃŠ¾ŃŠµŠ“ŠµŠ¹ Š“Š°Š½Š½Š¾Š¹ Š²ŠµŃŃŠøŠ½Ń.
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)Ir viegli redzÄt, ka, ja dziļuma pirmÄs meklÄÅ”anas laikÄ mÄs atradÄm konfliktÄjoÅ”u malu, nepÄra cikls atrodas rekursijas steka augÅ”pusÄ. TÄdÄjÄdi, lai to atjaunotu, mums ir jÄnogriež viss, sÄkot no rekursijas steka lÄ«dz pirmajai pÄdÄjÄs virsotnes gadÄ«jumam.
MÄs Ä«stenojam dziļuma meklÄÅ”anu, katrai virsotnei uzturot asociatÄ«vu koplietoÅ”anas numuru masÄ«vu. Rekursijas kaudze tiks automÄtiski uzturÄta, ievieÅ”ot mÅ«su izvÄlÄtÄs monÄdes Functor klasi: mums bÅ«s tikai jÄievieto visas virsotnes no ceļa rezultÄtos, kas atgriezts no rekursÄ«vÄs funkcijas.
Mana pirmÄ ideja bija izmantot vai nu monÄdi, kas, Ŕķiet, Ä«steno tieÅ”i mums nepiecieÅ”amos efektus. PirmÄ ievieÅ”ana, ko es uzrakstÄ«ju, bija ļoti tuvu Å”ai opcijai. PatiesÄ«bÄ man vienÄ brÄ«dÄ« bija piecas dažÄdas ievieÅ”anas, un galu galÄ es izvÄlÄjos citu.
PirmkÄrt, mums ir jÄsaglabÄ asociatÄ«vs akciju identifikatoru masÄ«vs ā tas ir kaut kas par valsti. OtrkÄrt, mums ir jÄspÄj apstÄties, kad tiek atklÄts konflikts. Tas var bÅ«t vai nu Monad for Any, vai MonadPlus for Maybe. GalvenÄ atŔķirÄ«ba ir tÄ, ka vai nu var atgriezt vÄrtÄ«bu, ja aprÄÄ·ins nav apturÄts, un Maybe Å”ajÄ gadÄ«jumÄ atgriež tikai informÄciju par to. TÄ kÄ panÄkumiem nav nepiecieÅ”ama atseviŔķa vÄrtÄ«ba (tÄ jau ir saglabÄta Å”tatÄ), mÄs izvÄlamies VarbÅ«t. Un tajÄ brÄ«dÄ«, kad mums ir jÄapvieno divu monÄžu ietekme, tÄs iznÄk , kas precÄ«zi apvieno Å”os efektus.
KÄpÄc es izvÄlÄjos tik sarežģītu veidu? Divi iemesli. PirmkÄrt, Ä«stenoÅ”ana izrÄdÄs ļoti lÄ«dzÄ«ga imperatÄ«vai. OtrkÄrt, mums ir jÄmanipulÄ ar atgrieÅ”anas vÄrtÄ«bu konflikta gadÄ«jumÄ, atgriežoties no rekursijas, lai atjaunotu nepÄra cilpu, kas ir daudz vieglÄk izdarÄms Maybe monÄdÄ.
TÄdÄjÄdi mÄs iegÅ«stam Å”o ievieÅ”anu.
{-# 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)
Kur bloks ir algoritma kodols. MÄÄ£inÄÅ”u paskaidrot, kas tajÄ iekÅ”Ä notiek.
- inVertex ir dziļuma pirmÄs meklÄÅ”anas daļa, kurÄ mÄs pirmo reizi apmeklÄjam virsotni. Å eit mÄs pieŔķiram virsotnei koplietoÅ”anas numuru un palaižam onEdge uz visiem kaimiÅiem. Å eit mÄs arÄ« atjaunojam izsaukuma steku: ja msum atgrieza vÄrtÄ«bu, mÄs tur nospiežam virsotni v.
- onEdge ir daļa, kurÄ mÄs apmeklÄjam malu. Katrai malai to sauc divreiz. Å eit mÄs pÄrbaudÄm, vai virsotne otrÄ pusÄ ir apmeklÄta, un apmeklÄjiet to, ja nÄ. Ja apmeklÄjat, mÄs pÄrbaudÄm, vai mala nav konfliktÄjoÅ”a. Ja tÄ ir, mÄs atgriežam vÄrtÄ«bu - paÅ”u rekursijas kaudzes augÅ”daļu, kur pÄc atgrieÅ”anÄs tiks novietotas visas pÄrÄjÄs virsotnes.
- processVertex pÄrbauda katrai virsotnei, vai tÄ ir apmeklÄta, un palaiž tajÄ inVertex, ja nÄ.
- dfs palaiž processVertex visÄs virsotnÄs.
Tas ir viss.
VÄrda INLINE vÄsture
VÄrds INLINE nebija pirmajÄ algoritma realizÄcijÄ, tas parÄdÄ«jÄs vÄlÄk. Kad es mÄÄ£inÄju atrast labÄku ievieÅ”anu, es atklÄju, ka versija, kas nav INLINE, dažos grafikos ir ievÄrojami lÄnÄka. Å emot vÄrÄ, ka semantiski funkcijÄm jÄdarbojas vienÄdi, tas mani ļoti pÄrsteidza. VÄl dÄ«vainÄk, citÄ maŔīnÄ ar citu GHC versiju nebija manÄmas atŔķirÄ«bas.
PÄc tam, kad pavadÄ«ju nedÄļu, lasot GHC Core izvadi, es varÄju novÄrst problÄmu, izmantojot vienu INLINE rindiÅu. KÄdÄ brÄ«dÄ« starp GHC 8.4.4 un GHC 8.6.5 optimizÄtÄjs pÄrtrauca to darÄ«t pats.
Es nebiju gaidÄ«jis, ka Haskell programmÄÅ”anas laikÄ sastapsies ar tik netÄ«rumiem. TomÄr pat mÅ«sdienÄs optimizÄtÄji dažreiz pieļauj kļūdas, un mÅ«su uzdevums ir dot viÅiem padomus. PiemÄram, Å”eit mÄs zinÄm, ka funkcijai jÄbÅ«t iekļautai, jo tÄ ir iekļauta obligÄtajÄ versijÄ, un tas ir iemesls, lai sniegtu kompilatoram mÄjienu.
Kas notika tÄlÄk?
Tad es ieviesu Hopcroft-Karp algoritmu ar citÄm monÄdÄm, un ar to arÄ« programma beidzÄs.
Pateicoties Google Summer of Code, es ieguvu praktisku pieredzi funkcionÄlajÄ programmÄÅ”anÄ, kas man ne tikai palÄ«dzÄja nÄkamajÄ vasarÄ iegÅ«t praksi Džeinas ielÄ (es neesmu pÄrliecinÄts, cik labi Ŕī vieta ir pazÄ«stama pat Habra zinoÅ”Äs auditorijas vidÅ«, bet tÄ ir viena no retajiem, kur var nodarboties ar funkcionÄlo programmÄÅ”anu), bet arÄ« iepazÄ«stinÄja mani ar Ŕīs paradigmas pielietoÅ”anas brÄ«niŔķīgo pasauli, kas bÅ«tiski atŔķiras no manas pieredzes tradicionÄlajÄs valodÄs.
Avots: www.habr.com