Lehlabuleng le fetileng ke ile ka nka karolo - lenaneo bakeng sa baithuti ba Google. Selemo se seng le se seng, bahlophisi ba khetha merero e mengata ea Open Source, ho kenyelletsa le mekhatlo e tsebahalang joalo ka и . Google e mema liithuti ho tsoa lefats'eng lohle ho sebetsa mesebetsing ena.
Ha ke le karolo ho Google Summer of Code 2019, ke entse projeke ka har'a laeborari le mokhatlo , e ntseng e ntlafatsa puo ea Haskell - e 'ngoe ea lipuo tse tummeng ka ho fetisisa tse sebetsang. Alga ke laebrari e emelang boemeli ba li-graph ho Haskell. E sebelisoa, ka mohlala, ka - laebrari ea Github e hahang lifate tsa semantic, ho letsetsa le ho itšetleha ka li-graph tse thehiloeng ho khoutu 'me li ka li bapisa. Morero oa ka e ne e le ho kenyelletsa setšoantšo se bolokehileng bakeng sa li-graph tsa bipartite le li-algorithms bakeng sa kemelo eo.
Ka poso ena ke tla bua ka ts'ebetsong ea ka ea algorithm bakeng sa ho hlahloba graph bakeng sa bipartiteness ho Haskell. Leha algorithm e le e 'ngoe ea tse bohlokoa ka ho fetesisa, ho e kenya tšebetsong hantle ka mokhoa o sebetsang ho nkile makhetlo a' maloa mme ho hloka mosebetsi o mongata. Ka lebaka leo, ke ile ka lula ka ts'ebetsong le li-transformer tsa monad.
Ka 'na
Lebitso la ka ke Vasily Alferov, ke seithuti sa selemo sa bone sa St. Petersburg HSE. Pejana ho blog ke ile ka ngola и . Hona joale ke ho internship ho Norway, moo ke sebetsanang le mekhoa ea ho rarolla bothata . Lintho tseo ke li ratang li kenyelletsa li-algorithms tsa parameterized le mananeo a sebetsang.
Mabapi le ts'ebetsong ea algorithm
Tlhaloso
Baithuti ba nkang karolo lenaneong ba khothaletsoa ka matla ho etsa blog. Ba ile ba mpha sethala sa blog . Sengoliloeng sena ke phetolelo , e ngotsoeng ke ’na moo ka July ka Senyesemane, ka selelekela se sekhutšoanyane.
Kopa Kopo e nang le khoutu e potsoeng e ka fumanoa .
U ka bala ka liphetho tsa mosebetsi oa ka (ka Senyesemane) .
Poso ena e reretsoe ho tloaelana le 'mali ka likhopolo tsa motheo lenaneong le sebetsang, le hoja ke tla leka ho hopola mantsoe ohle a sebelisoang ha nako e fihla.
Ho hlahloba li-graph bakeng sa bipartiteness
Algorithm bakeng sa ho hlahloba kerafo bakeng sa bipartiteness hangata e fanoa thupelong ea algorithms e le e 'ngoe ea meralo e bonolo ea kerafo. Maikutlo a hae a hlakile: pele ka tsela e itseng re beha li-vertices ka lehlakoreng le letšehali kapa le letona, 'me ha ho fumanoa moeli o hanyetsanang, re tiisa hore graph ha e kopane.
Lintlha tse ling: pele re beha vertex karolong e ka letsohong le letšehali. Ho hlakile hore baahelani bohle ba vertex ena ba tlameha ho robala ka lobe e nepahetseng. Ho feta moo, baahelani bohle ba baahelani ba vertex ena ba tlameha ho robala ka lehlakoreng le letšehali, joalo-joalo. Re tsoela pele ho abela li-share ho li-vertices ha feela ho ntse ho e-na le li-vertices karolong e hokahaneng ea vertex eo re qalileng ka eona eo re sa kang ra e abela baahelani. Ebe re pheta ketso ena bakeng sa likarolo tsohle tse hokahaneng.
Haeba ho na le moeli pakeng tsa li-vertices tse oelang karohanong e le 'ngoe, ha ho thata ho fumana potoloho e makatsang ka har'a kerafo, e tsejoang haholo ('me ho hlakile) e ke keng ea khoneha ho graph ea bipartite. Ho seng joalo, re na le karohano e nepahetseng, ho bolelang hore graph ke bipartite.
Ka tloaelo, algorithm ena e sebelisoa ho sebelisoa kapa . Lipuong tsa bohlokoa, patlisiso e tebileng ea pele e atisa ho sebelisoa kaha e bonolo haholoanyane 'me ha e hloke lisebelisoa tse eketsehileng tsa data. Ke boetse ke khethile lipatlisiso tse tebileng-pele kaha e le tsa setso.
Kahoo, re fihlile morerong o latelang. Re haola le li-vertices tsa kerafo re sebelisa lipatlisiso tse tebileng-pele 'me re li abela likarolo, re fetola palo ea kabelo ha re ntse re tsamaea moeling. Haeba re leka ho abela karolo ho vertex e seng e ntse e e-na le karolo e abetsoeng, re ka bua ka mokhoa o sireletsehileng hore graph ha e kopane. Nako eo li-vertices tsohle li abetsoeng karolo 'me re se re shebile mahlakoreng ohle, re na le karohano e ntle.
Bohloeki ba lipalo
Ho Haskell re nka hore lipalo tsohle li hloekile. Leha ho le joalo, haeba ho ne ho hlile ho le joalo, re ka be re se na mokhoa oa ho hatisa letho skrineng. Ho hang, hloekile lipalo li botsoa hoo ho seng letho hloekile mabaka a ho bala ntho e itseng. Lipalo tsohle tse hlahang lenaneong li qobelloa ka tsela e itseng "sa hloeka" mona IO.
Monads ke mokhoa oa ho emela lipalo ka liphello ho Haskell. Ho hlalosa hore na ba sebetsa joang ho feta sebaka sa poso ena. Tlhaloso e ntle le e hlakileng e ka baloa ka Senyesemane .
Mona ke batla ho supa hore le hoja li-monads tse ling, tse kang IO, li kenngoa ts'ebetsong ka boselamose ba compiler, hoo e batlang e le tse ling kaofela li kenngoa ts'ebetsong 'me lipalo tsohle ho tsona li hloekile.
Ho na le litlamorao tse ngata mme e 'ngoe le e' ngoe e na le monad ea eona. Ena ke khopolo e matla haholo ebile e ntle: li-monads tsohle li sebelisa sebopeho se tšoanang. Re tla bua ka li-monads tse tharo tse latelang:
- Ea ke palo e khutlisetsang boleng ba mofuta oa a kapa e etsang mokhelo oa mofuta oa e. Boitšoaro ba monad bo ts'oana haholo le ho sebetsana le mokhelo ka lipuo tsa bohlokoa: liphoso li ka ts'oaroa kapa tsa fetisoa. Phapang e kholo ke hore monad e sebelisoa ka mokhoa o hlakileng laebraring e tloaelehileng ea Haskell, athe lipuo tsa bohlokoa hangata li sebelisa mekhoa ea ts'ebetso.
- State sa ke palo e khutlisang boleng ba mofuta oa a mme e na le phihlello ea maemo a feto-fetohang a mofuta oa s.
- Mohlomong a. The Maybe monad e hlahisa khomphutha e ka sitisoang ka nako efe kapa efe ka ho khutlisa letho. Leha ho le joalo, re tla bua ka ts'ebetsong ea sehlopha sa MonadPlus bakeng sa mofuta oa Mohlomong, o hlalosang phello e fapaneng: ke palo e ka sitisoang ka nako leha e le efe ka ho khutlisetsa boleng bo itseng.
Ts'ebetsong ea algorithm
Re na le mefuta e 'meli ea data, Graph a le Bigraph ab, ea pele e emelang li-graph tse nang le li-vertices tse ngotsoeng ka boleng ba mofuta oa a, 'me ea bobeli e emela li-graphite tse nang le li-vertices tse ka lehlakoreng le letšehali tse ngotsoeng ka boleng ba mofuta oa a le oa ho le letona. - li-vertices tsa mahlakoreng tse ngotsoeng ka boleng ba mofuta oa b.
Tsena ha se mefuta e tsoang laebraring ea Alga. Alga ha e na boemeli ba li-graph tsa bipartite tse sa lebelloang. Ke entse mefuta e kang ena bakeng sa ho hlaka.
Hape re tla hloka mesebetsi ea bathusi e nang le li-signature tse latelang:
-- Список соседей данной вершины.
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)Ho bonolo ho bona hore haeba nakong ea lipatlisiso tse tebileng-pele re fumane moeli o hanyetsanang, potoloho e makatsang e ka holim'a stack ea ho khutla. Ka hona, ho e khutlisa, re hloka ho khaola ntho e 'ngoe le e' ngoe ho tloha ho "recursion stack" ho fihlela ketsahalong ea pele ea vertex ea ho qetela.
Re kenya tšebetsong patlisiso e tebileng ea pele ka ho boloka palo e kopanetsoeng ea linomoro tsa kabelo bakeng sa vertex ka 'ngoe. Recursion stack e tla bolokoa ka bo eona ka ts'ebetsong ea Sehlopha sa Functor sa monad seo re se khethileng: re tla hloka feela ho beha li-vertices tsohle ho tloha tseleng ho ea sephethong se khutlisitsoeng ho tsoa ts'ebetsong ea boithuto.
Mohopolo oa ka oa pele e ne e le ho sebelisa Ether monad, e bonahalang e phethahatsa hantle litlamorao tseo re li hlokang. Ts'ebetsong ea pele eo ke e ngotseng e ne e le haufi haholo le khetho ena. Ha e le hantle, ke ne ke e-na le mekhoa e mehlano e fapaneng ea ts'ebetsong ka nako e 'ngoe' me qetellong ka lula ho e 'ngoe.
Taba ea pele, re hloka ho boloka letoto la li-share identifiers - sena ke taba e mabapi le Naha. Ea bobeli, re hloka ho khona ho emisa ha khohlano e fumanoa. Sena e ka ba Monad bakeng sa Ebang, kapa MonadPlus bakeng sa Mohlomong. Phapang e kholo ke hore Ebang e ka khutlisa boleng haeba palo e sa emisoa, 'me Mohlomong e khutlisa feela tlhahisoleseling mabapi le sena tabeng ena. Kaha ha re hloke boleng bo arohaneng bakeng sa katleho (e se e bolokiloe State), re khetha Mohlomong. 'Me ka nako eo re lokelang ho kopanya liphello tsa li-monads tse peli, li tsoa , e kopanyang liphello tsena hantle.
Ke hobane'ng ha ke khethile mofuta o rarahaneng hakaale? Mabaka a mabeli. Ntlha ea pele, ts'ebetsong e bonahala e tšoana haholo le ea bohlokoa. Taba ea bobeli, re hloka ho theola boleng ba ho khutla ha ho ka ba le likhohlano ha re khutla ho khutlela morao ho khutlisetsa loop e makatsang, e leng bonolo haholo ho e etsa ho Mohlomong monad.
Ka hona re fumana ts'ebetsong ena.
{-# 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)
Sebaka seo block ke sona motheo oa algorithm. Ke tla leka ho hlalosa se etsahalang ka hare ho eona.
- inVertex ke karolo ea lipatlisiso tse tebileng tsa pele moo re etelang vertex lekhetlo la pele. Mona re abela nomoro ea kabelo ho vertex mme re tsamaisa OneEdge ho baahisani bohle. Mona hape ke moo re khutlisetsang mohala oa mohala: haeba msum e khutlisitse boleng, re sutumelletsa vertex v moo.
- onEdge ke karolo eo re e etelang moeling. E bitsoa habeli bakeng sa moeli o mong le o mong. Mona re hlahloba hore na vertex ka lehlakoreng le leng e 'nile ea eteloa,' me u e etele haeba ho se joalo. Haeba re eteloa, re hlahloba hore na moeli o oa hanyetsana. Haeba ho joalo, re khutlisa boleng - karolo e kaholimo ea "recursion stack", moo li-vertices tse ling kaofela li tla beoa ha li khutla.
- processVertex e hlahloba vertex e 'ngoe le e 'ngoe hore na e etetsoe ebe e sebelisa inVertex ho eona haeba ho se joalo.
- dfs e tsamaisa processVertex ho li-vertices tsohle.
Ke phetho.
Nalane ea lentsoe INLINE
Lentsoe INLINE le ne le se ts'ebetsong ea pele ea algorithm; le hlahile hamorao. Ha ke leka ho fumana ts'ebetsong e betere, ke ile ka fumana hore mofuta oo e seng oa INLINE o ne o le butle butle lirapeng tse ling. Ha re nahana hore mesebetsi e lokela ho sebetsa ka mokhoa o ts'oanang, sena se ile sa 'makatsa haholo. Esita le motho eo u sa mo tsebeng, mochine o mong o nang le mofuta o fapaneng oa GHC ho ne ho se na phapang e bonahalang.
Kamora ho qeta beke ke bala tlhahiso ea GHC Core, ke ile ka khona ho lokisa bothata ka mola o le mong oa INLINE e hlakileng. Ka nako e 'ngoe pakeng tsa GHC 8.4.4 le GHC 8.6.5 optimizer e ile ea khaotsa ho etsa sena ka boeona.
Ke ne ke sa lebella ho kopana le litšila tse joalo lenaneong la Haskell. Leha ho le joalo, le kajeno, li-optimizer ka linako tse ling li etsa liphoso, 'me ke mosebetsi oa rona ho ba fa malebela. Ka mohlala, mona rea tseba hore mosebetsi o lokela ho kenngoa ka mola hobane o kentsoe ka har'a mofuta oa bohlokoa, 'me lena ke lebaka la ho fa moqapi leseli.
Ho ile ha etsahala’ng ka mor’a moo?
Eaba ke kenya tšebetsong algorithm ea Hopcroft-Karp le li-monads tse ling, 'me e bile pheletso ea lenaneo.
Ka lebaka la Google Summer of Code, ke ile ka fumana phihlelo e sebetsang ea mananeo a sebetsang, a sa kang a nthusa feela hore ke fumane internship ho Jane Street lehlabuleng le latelang (ha ke tsebe hantle hore na sebaka sena se tsebahala hakae esita le har'a bamameli ba nang le tsebo ea Habr, empa ke e 'ngoe. ho tse 'maloa moo u ka khonang hlabula ho kenya letsoho lenaneong le sebetsang), empa hape o ile a ntsebisa lefats'e le tsotehang la ho sebelisa paradigm ena ka ts'ebetso, e fapaneng haholo le phihlelo ea ka ea lipuo tsa setso.
Source: www.habr.com