Chilimwe chatha ndinachita nawo Google Chilimwe cha Code - pulogalamu ya ophunzira ochokera ku Google. Chaka chilichonse, okonza amasankha mapulojekiti angapo a Open Source, kuphatikiza kuchokera kumabungwe odziwika bwino monga Boost.org и Maziko a Linux. Google imaitana ophunzira ochokera padziko lonse lapansi kuti agwire ntchito imeneyi.

Monga otenga nawo gawo mu Google Summer of Code 2019, ndidachita ntchito mulaibulale Malipiro ndi bungwe Haskell.org, yomwe ikupanga chilankhulo cha Haskell - chimodzi mwa zilankhulo zodziwika bwino zamapulogalamu. Alga ndi laibulale yomwe imayimira lembani zotetezeka kuyimira kwa ma graph ku Haskell. Amagwiritsidwa ntchito, mwachitsanzo, mu wamisala - laibulale ya Github yomwe imapanga mitengo ya semantic, kuyimba ndi kudalira ma graph kutengera ma code ndipo amatha kufananiza. Pulojekiti yanga inali kuwonjezera mawonekedwe otetezedwa amtundu wa bipartite ma graph ndi ma algorithms oyimirawo.

Mu positi iyi ndilankhula za kukhazikitsidwa kwanga kwa algorithm yoyang'ana chithunzi cha bipartiteness ku Haskell. Ngakhale ma aligorivimu ndi imodzi mwazofunikira kwambiri, kuyigwiritsa ntchito moyenera kumanditengera kangapo ndipo kumafuna ntchito yambiri. Zotsatira zake, ndidakhazikika pakukhazikitsa ndi ma monad transfoma.

Payekha

Dzina langa ndine Vasily Alferov, ndine wophunzira wazaka zinayi ku St. Petersburg HSE. Poyambirira mu blog ndinalemba za polojekiti yanga yokhudzana ndi ma algorithms a parameterized и za ulendo wopita ku ZuriHac. Pakali pano ndili pa internship ku Yunivesite ya Bergen ku Norway, komwe ndikukonzekera njira zothetsera vutoli List Coloring. Zokonda zanga zikuphatikiza ma aligorivimu a parameterized ndi kukonza mapulogalamu.

Za kukhazikitsidwa kwa algorithm

Maulosi

Ophunzira omwe akutenga nawo gawo mu pulogalamuyi amalimbikitsidwa kwambiri kuti alembe mabulogu. Adandipatsa nsanja yabulogu Chilimwe cha Haskell. Nkhaniyi ndi yomasulira zolemba, lolembedwa ndi ine kumeneko mu July m’Chingelezi, ndi mawu oyamba achidule.

Kokani Pempho ndi code yomwe mukufunsidwa ingapezeke apa.

Mutha kuwerenga za zotsatira za ntchito yanga (mu Chingerezi) apa.

Cholemba ichi ndi cholinga chodziwitsa owerenga mfundo zoyambira pamapulogalamu ogwirira ntchito, ngakhale ndiyesetsa kukumbukira mawu onse ogwiritsidwa ntchito ikafika nthawi.

Kuyang'ana ma grafu kwa bipartiteness

Ma aligorivimu owonera ma graph ngati pali bipartiteness nthawi zambiri amaperekedwa mu maphunziro a ma aligorivimu ngati imodzi mwama graph algorithms osavuta. Lingaliro lake ndi lolunjika: choyamba ife mwanjira ina timayika ma vertices kumanzere kapena kumanja, ndipo pamene malire otsutsana apezeka, timatsimikizira kuti graph siili ndi magawo awiri.

Tsatanetsatane pang'ono: choyamba timayika vertex kumanzere. Mwachiwonekere, oyandikana nawo onse a vertex iyi ayenera kugona mu lobe yoyenera. Komanso, oyandikana nawo onse oyandikana nawo a vertex iyi ayenera kugona mu lobe lakumanzere, ndi zina zotero. Tikupitiliza kugawa magawo ku ma vertices bola pakadali ma vertices mu gawo lolumikizidwa la vertex yomwe tidayamba nayo yomwe sitinagawireko oyandikana nawo. Kenako timabwereza izi pazigawo zonse zolumikizidwa.

Ngati pali m'mphepete pakati pa ma vertices omwe amagwera mu gawo lomwelo, sikovuta kupeza kuzungulira kwachilendo mu graph, yomwe imadziwika kwambiri (ndipo mwachiwonekere) zosatheka mu graph ya bipartite. Kupanda kutero, tili ndi magawo olondola, zomwe zikutanthauza kuti graph ndi bipartite.

Kawirikawiri, algorithm iyi imagwiritsidwa ntchito kufufuza koyamba kapena kufufuza kwakuya koyamba. M'zilankhulo zofunikira, kufufuza mozama koyamba kumagwiritsidwa ntchito chifukwa kumakhala kosavuta komanso sikufuna zina zowonjezera. Ndinasankhanso kusaka kozama koyamba chifukwa kumakhala kwachikhalidwe.

