I tera raumati i whai waahi ahau - he kaupapa mo nga tauira mai i a Google. Ia tau, ka tohua e nga kaiwhakarite etahi kaupapa Open Source, tae atu ki nga whakahaere rongonui penei и . Ka tono a Google i nga tauira o te ao katoa ki te mahi i enei kaupapa.
I te mea he kaiuru au ki te Google Summer of Code 2019, i mahia e au tetahi kaupapa i roto i te whare pukapuka me te whakahaere , e whakawhanake ana i te reo Haskell - tetahi o nga reo hotaka mahi rongonui. Ko Alga he whare pukapuka e tohu ana he tohu mo nga kauwhata i Haskell. Ka whakamahia, hei tauira, i roto i — he whare pukapuka Github e hanga ana i nga rakau tohu, waea me nga kauwhata whakawhirinaki i runga i te waehere ka taea te whakataurite. Ko taku kaupapa ko te taapiri i tetahi momo-haumaru mo nga kauwhata takirua me nga algorithm mo taua whakaaturanga.
I roto i tenei pou ka korero ahau mo taku whakatinanatanga o te algorithm mo te tirotiro i te kauwhata mo te takirua i Haskell. Ahakoa ko te algorithm tetahi o nga mea tino nui, na te whakatinanatanga ataahua i roto i te ahua mahi, he maha nga huringa me te nui o te mahi. Ko te mutunga mai, i whakatau ahau ki te whakatinanatanga me nga kaiwhakawhiti monad.
Mōku anō
Ko Vasily Alferov toku ingoa, he akonga tau tuawha ahau i St. Petersburg HSE. I mua i te blog i tuhia e au и . Inaianei kei runga ahau i te whakangungu i i Norway, kei reira ahau e mahi ana i nga huarahi ki te raru . Ko nga mea e pai ana ki a au ko nga algorithm kua whakaritea me te hotaka mahi.
Mo te whakatinanatanga o te algorithm
Kupuhipa
Ko nga akonga e whai waahi ana ki te kaupapa e tino akiakihia ana ki te blog. I homai e ratou he turanga mo te blog . He whakamaoritanga tenei tuhinga , i tuhia e au ki reira i te marama o Hurae i te reo Ingarihi, me te kupu o mua poto.
Ka kitea te Tono Tono me te waehere e patai ana .
Ka taea e koe te panui mo nga hua o aku mahi (i te reo Ingarihi) .
Ko te tikanga o tenei pou kia waia ai te kaipanui ki nga aria taketake o te kaupapa mahi, ahakoa ka ngana ahau ki te maumahara ki nga kupu katoa e whakamahia ana ina tae mai te wa.
Te arowhai kauwhata mo te mahi takirua
I te nuinga o te wa ka tukuna he tohu algorithm mo te tirotiro i te kauwhata mo te taha takirua i roto i te akoranga mo te algorithms hei tetahi o nga algorithms kauwhata ngawari. He maamaa tonu tana whakaaro: i te tuatahi ka tuuhia nga poupou ki te taha maui, ki te taha matau ranei, a, ka kitea he mata taupatupatu, ka kii matou ehara te kauwhata i te wahanga rua.
He iti ake nga korero: i te tuatahi ka tukuna e matou etahi tohu ki te taha maui. Ko te tikanga, ko nga hoa tata katoa o tenei pito me takoto ki te kopa matau. I tua atu, ko nga hoa noho tata katoa o tenei tihi me takoto ki te taha maui, me etahi atu. Ka tautapa tonu matou i nga hea ki nga poupou i te mea kei te noho tonu nga poupou i roto i te waahanga hono o te tihi i timatahia e matou kaore ano matou i tautapa ki nga hoa tata. Ka whakahoki ano i tenei mahi mo nga waahanga hono katoa.
Mēnā he tapa kei waenganui i ngā poutū ka taka ki roto i te wehenga kotahi, ehara i te mea uaua ki te kimi i tetahi huringa rereke i roto i te kauwhata, e mohiotia ana (me te tino marama) kaore e taea i roto i te kauwhata rua. Ki te kore, he tika to tatou wehewehenga, ko te tikanga ko te kauwhata he wahanga rua.
Ko te tikanga, ka whakatinanahia tenei algorithm ma te whakamahi ranei . I roto i nga reo whakahirahira, ka whakamahia te rapu hohonu-tuatahi na te mea he ngawari ake, kaore e hiahiatia he hanganga raraunga taapiri. I whiriwhiria ano e ahau te rapu hohonu-tuatahi na te mea he tikanga tuku iho.
Na, i tae mai matou ki te kaupapa e whai ake nei. Ka takahia e matou nga poupou o te kauwhata ma te rapu hohonu-tuatahi ka tautapa nga hea ki a ratou, ka huri i te maha o te wahanga i a matou e neke haere ana i te taha. Mena ka ngana tatou ki te tautapa i tetahi hea ki tetahi pito kua tohua he hea, ka taea te kii he kore te kauwhata i te wahanga rua. I te wa ka whakawhiwhia nga poutoko katoa ki tetahi wahanga ka tirohia e matou nga tapa katoa, he pai to matou wehewehenga.
Te ma o nga tatauranga
Kei Haskell te whakaaro ko nga tatauranga katoa ma. Heoi, mena he pono tenei, karekau he huarahi ki te ta i tetahi mea ki te mata. Katoa, maema he tino mangere nga tatauranga karekau he kotahi ma take ki te tatau i tetahi mea. Ko nga tatauranga katoa kei roto i te hotaka ka uru ki roto " poke " monad IO.
Ko nga Monads he huarahi hei tohu i nga tatauranga pānga kei Haskell. Ko te whakamarama i a raatau mahi kei tua atu i te waahanga o tenei pou. Ka taea te korero i tetahi whakaahuatanga pai me te marama i te reo Ingarihi .
I konei e hiahia ana ahau ki te tohu ko etahi o nga monads, penei i te IO, e whakatinanahia ana na roto i te mahi makutu whakahiato, tata katoa etahi atu ka whakatinanahia i roto i te rorohiko me nga tatauranga katoa kei roto he parakore.
He maha nga paanga, kei a ia ano tana ake monad. He ariā tino kaha me te ataahua tenei: ko nga monads katoa e whakatinana ana i te atanga kotahi. Ka korero tatou mo nga monad e toru e whai ake nei:
- Ko te ea he tataunga e whakahoki mai ana i te uara o te momo a, ka maka atu ranei i te momo e. Ko te whanonga o tenei monad he tino rite ki te whakahaere motuhake i roto i nga reo whakahirahira: ka taea te mau hapa, ka tukuna atu ranei. Ko te rereketanga nui ko te monad kua tino whakatinanahia i roto i te whare pukapuka paerewa i Haskell, i te nuinga o te waa ka whakamahi nga reo whakahirahira i nga punaha whakahaere.
- Ko te State sa he tatauranga e whakahoki ana i te uara o te momo a me te whai waahi ki te ahua rereke o te momo s.
- Pea a. Ko te Pea monad e whakaatu ana i te tatauranga ka taea te haukotia i nga wa katoa ma te whakahoki i te Karekau. Engari, ka korero tatou mo te whakatinanatanga o te karaehe MonadPlus mo te momo Pea, e whakaatu ana i te ahua rereke: he tatauranga ka taea te whakakore i nga wa katoa ma te whakahoki i tetahi uara motuhake.
Te whakatinanatanga o te algorithm
E rua a matou momo raraunga, te Kauwhata a me te Bigraph ab, ko te tuatahi he tohu kauwhata me nga poupou kua tapaina ki nga uara o te momo a, ko te tuarua he tohu kauwhata takirua me nga tohu taha maui kua tapaina ki nga uara o te momo a me te matau. -ko nga pito taha kua tapaina me nga uara o te momo b.
Ehara enei i nga momo mai i te whare pukapuka Alga. Karekau he tohu a Alga mo nga kauwhata takirua takirua. I mahia e au nga momo penei mo te maarama.
Ka hiahia ano matou ki nga mahi kaiawhina me nga waitohu e whai ake nei:
-- Список соседей данной вершины.
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)He ngawari ki te kite mena i te rapunga hohonu-tuatahi ka kitea e matou he mata taupatupatu, kei runga ake o te puranga recursion te huringa rereke. No reira, ki te whakahoki mai, me tapahi nga mea katoa mai i te recursion stack ki te puta tuatahi o te pito whakamutunga.
Ka whakatinanahia e matou te rapu hohonu-tuatahi ma te pupuri i te huinga hononga o nga tau tiritiri mo ia pito. Ka mau tonu te puranga recursion na roto i te whakatinanatanga o te karaehe Functor o te monad i kowhiria e matou: me whakauru noa nga poupou katoa mai i te ara ki te hua i whakahokia mai i te mahi recursive.
Ko taku whakaaro tuatahi ko te whakamahi i te Either monad, e ahua rite ana ki te whakatinana i nga paanga e hiahiatia ana e tatou. Ko te whakatinanatanga tuatahi i tuhia e ahau i tino tata ki tenei whiringa. Otirā, e rima aku whakatinanatanga rerekē i tētahi wā, ā, i te mutunga ka tau ki tētahi atu.
Tuatahi, me mau tonu tatou i te huinga hononga o nga tohu tohu - he mea tenei mo te Kawanatanga. Tuarua, me kaha tatou ki te whakamutu ina kitea he pakanga. Ka taea e Monad tenei mo Either, MonadPlus ranei mo Pea. Ko te rereketanga nui ka taea e Either te whakahoki mai i te uara mena kaore i mutu te tatauranga, a ka whakahoki pea pea nga korero mo tenei keehi. I te mea kaore e hiahiatia he uara motuhake mo te angitu (kei te rongoa i roto i te kawanatanga), ka kowhiria e maatau pea. A i te wa e hiahia ana tatou ki te whakakotahi i nga paanga o nga monad e rua, ka puta , e whakakotahi ana i enei paanga.
He aha ahau i whiriwhiri ai i taua momo uaua? E rua nga take. Tuatahi, ko te whakatinanatanga ka tino rite ki te whakahau. Tuarua, me raweke i te uara o te hokinga mai i te wa e taupatupatu ana i te hokinga mai i te recursion ki te whakahoki mai i te kopae rereke, he maamaa ake te mahi i te pea monad.
Na ka whiwhi tatou i tenei whakatinanatanga.
{-# 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)
Ko te poraka kei hea te matua o te algorithm. Ka ngana ahau ki te whakamarama i nga mea kei roto.
- Ko inVertex te waahanga o te rapu hohonu-tuatahi ka toro atu matou ki te tihi mo te wa tuatahi. I konei ka tautapahia he nama tiritiri ki te tihi ka whakahaere i te onEdge ki nga hoa tata katoa. Koinei hoki te waahi ka whakahokia e matou te puranga waea: ki te whakahokia mai e te msum he uara, ka panaia te vertex v ki reira.
- Ko te oneEdge te waahanga ka toro atu matou ki te taha. E rua nga karangatanga mo ia tapa. I konei ka tirohia mena kua torohia te tihi o tera taha, ka toro atu ki te kore. Mena ka torohia, ka tirohia mena kei te taupatupatu te taha. Mena ko te mea, ka whakahokia e matou te uara - te runga rawa o te taapu whakamuri, ka tuu katoa atu nga poupou ina hoki mai.
- Ka tirotirohia e te processVertex mo ia poupou mehemea kua torohia, ka rere ki rotoVertex ki runga mena kaore.
- Ka whakahaerehia e dfs te processVertex i runga i nga poupou katoa.
Heoi ano.
Te hitori o te kupu INLINE
Ko te kupu INLINE karekau i te whakatinanatanga tuatahi o te algorithm; ka puta mai i muri mai. I taku ngana ki te kimi i tetahi whakatinanatanga pai ake, i kitea e au ko te putanga kore-INLINE he tino puhoi ki etahi kauwhata. Ki te whakaaro he rite tonu te mahi o nga mahi, i tino miharo ahau. Ahakoa te tangata ke, i runga i tetahi atu miihini me te ahua rereke o te GHC kaore he rereke rereke.
I muri i te paunga o te wiki ki te panui i te putanga GHC Core, i taea e au te whakatika i te raru me tetahi rarangi o INLINE. I etahi wa i waenganui i te GHC 8.4.4 me te GHC 8.6.5 ka mutu te mahi a te kaihoroi i a ia ano.
Kare au i whakaaro ka tutaki ahau ki taua paru i roto i te kaupapa Haskell. Heoi, ahakoa i tenei ra, i etahi wa ka pohehe nga kaiwhakatikatika, a na matou te mahi ki te tuku tohu. Hei tauira, i konei e mohio ana matou me whakauru te mahi na te mea kua whakauruhia ki roto i te putanga whai mana, a he take tenei hei tohu ki te kaitoi.
He aha i muri mai?
Na ka whakatinanahia e ahau te Hopcroft-Karp algorithm me etahi atu monads, a ko te mutunga o te kaupapa.
He mihi ki a Google Summer of Code, i whai wheako ahau ki nga kaupapa mahi, ehara i te mea i awhina noa ahau ki te whai waahi ki te tiriti o Jane i te raumati e whai ake nei (Kaore au i te tino mohio he aha te rongonui o tenei waahi ahakoa kei waenga i te hunga whakarongo a Habr, engari ko tetahi. o te torutoru ka taea e koe te raumati ki te whakauru ki nga kaupapa mahi), engari i whakauru mai ano ahau ki te ao whakamiharo o te whakamahi i tenei tauira i roto i nga mahi, he tino rereke mai i taku wheako ki nga reo tuku iho.
Source: will.com