As t-samhradh an-uiridh ghabh mi pàirt ann - prògram do dh'oileanaich bho Google. Gach bliadhna, bidh an luchd-eagrachaidh a’ taghadh grunn phròiseactan Open Source, a’ gabhail a-steach bho bhuidhnean ainmeil mar и . Tha Google a’ toirt cuireadh do dh’ oileanaich bho air feadh an t-saoghail a bhith ag obair air na pròiseactan sin.
Mar chom-pàirtiche ann an Google Summer of Code 2019, rinn mi pròiseact taobh a-staigh an leabharlann leis a’ bhuidheann , a tha a’ leasachadh cànan Haskell - aon de na cànanan prògramaidh gnìomh as ainmeil. Tha Alga na leabharlann a tha a’ riochdachadh riochdachadh airson grafaichean ann an Haskell. Tha e air a chleachdadh, mar eisimpleir, ann an - leabharlann Github a bhios a’ togail chraobhan semantach, grafaichean gairm is eisimeileachd stèidhichte air còd agus as urrainn coimeas a dhèanamh eadar iad. B 'e am pròiseact agam riochdachadh seòrsa-sàbhailte a chur ris airson grafaichean bipartite agus algorithms airson an riochdachadh sin.
Anns an dreuchd seo bruidhnidh mi mu mo bhuileachadh air algairim airson sgrùdadh a dhèanamh air graf airson bipartiteness ann an Haskell. Eadhon ged a tha an algairim mar aon den fheadhainn as bunaitiche, thug a bhith ga chuir an gnìomh gu breagha ann an stoidhle gnìomh grunn ath-aithrisean dhomh agus bha feum air tòrr obrach. Mar thoradh air an sin, shocraich mi air buileachadh le cruth-atharraichean monad.
Mu mo dheidhinn fhèin
Is e m ’ainm Vasily Alferov, tha mi nam oileanach sa cheathramh bliadhna aig St. Petersburg HSE. Na bu thràithe sa bhlog sgrìobh mi и . An-dràsta tha mi air inntearnas aig ann an Nirribhidh, far a bheil mi ag obair air dòighean-obrach a thaobh na trioblaid . Tha na h-ùidhean agam a’ toirt a-steach algorithms parameterized agus prògramadh gnìomh.
Mu chur an gnìomh an algairim
Facal-toisich
Thathas a’ brosnachadh oileanaich a tha a’ gabhail pàirt sa phrògram gu bhith a’ blogadh. Thug iad dhomh àrd-ùrlar airson a’ bhlog . Is e eadar-theangachadh a tha san artaigil seo , air a sgrìobhadh leam an sin san Iuchar ann am Beurla, le ro-ràdh goirid.
Gheibhear Iarrtas Tarraing leis a’ chòd sin .
Faodaidh tu leughadh mu thoraidhean na h-obrach agam (ann am Beurla) .
Tha an dreuchd seo ag amas air eòlas a thoirt don leughadair air na bun-bheachdan ann am prògramadh gnìomh, ged a dh’ fheuchaidh mi ri cuimhneachadh air a h-uile teirm a chleachdar nuair a thig an t-àm.
A’ sgrùdadh ghrafaichean airson bipartiteness
Mar as trice tha algairim airson sgrùdadh graf airson bipartiteness air a thoirt seachad ann an cùrsa air algorithms mar aon de na h-algorithms graf as sìmplidh. Tha a bheachd sìmplidh: an toiseach bidh sinn dòigh air choireigin a’ cur vertices anns a’ chuibhreann chlì no deas, agus nuair a lorgar oir connspaideach, bidh sinn ag ràdh nach eil an graf dà-thaobhach.
Beagan a bharrachd mion-fhiosrachaidh: an toiseach chuir sinn beagan vertex anns a’ chuibhreann chlì. Gu follaiseach, feumaidh uile choimhearsnaich an vertex seo laighe anns an lobe cheart. Nas fhaide, feumaidh a h-uile nàbaidh nàbaidhean an vertex seo laighe anns an lobe chlì, agus mar sin air adhart. Bidh sinn a’ leantainn le bhith a’ sònrachadh earrannan gu vertices fhad ‘s a tha vertices fhathast anns a’ phàirt cheangailte den vertex ris an do thòisich sinn nach eil sinn air nàbaidhean a shònrachadh dhaibh. Bidh sinn an uairsin ag ath-aithris a’ ghnìomh seo airson a h-uile pàirt ceangailte.
Ma tha iomall eadar vertices a tha a 'tuiteam a-steach don aon sgaradh, chan eil e doirbh cearcall neònach a lorg anns a' ghraf, a tha aithnichte gu farsaing (agus gu math follaiseach) do-dhèanta ann an graf dà-thaobhach. Rud eile, tha sgaradh ceart againn, a tha a’ ciallachadh gu bheil an graf bipartite.
Mar as trice, bidh an algairim seo air a chur an gnìomh a 'cleachdadh no . Ann an cànanan riatanach, mar as trice bidh sgrùdadh domhainn air a chleachdadh leis gu bheil e beagan nas sìmplidh agus nach eil feum air structaran dàta a bharrachd. Thagh mi cuideachd sgrùdadh doimhneachd-an-toiseach oir tha e nas traidiseanta.
Mar sin, thàinig sinn chun sgeama a leanas. Bidh sinn a’ dol thairis air uinneanan a’ ghraf a’ cleachdadh sgrùdadh doimhneachd-an-toiseach agus a’ sònrachadh earrannan dhaibh, ag atharrachadh àireamh a’ chuibhreann mar a bhios sinn a’ gluasad air adhart air an oir. Ma dh’ fheuchas sinn ri cuibhreann a shònrachadh do vertex aig a bheil cuibhreann air a shònrachadh mar-thà, faodaidh sinn a ràdh gu sàbhailte nach eil an graf dà-thaobhach. Cho luath ‘s a thèid cuibhreann a thoirt do gach vertice agus tha sinn air sùil a thoirt air na h-oirean gu lèir, tha deagh sgaradh againn.
Purity àireamhachadh
Ann an Haskell tha sinn a 'gabhail ris gu bheil a h-uile àireamhachadh glan. Ach, nam biodh seo fìor, cha bhiodh dòigh againn dad a chlò-bhualadh chun sgrion. Idir idir, glan tha àireamhachadh cho leisg 's nach eil aon ann glan adhbharan airson rudeigin a thomhas. Bithear a’ sparradh a-steach dòigh air choireigin air a h-uile àireamhachadh a tha a’ tachairt sa phrògram "neòghlan" mona IO.
Tha monads mar dhòigh air àireamhachadh a riochdachadh le buaidhean ann an Haskell. Tha mìneachadh mar a tha iad ag obair taobh a-muigh raon na dreuchd seo. Faodar tuairisgeul math agus soilleir a leughadh sa Bheurla .
An seo tha mi airson a chomharrachadh ged a tha cuid de mhonadan, leithid IO, air an cur an gnìomh tro dhraoidheachd cruinneachaidh, tha cha mhòr a h-uile gin eile air an cur an gnìomh ann am bathar-bog agus tha a h-uile àireamhachadh annta fìor.
Tha mòran bhuaidhean ann agus tha a monad fhèin aig gach fear. Is e teòiridh fìor làidir agus brèagha a tha seo: bidh na monaidhean uile a’ cur an aon eadar-aghaidh an gnìomh. Bruidhnidh sinn mu na trì monaidhean a leanas:
- Is e àireamhachadh a th’ ann an ea a bhios a’ tilleadh luach seòrsa a no a’ tilgeil eisgeachd seòrsa e. Tha giùlan a 'mhonaid seo glè choltach ri làimhseachadh eisgeachd ann an cànanan riatanach: faodar mearachdan a ghlacadh no a thoirt seachad. Is e am prìomh eadar-dhealachadh gu bheil am monad air a chuir an gnìomh gu tur gu loidsigeach anns an leabharlann àbhaisteach ann an Haskell, fhad ‘s a bhios cànanan riatanach mar as trice a’ cleachdadh uidheamachdan siostam obrachaidh.
- Is e àireamhachadh a th’ ann an State sa a thilleas luach seòrsa a agus aig a bheil cothrom air staid mutable de sheòrsa s.
- 'S dòcha a. Tha monad The May a 'cur an cèill àireamhachadh a dh' fhaodar a bhriseadh aig àm sam bith le bhith a 'tilleadh Nothing. Ach, bruidhnidh sinn mu bhith a 'cur an gnìomh clas MonadPlus airson an t-seòrsa' S dòcha, a tha a 'nochdadh a' bhuaidh eile: is e àireamhachadh a th 'ann a dh' fhaodar a bhriseadh aig àm sam bith le bhith a 'tilleadh luach sònraichte.
Cur an gnìomh an algairim
Tha dà sheòrsa dàta againn, Graph a agus Bigraph ab, a’ chiad fhear a’ riochdachadh ghrafaichean le vertices air an comharrachadh le luachan seòrsa a, agus an dàrna fear a’ riochdachadh ghrafaichean dà-phàirteach le vertices air an taobh chlì air an comharrachadh le luachan seòrsa a agus deas. -side vertices le bileagan le luachan seòrsa b.
Chan e seòrsaichean bho leabharlann Alga a tha seo. Chan eil riochdachadh aig Alga airson grafaichean bipartite neo-stiùiridh. Rinn mi na seòrsaichean mar seo airson soilleireachd.
Bidh feum againn cuideachd air gnìomhan cuideachaidh leis na h-ainmean a leanas:
-- Список соседей данной вершины.
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)Tha e furasta fhaicinn ma lorg sinn rè an rannsachaidh doimhneachd an-toiseach oir connspaideach, tha an cearcall neònach na laighe air mullach a’ chruach ath-chuairteachaidh. Mar sin, airson a thoirt air ais, feumaidh sinn a h-uile càil a ghearradh dheth bhon chruach ath-chuairteachaidh suas chun chiad tachartas den vertex mu dheireadh.
Bidh sinn a’ cur an gnìomh sgrùdadh doimhneachd-an-toiseach le bhith a’ cumail sreath cheangail de àireamhan earrannan airson gach vertex. Thèid a’ chruach ath-chuairteachaidh a chumail gu fèin-ghluasadach tro bhith a’ buileachadh clas Functor den mhonad a thagh sinn: cha leig sinn a leas ach a h-uile vertice bhon t-slighe a chuir a-steach don toradh a chaidh a thilleadh bhon ghnìomh ath-chuairteachaidh.
B 'e a' chiad bheachd a bh 'agam a bhith a' cleachdadh monad Eithid, a tha coltach gu bheil e a 'cur an gnìomh na buaidhean a tha a dhìth oirnn. Bha a 'chiad bhuileachadh a sgrìobh mi gu math faisg air an roghainn seo. Gu dearbh, bha còig buileachadh eadar-dhealaichte agam aig aon àm agus mu dheireadh shocraich mi air fear eile.
An toiseach, feumaidh sinn sreath de luchd-aithneachaidh com-pàirteach a chumail - is e seo rudeigin mun Stàit. San dàrna h-àite, feumaidh sinn a bhith comasach air stad nuair a lorgar còmhstri. Faodaidh seo a bhith an dàrna cuid Monad airson an dàrna cuid, no MonadPlus airson Is dòcha. Is e am prìomh eadar-dhealachadh gum faod an dàrna cuid luach a thilleadh mura deach an àireamhachadh a stad, agus is dòcha nach till e ach fiosrachadh mu dheidhinn sa chùis seo. Leis nach fheum sinn luach air leth airson soirbheachas (tha e air a stòradh mar-thà san Stàit), bidh sinn a’ taghadh S dòcha. Agus an-dràsta nuair a dh'fheumas sinn buaidh dà mhonadh a chur còmhla, thig iad a-mach , a tha gu cinnteach a’ cothlamadh nam buaidhean sin.
Carson a thagh mi seòrsa cho iom-fhillte? Dà adhbhar. An toiseach, tha e coltach gu bheil am buileachadh glè choltach ris an riatanas. San dàrna h-àite, feumaidh sinn an luach tilleadh a làimhseachadh gun fhios nach bi còmhstri ann nuair a thilleas sinn air ais bho ath-chuairteachadh gus an lùb neònach a thoirt air ais, rud a tha fada nas fhasa a dhèanamh anns a’ mhonad dòcha.
Mar sin gheibh sinn am buileachadh seo.
{-# 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)
Far a bheil am bloc aig cridhe an algairim. Feuchaidh mi ri mìneachadh dè tha a’ tachairt na bhroinn.
- Is e inVertex am pàirt de sgrùdadh doimhneachd an toiseach far am bi sinn a’ tadhal air an vertex airson a’ chiad uair. An seo bidh sinn a’ sònrachadh àireamh cuibhreann don vertex agus a’ ruith onEdge air a h-uile nàbaidh. Seo cuideachd far am bi sinn ag ath-nuadhachadh a’ chruach ghairm: ma thill msum luach, bidh sinn a’ putadh vertex v an sin.
- Is e OnEdge am pàirt far am bi sinn a’ tadhal air an oir. Tha e air a ghairm dà uair airson gach oir. An seo nì sinn sgrùdadh an deach tadhal air an vertex air an taobh eile, agus tadhal air mura deach. Ma thèid tadhal, nì sinn sgrùdadh a bheil an oir eadar-dhealaichte. Ma tha, bidh sinn a 'tilleadh an luach - fìor mhullach a' chruach ath-chuairteachaidh, far an tèid a h-uile vertice eile a chuir air ais nuair a thilleas sinn.
- Bidh processVertex a’ sgrùdadh airson gach vertex an deach tadhal air agus a’ ruith inVertex air mura deach.
- Bidh dfs a’ ruith processVertex air a h-uile vertice.
Sin e.
Eachdraidh am facal INLINE
Cha robh am facal INLINE anns a’ chiad bhuileachadh air an algairim; nochd e nas fhaide air adhart. Nuair a dh’ fheuch mi ri buileachadh nas fheàrr a lorg, lorg mi gu robh an dreach neo-INLINE gu math nas slaodaiche air cuid de ghrafaichean. Leis gum bu chòir na gnìomhan gu semantach obrachadh mar an ceudna, chuir seo iongnadh mòr orm. Eadhon coigreach, air inneal eile le dreach eadar-dhealaichte de GHC cha robh eadar-dhealachadh follaiseach ann.
Às deidh dhomh seachdain a chuir seachad a’ leughadh toradh GHC Core, bha e comasach dhomh an duilgheadas a cheartachadh le aon loidhne de INLINE soilleir. Aig àm air choreigin eadar GHC 8.4.4 agus GHC 8.6.5 sguir an optimizer seo a dhèanamh leis fhèin.
Cha robh dùil agam a leithid de shalachar a choinneachadh ann am prògramadh Haskell. Ach, eadhon an-diugh, bidh optimizers uaireannan a’ dèanamh mhearachdan, agus tha e mar dhleastanas oirnn sanasan a thoirt dhaibh. Mar eisimpleir, an seo tha fios againn gum bu chòir an gnìomh a bhith air a chòmhdach leis gu bheil e air a chòmhdach anns an dreach riatanach, agus tha seo na adhbhar airson sanas a thoirt don neach-cruinneachaidh.
Dè thachair a-nis?
An uairsin chuir mi an gnìomh algorithm Hopcroft-Karp le monads eile, agus b’ e sin deireadh a ’phrògraim.
Taing do Google Summer of Code, fhuair mi eòlas practaigeach ann am prògramadh gnìomh, a chuidich chan e a-mhàin mi a’ faighinn inntearnas aig Sràid Jane an ath shamhradh (chan eil mi cinnteach dè cho aithnichte ‘s a tha an t-àite seo eadhon am measg luchd-èisteachd eòlach Habr, ach is e aon a th’ ann. den bheagan far an urrainn dhut samhradh a dhol an sàs ann am prògramadh gnìomh), ach thug e cuideachd a-steach mi don t-saoghal iongantach a thaobh a bhith a’ cleachdadh a’ phàtran seo ann an cleachdadh, gu math eadar-dhealaichte bhon eòlas agam ann an cànanan traidiseanta.
Source: www.habr.com