Choncho, tinafika zotsatirazi chiwembu. Timadutsa ma vertices a graph pogwiritsa ntchito kufufuza mozama-koyamba ndi kugawa magawo kwa iwo, kusintha chiwerengero cha gawo pamene tikuyenda m'mphepete. Ngati tiyesa kugawira gawo ku vertex yomwe ili kale ndi gawo lomwe lapatsidwa, titha kunena mosabisa kuti graph siili pawiri. Pomwe ma vertices onse amagawidwa ndipo tayang'ana m'mbali zonse, tili ndi magawo abwino.

Kuyera kwa mawerengedwe

Ku Haskell timaganiza kuti kuwerengera konse kuli woyera. Komabe, ngati izi zinalidi choncho, sitikanakhala ndi njira yosindikizira pazenera. Ayi, oyera mawerengero ndi aulesi moti palibe woyera zifukwa zowerengera kanthu. Zowerengera zonse zomwe zikuchitika mu pulogalamuyi zimakakamizidwa mwanjira ina "zodetsedwa" monga IO.

Monads ndi njira yoyimira kuwerengera ndi zotsatira ku Haskell. Kufotokozera momwe amagwirira ntchito ndikupitilira positi iyi. Kufotokozera kwabwino komanso komveka bwino kumatha kuwerengedwa mu Chingerezi apa.

Apa ndikufuna kuwonetsa kuti ngakhale ma monads ena, monga IO, akugwiritsidwa ntchito pogwiritsa ntchito matsenga a compiler, pafupifupi ena onse amakhazikitsidwa mu mapulogalamu ndipo zowerengera zonse mwazo ndizoyera.

Pali zotsatira zambiri ndipo aliyense ali ndi monad yake. Ichi ndi chiphunzitso champhamvu komanso chokongola: ma monads onse amagwiritsa ntchito mawonekedwe omwewo. Tilankhula za ma monads atatu awa:

Eya ndi chiŵerengero chomwe chimabweretsa mtengo wa mtundu a kapena kuponya kusiyapo mtundu e. Makhalidwe a monad ndi ofanana kwambiri ndi machitidwe apadera m'zilankhulo zofunika: zolakwika zimatha kugwidwa kapena kuperekedwa. Kusiyana kwakukulu ndikuti monad imayendetsedwa bwino mulaibulale yokhazikika ku Haskell, pomwe zilankhulo zofunika nthawi zambiri zimagwiritsa ntchito makina ogwiritsira ntchito.
State sa ndi chiŵerengero chomwe chimabweretsa mtengo wa mtundu a ndipo amatha kupeza mawonekedwe osinthika amtundu wa s.
Mwina a. The Maybe monad ikuwonetsa kuwerengera komwe kumatha kusokonezedwa nthawi iliyonse pobweza Palibe. Komabe, tidzakambirana za kukhazikitsidwa kwa kalasi ya MonadPlus ya mtundu wa Mwina, womwe umasonyeza zosiyana: ndi kuwerengera komwe kungathe kusokonezedwa nthawi iliyonse pobwezera mtengo wake.

Kukonzekera kwa algorithm

Tili ndi mitundu iwiri ya data, Graph a ndi Bigraph ab, yoyamba yomwe imayimira ma graph okhala ndi ma vertices olembedwa ndi mikhalidwe ya mtundu a, ndipo yachiwiri imayimira ma graph a bipartite okhala ndi ma vertices akumanzere olembedwa ndi mikhalidwe ya mtundu a ndi kumanja. -ma vertices am'mbali olembedwa ndi mikhalidwe ya mtundu b.

Izi si mitundu yochokera ku laibulale ya Alga. Alga ilibe choyimira cha ma graph osagwirizana. Ndinapanga mitundu ngati iyi kuti imveke bwino.

Tifunikanso ntchito zothandizira ndi siginecha zotsatirazi:

-- Список соседей данной вершины.
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)

Ndizosavuta kuwona kuti ngati pakufufuza kozama koyamba tidapeza m'mphepete mwake, kuzungulira kosamvetseka kumakhala pamwamba pa stack yobwereza. Chifukwa chake, kuti tibwezeretse, tifunika kudula chilichonse kuyambira pamutu wobwereza mpaka pomwe pamakhala vertex yomaliza.

Timagwiritsa ntchito kusaka kozama koyamba posunga manambala ogwirizana a vertex pa vertex iliyonse. Kubwezeretsanso kudzasungidwa kokha kudzera mu kukhazikitsidwa kwa Functor kalasi ya monad yomwe tasankha: tidzangofunika kuyika ma vertices onse kuchokera panjira kupita ku zotsatira zomwe zabwezedwa kuchokera ku ntchito yobwereza.

Lingaliro langa loyamba linali kugwiritsa ntchito Ether monad, yomwe ikuwoneka kuti ikukwaniritsa zomwe tikufuna. Kukhazikitsa koyamba komwe ndinalemba kunali pafupi kwambiri ndi njirayi. M'malo mwake, ndinali ndi machitidwe asanu osiyanasiyana panthawi imodzi ndipo pamapeto pake ndidakhazikika pa ina.

