Sa miaging ting-init miapil ko - usa ka programa alang sa mga estudyante gikan sa Google. Matag tuig, ang mga tig-organisar mopili ug daghang mga proyekto sa Open Source, lakip ang gikan sa mga iladong organisasyon sama sa и . Gidapit sa Google ang mga estudyante gikan sa tibuok kalibutan sa pagtrabaho niini nga mga proyekto.
Isip usa ka partisipante sa Google Summer of Code 2019, naghimo ko og proyekto sulod sa library uban sa organisasyon , nga nagpalambo sa Haskell nga pinulongan - usa sa labing inila nga functional programming language. Ang Alga usa ka librarya nga nagrepresentar representasyon alang sa mga graph sa Haskell. Kini gigamit, pananglitan, sa - usa ka librarya sa Github nga nagtukod og mga semantic tree, tawag ug dependency graphs base sa code ug mahimong itandi kini. Ang akong proyekto mao ang pagdugang ug tipo nga luwas nga representasyon para sa bipartite nga mga graph ug mga algorithm alang niana nga representasyon.
Sa kini nga post maghisgot ako bahin sa akong pagpatuman sa usa ka algorithm alang sa pagsusi sa usa ka graph alang sa bipartiteness sa Haskell. Bisan kung ang algorithm usa sa labing sukaranan, ang pag-implementar niini nga matahum sa usa ka praktikal nga istilo nagdala kanako daghang mga pag-uli ug nanginahanglan daghang trabaho. Ingon usa ka sangputanan, gihusay nako ang usa ka pagpatuman sa mga transformer sa monad.
Mahitungod sa akong kaugalingon
Ang akong ngalan mao si Vasily Alferov, ako usa ka ikaupat nga tuig nga estudyante sa St. Petersburg HSE. Kaniadto sa blog nga akong gisulat и . Karon naa ko sa internship sa sa Norway, diin ako nagtrabaho sa mga pamaagi sa problema . Ang akong mga interes naglakip sa parameterized algorithms ug functional programming.
Mahitungod sa pagpatuman sa algorithm
Pasiuna
Ang mga estudyante nga miapil sa programa kusganong gidasig sa pag-blog. Gihatagan ko nila og plataporma alang sa blog . Kini nga artikulo usa ka hubad , gisulat nako didto sa Hulyo sa English, nga adunay mubo nga pasiuna.
Ang Paghangyo sa Pagbitad nga adunay code nga gipangutana makit-an .
Makabasa ka bahin sa mga resulta sa akong trabaho (sa English) .
Kini nga post gituyo aron mapamilyar ang magbabasa sa mga batakang konsepto sa functional programming, bisan kung sulayan nako nga hinumdoman ang tanan nga mga termino nga gigamit kung moabut ang oras.
Pagsusi sa mga graph alang sa bipartiteness
Usa ka algorithm sa pagsusi sa usa ka graph alang sa bipartiteness kasagarang gihatag sa usa ka kurso sa mga algorithm isip usa sa pinakasimple nga graph algorithm. Ang iyang ideya prangka: una sa usa ka paagi gibutang namon ang mga vertices sa wala o tuo nga bahin, ug kung makit-an ang usa ka nagkasumpaki nga sulud, among gipahayag nga ang graph dili bipartite.
Usa ka gamay nga detalye: una among gibutang ang pipila ka vertex sa wala nga bahin. Dayag nga ang tanan nga mga silingan niini nga vertex kinahanglan nga nahimutang sa tuo nga lobe. Dugang pa, ang tanan nga mga silingan sa mga silingan niini nga vertex kinahanglan nga nahimutang sa wala nga lobe, ug uban pa. Nagpadayon kami sa pag-assign sa mga bahin sa mga vertex basta adunay mga vertex sa konektado nga sangkap sa vertex nga among gisugdan nga wala pa namon gi-assign sa mga silingan. Gisubli namon kini nga aksyon alang sa tanan nga konektado nga mga sangkap.
Kung adunay usa ka sulud tali sa mga vertices nga nahulog sa parehas nga partisyon, dili lisud ang pagpangita sa usa ka katingad-an nga siklo sa graph, nga nahibal-an sa kadaghanan (ug klaro kaayo) nga imposible sa usa ka bipartite graph. Kung dili, kami adunay husto nga partisyon, nga nagpasabut nga ang graph usa ka bipartite.
Kasagaran, kini nga algorithm gipatuman gamit ang o . Sa imperative nga mga lengguwahe, ang depth-first nga pagpangita kasagarang gigamit tungod kay kini mas simple ug wala magkinahanglan og dugang nga mga istruktura sa datos. Gipili sab nako ang depth-first search kay mas tradisyonal.
Busa, nakaabot kami sa mosunod nga laraw. Among gisubay ang mga vertices sa graph gamit ang depth-first search ug nag-assign sa mga bahin niini, nag-ilis sa gidaghanon sa share samtang naglihok kami sa daplin. Kung kita mosulay sa pag-assign sa usa ka bahin sa usa ka vertex nga adunay bahin nga gi-assign, kita luwas nga makaingon nga ang graph dili bipartite. Sa higayon nga ang tanan nga mga vertices gihatagan usa ka bahin ug among gitan-aw ang tanan nga mga sulud, kami adunay usa ka maayo nga partisyon.
Kaputli sa mga kalkulasyon
Sa Haskell atong gihunahuna nga ang tanan nga mga kalkulasyon limpyo. Bisan pa, kung kini tinuod nga kaso, wala kami'y paagi sa pag-imprinta bisan unsa sa screen. Sa tanan, limpyo tapulan kaayo ang mga kalkulasyon nga walay usa limpyo mga rason sa pagkalkulo sa usa ka butang. Ang tanan nga mga kalkulasyon nga nahitabo sa programa sa usa ka paagi napugos sa "hugaw" monad IO.
Ang mga monad usa ka paagi sa pagrepresentar sa mga kalkulasyon mga epekto sa Haskell. Ang pagpatin-aw kon sa unsang paagi sila nagtrabaho lapas pa sa sakup niini nga post. Ang usa ka maayo ug tin-aw nga paghulagway mabasa sa English .
Dinhi gusto nakong ipunting nga samtang ang pipila ka mga monad, sama sa IO, gipatuman pinaagi sa compiler magic, halos tanan nga uban gipatuman sa software ug ang tanan nga mga kalkulasyon niini puro.
Adunay daghang mga epekto ug ang matag usa adunay kaugalingon nga monad. Kini usa ka kusgan ug matahum nga teorya: ang tanan nga monad nagpatuman sa parehas nga interface. Atong hisgotan ang mosunod nga tulo ka monad:
- Ang ea usa ka kalkulasyon nga nagbalik sa usa ka bili sa tipo a o naghulog ug eksepsiyon sa tipo nga e. Ang pamatasan sa kini nga monad parehas kaayo sa pagdumala sa eksepsiyon sa mga kinahanglanon nga sinultian: ang mga sayup mahimong makuha o ipasa. Ang nag-unang kalainan mao nga ang monad hingpit nga lohikal nga gipatuman sa standard nga librarya sa Haskell, samtang ang mga kinahanglanon nga mga pinulongan kasagarang naggamit sa mga mekanismo sa operating system.
- Ang estado sa usa ka kalkulasyon nga nagbalik sa usa ka kantidad sa tipo a ug adunay access sa mutable nga kahimtang sa tipo s.
- Tingali a. Ang Maybe monad nagpahayag ug computation nga mahimong mabalda bisan unsang orasa pinaagi sa pagbalik sa Wala. Bisan pa, maghisgot kami bahin sa pagpatuman sa klase sa MonadPlus alang sa tipo nga Tingali, nga nagpahayag sa kaatbang nga epekto: kini usa ka kalkulasyon nga mahimong mabalda bisan unsang oras pinaagi sa pagbalik sa usa ka piho nga kantidad.
Pagpatuman sa algorithm
Adunay kami duha ka mga tipo sa datos, Graph a ug Bigraph ab, ang una niini nagrepresentar sa mga graph nga adunay mga vertices nga gimarkahan sa mga kantidad sa type a, ug ang ikaduha nagrepresentar sa mga bipartite graph nga adunay wala nga kilid nga vertices nga gimarkahan sa mga kantidad sa tipo a ug tuo. -side vertices nga gimarkahan sa mga kantidad sa tipo b.
Dili kini mga tipo gikan sa librarya sa Alga. Ang Alga walay representasyon alang sa dili direkta nga bipartite graphs. Gihimo nako ang mga tipo nga sama niini para sa katin-awan.
Kinahanglan usab namon ang mga function sa katabang nga adunay mga mosunud nga pirma:
-- Список соседей данной вершины.
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)Sayon nga makita nga kung sa panahon sa una nga giladmon nga pagpangita nakit-an namon ang usa ka nagkasumpaki nga sulud, ang katingad-an nga siklo nahimutang sa ibabaw sa recursion stack. Busa, aron mapasig-uli kini, kinahanglan natong putlon ang tanan gikan sa recursion stack hangtod sa unang panghitabo sa kataposang vertex.
Gipatuman namo ang depth-first search pinaagi sa pagmintinar sa usa ka associative array sa share number para sa matag vertex. Ang recursion stack awtomatik nga mamentinar pinaagi sa pagpatuman sa Functor nga klase sa monad nga atong gipili: kinahanglan lang natong ibutang ang tanang vertices gikan sa dalan ngadto sa resulta nga gibalik gikan sa recursive function.
Ang una nakong ideya mao ang paggamit sa Either monad, nga morag nagpatuman sa eksakto nga mga epekto nga atong gikinahanglan. Ang una nga pagpatuman nga akong gisulat hapit kaayo sa kini nga kapilian. Sa tinuud, aduna akoy lima ka lainlaing mga pagpatuman sa usa ka punto ug sa kadugayan nahusay sa lain.
Una, kinahanglan natong ipadayon ang usa ka associative array sa share identifiers - kini usa ka butang mahitungod sa Estado. Ikaduha, kinahanglan nga makahunong kita kung adunay namatikdan nga panagbangi. Mahimo kini nga Monad alang sa Bisan kinsa, o MonadPlus alang sa Tingali. Ang nag-unang kalainan mao nga ang Bisan kinsa makabalik sa usa ka bili kung ang kalkulasyon wala mahunong, ug Tingali nagbalik lamang sa impormasyon mahitungod niini sa niini nga kaso. Tungod kay wala kami magkinahanglan og usa ka bulag nga bili alang sa kalampusan (kini gitipigan na sa Estado), gipili namo ang Tingali. Ug sa higayon nga kinahanglan naton nga i-combine ang mga epekto sa duha ka monad, mogawas sila , nga tukma nga naghiusa niini nga mga epekto.
Ngano nga gipili nako ang ingon ka komplikado nga tipo? Duha ka rason. Una, ang pagpatuman nahimo nga parehas kaayo sa imperative. Ikaduha, kinahanglan naton nga manipulahon ang pagbalik nga kantidad kung adunay panagbangi kung mobalik gikan sa recursion aron mapasig-uli ang katingad-an nga loop, nga labi kadali buhaton sa Tingali monad.
Sa ingon atong makuha kini nga pagpatuman.
{-# 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)
Ang diin block mao ang kinauyokan sa algorithm. Akong sulayan nga ipasabut kung unsa ang nahitabo sa sulod niini.
- Ang inVertex mao ang bahin sa depth-first search diin atong bisitahan ang vertex sa unang higayon. Dinhi naghatag kami usa ka numero sa bahin sa vertex ug gipadagan ang onEdge sa tanan nga mga silingan. Dinhi usab nato ibalik ang call stack: kung ang msum mibalik ug bili, atong iduso ang vertex v didto.
- Ang onEdge mao ang bahin diin kita mobisita sa daplin. Gitawag kini kaduha alang sa matag sidsid. Dinhi atong susihon kung ang vertex sa pikas nga bahin nabisitahan, ug bisitaha kini kung wala. Kung gibisitahan, among susihon kung nagkasumpaki ba ang ngilit. Kung mao, ibalik namon ang kantidad - ang pinakataas nga bahin sa recursion stack, diin ang tanan nga uban pang mga vertices ibutang sa pagbalik.
- Ang processVertex nagsusi sa matag vertex kung nabisita na ba kini ug nagpadagan sa inVertex niini kung wala.
- Ang dfs nagpadagan sa processVertex sa tanang vertices.
Mao ra.
Kasaysayan sa pulong INLINE
Ang pulong INLINE wala sa una nga pagpatuman sa algorithm; kini nagpakita sa ulahi. Sa diha nga ako misulay sa pagpangita sa usa ka mas maayo nga pagpatuman, akong nakita nga ang non-INLINE nga bersyon mao ang mamatikdan nga hinay sa pipila graphs. Sa pagkonsiderar nga ang semantically ang mga gimbuhaton kinahanglan nga molihok nga parehas, kini nakapatingala kaayo kanako. Bisan ang estranghero, sa lain nga makina nga adunay lahi nga bersyon sa GHC wala’y nakita nga kalainan.
Human sa paggahin og usa ka semana sa pagbasa sa GHC Core nga output, ako nakahimo sa pag-ayo sa problema sa usa ka linya sa dayag nga INLINE. Sa usa ka punto tali sa GHC 8.4.4 ug GHC 8.6.5 ang optimizer mihunong sa pagbuhat niini sa iyang kaugalingon.
Wala ko magdahom nga makasugat og ingon nga hugaw sa Haskell programming. Bisan pa, bisan karon, ang mga optimizer usahay masayop, ug among trabaho ang paghatag kanila og mga pahiwatig. Pananglitan, dinhi nahibal-an namon nga ang function kinahanglan nga inlined tungod kay kini na-inline sa imperative nga bersyon, ug kini usa ka rason aron mahatagan ang compiler og usa ka timaan.
Unsay sunod nga nahitabo?
Unya gipatuman nako ang algorithm sa Hopcroft-Karp sa ubang mga monad, ug kana ang katapusan sa programa.
Salamat sa Google Summer of Code, nakabaton kog praktikal nga kasinatian sa functional programming, nga dili lang nakatabang nako nga makakuha og internship sa Jane Street pagkasunod ting-init (Dili ko sigurado kung unsa ka ilado kining dapita bisan sa mga batid nga mamiminaw ni Habr, apan usa kini sa pipila diin mahimo nimo ang ting-init aron moapil sa functional programming), apan gipaila usab ako sa nindot nga kalibutan sa pagpadapat niini nga paradigm sa praktis, nga lahi kaayo sa akong kasinatian sa tradisyonal nga mga pinulongan.
Source: www.habr.com