Choyamba, tikuyenera kukhalabe ndi zizindikiritso zogawana - izi ndi zina zokhudza Boma. Chachiwiri, tiyenera kutha kuyimitsa pamene mkangano wapezeka. Izi zitha kukhala Monad ya Either, kapena MonadPlus mwina. Kusiyanitsa kwakukulu ndikuti Aliyense akhoza kubwezera mtengo ngati kuwerengera sikunayimitsidwe, ndipo Mwinamwake kubwezera chidziwitso chokha pa nkhaniyi. Popeza sitifuna mtengo wosiyana kuti apambane (wasungidwa kale mu State), timasankha Mwina. Ndipo panthawi yomwe tifunika kuphatikiza zotsatira za monads ziwiri, zimatuluka ma transfoma, zomwe zimagwirizanitsa ndendende zotsatirazi.

N’chifukwa chiyani ndinasankha mtundu wovuta chonchi? Zifukwa ziwiri. Choyamba, kukhazikitsidwa kumakhala kofanana kwambiri ndi kofunikira. Chachiwiri, tifunika kuwongolera mtengo wobwezera ngati pali mikangano pobwerera kuchokera kubwereza kuti tibwezeretse kuzungulira kosamvetseka, komwe kumakhala kosavuta kuchita mu Mwina monad.

Chifukwa chake timapeza kukhazikitsa uku.

{-# 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)

Pomwe block ndiye maziko a algorithm. Ndiyesera kufotokoza zomwe zikuchitika mkati mwake.

inVertex ndi gawo lakusaka kozama komwe timayendera vertex kwa nthawi yoyamba. Apa timapereka nambala yogawana ku vertex ndikuyendetsa OneEdge pa oyandikana nawo onse. Apa ndipamene timabwezeretsanso stack: ngati msum yabweza mtengo, timakankhira vertex v pamenepo.
OneEdge ndi gawo lomwe timayendera m'mphepete. Imatchedwa kawiri pamphepete iliyonse. Apa timayang'ana ngati vertex kumbali ina yachezeredwa, ndikuyiyendera ngati sichoncho. Tikachezeredwa, timayang'ana ngati m'mphepete mwake mukusemphana. Ngati ndi choncho, timabweza mtengowo - pamwamba pomwepanso, pomwe ma vertices ena onse adzayikidwa pobwerera.
processVertex imayang'ana vertex iliyonse ngati idachezeredwa ndikuyendetsa inVertex pamenepo ngati sichoncho.
dfs imayendetsa processVertex pama vertices onse.

Ndizomwezo.

Mbiri ya mawu akuti INLINE

Mawu akuti INLINE sanali pakukhazikitsa koyamba kwa algorithm; adawonekera pambuyo pake. Nditayesa kupeza njira yabwinoko, ndidapeza kuti mtundu wa non-INLINE unali wocheperako pama graph ena. Poganizira kuti semantically ntchitozo ziyenera kugwira ntchito mofanana, izi zinandidabwitsa kwambiri. Ngakhale mlendo, pamakina ena omwe ali ndi mtundu wina wa GHC panalibe kusiyana kowonekera.

Nditatha sabata ndikuwerenga zotuluka za GHC Core, ndidatha kukonza vutoli ndi mzere umodzi wa INLINE womveka. Panthawi ina pakati pa GHC 8.4.4 ndi GHC 8.6.5 optimizer inasiya kuchita izi yokha.

Sindimayembekezera kukumana ndi zoyipa zotere pamapulogalamu a Haskell. Komabe, ngakhale lero, okhathamiritsa nthawi zina amalakwitsa, ndipo ndi ntchito yathu kuwapatsa malangizo. Mwachitsanzo, apa tikudziwa kuti ntchitoyi iyenera kukhala yolumikizidwa chifukwa ili ndi mzere wofunikira, ndipo ichi ndi chifukwa chopatsa chidziwitso kwa wopanga.

Kenako chinachitika n’chiyani?

Kenako ndidakhazikitsa algorithm ya Hopcroft-Karp ndi ma monads ena, ndipo uku kunali kutha kwa pulogalamuyo.

Chifukwa cha Google Summer of Code, ndinapeza chidziwitso chothandizira pakupanga mapulogalamu, zomwe sizinangondithandiza kupeza internship ku Jane Street m'chilimwe chotsatira (sindikudziwa kuti malowa amadziwika bwanji ngakhale pakati pa omvera odziwa bwino a Habr, koma ndi amodzi. mwa ochepa kumene mungathe chilimwe kuchita nawo mapulogalamu ogwira ntchito), komanso adandidziwitsa dziko lodabwitsa la kugwiritsa ntchito paradigm iyi, mosiyana kwambiri ndi zomwe ndakumana nazo m'zinenero zachikhalidwe.

Source: www.habr.com

GSoC 2019: Kuyang'ana ma graph a bipartiteness ndi zosintha za monad