Ny fahavaratra lasa teo dia nandray anjara aho Google Code of Summer - fandaharana ho an'ny mpianatra avy amin'ny Google. Isan-taona dia mifantina tetikasa Open Source maromaro ny mpikarakara, anisan'izany ireo fikambanana malaza toy izany Boost.org и Ny Foundation Linux. Google dia manasa mpianatra avy amin'ny lafivalon'izao tontolo izao hiasa amin'ireo tetikasa ireo. 

Amin'ny maha mpandray anjara amin'ny Google Summer of Code 2019 dia nanao tetikasa tao anatin'ny tranomboky aho Alga miaraka amin’ny fikambanana Haskell.org, izay mampivelatra ny fiteny Haskell - iray amin'ireo fiteny fandaharana malaza indrindra miasa. Alga dia tranomboky misolo tena karazana azo antoka fanehoana an-tsary amin'ny Haskell. Izy io dia ampiasaina, ohatra, amin'ny zotran - tranomboky Github izay manangana hazo semantika, antso ary kisary miankina amin'ny kaody ary afaka mampitaha azy ireo. Ny tetik'asako dia ny hampiditra solontena azo antoka ho an'ny grafika bipartite sy algorithms ho an'io fanehoana io. 

Ato amin'ity lahatsoratra ity aho dia hiresaka momba ny fampiharana ny algorithm amin'ny fanamarinana ny kisary ho an'ny bipartiteness ao Haskell. Na dia iray amin'ireo fototra indrindra aza ny algorithm, ny fampiharana azy amin'ny fomba tsara tarehy amin'ny fomba fiasa dia nitondra fanamafisam-peo maromaro ary nitaky asa be dia be. Vokatr'izany dia nanorim-ponenana tamin'ny fampiharana miaraka amin'ny transformer monad aho. 

Ny tenako

Vasily Alferov no anarako, mpianatra taona fahefatra ao amin'ny HSE St. Petersburg aho. Tany am-boalohany tao amin'ny bilaogy no nanoratako momba ny tetikasako momba ny algorithms parameterized и momba ny dia mankany ZuriHac. Amin'izao fotoana izao aho dia manao internship ao Oniversiten'i Bergen any Norvezy, izay iasako ny fomba hamahana ny olana Fandokoana lisitra. Ny mahaliana ahy dia ny algorithm voafantina sy ny fandaharana miasa.

Momba ny fampiharana ny algorithm

sasin-teny

Ireo mpianatra mandray anjara amin'ny fandaharana dia entanina mafy hanao bilaogy. Nomen'izy ireo sehatra ho an'ny bilaogy aho Summer of Haskell. Dikanteny ity lahatsoratra ity lahatsoratra, nosoratako tany tamin'ny Jolay tamin'ny teny anglisy, miaraka amin'ny sasin-teny fohy. 

Pull Request miaraka amin'ny kaody resahina dia azo jerena eto.

Azonao atao ny mamaky momba ny vokatry ny asako (amin'ny teny anglisy) eto.

Ity lahatsoratra ity dia mihevitra fa ny mpamaky dia mahafantatra ny foto-kevitra fototra amin'ny fandaharana miasa, na dia hiezaka ny hitadidy ny teny rehetra ampiasaina aza aho rehefa tonga ny fotoana.

Fanamarinana ny grafika ho an'ny fizarazarana roa 

Ny algorithm amin'ny fanamarinana ny kisary ho an'ny bipartite dia matetika omena amin'ny fampianarana momba ny algorithm ho iray amin'ireo algorithm amin'ny grafika tsotra indrindra. Ny heviny dia mahitsy: aloha isika dia mametraka vertices amin'ny ampahany havia na havanana, ary rehefa hita ny sisiny mifanipaka, dia manamafy isika fa tsy bipartite ny grafika.

Fanazavana fanampiny: apetrakay ny vertex amin'ny ampahany havia. Mazava ho azy fa ny mpifanolo-bodirindrina amin'io vertex io dia tsy maintsy mandry eo amin'ny lobe havanana. Ankoatr'izay, ny mpifanolo-bodirindrina amin'ny mpifanolo-bodirindrina amin'ity vertex ity dia tsy maintsy mandry ao amin'ny lobe havia, sy ny sisa. Manohy manendry ampahany amin'ny vertex izahay raha mbola misy vertex ao amin'ny singa mifandray amin'ny vertex izay natombokay izay tsy nomenay mpifanolo-bodirindrina aminy. Averinay indray ity hetsika ity ho an'ny singa mifandray rehetra.

Raha misy sisiny eo anelanelan'ny vertices izay misaraka amin'ny fizarazarana mitovy, dia tsy sarotra ny mahita tsingerina hafahafa ao amin'ny grafika, izay fantatry ny maro (ary mazava ho azy) tsy azo atao amin'ny kisary bipartite. Raha tsy izany dia manana fizarazarana marina isika, izay midika fa ny grafika dia bipartite.

Amin'ny ankapobeny, ity algorithm ity dia ampiharina amin'ny fampiasana sakany fikarohana voalohany na lalina fikarohana voalohany. Amin'ny fiteny imperative dia matetika ampiasaina ny fikarohana lalina-voalohany satria tsotra kokoa ary tsy mila rafitra angon-drakitra fanampiny. Nisafidy fikarohana lalina ihany koa aho satria mahazatra kokoa.

Noho izany dia tonga tamin'ny drafitra manaraka izahay. Mandalo ny vertices amin'ny grafika amin'ny alàlan'ny fikarohana lalina-voalohany izahay ary manome fizarana ho azy ireo, manova ny isan'ny anjara rehefa mandroso amin'ny sisiny. Raha manandrana manendry ampahany amin'ny vertex izay efa manana anjara voatendry isika, dia afaka milaza tsara fa tsy bipartite ny grafika. Rehefa nomena anjara ny vertices rehetra ary nojerentsika ny sisiny rehetra dia manana fizarazarana tsara isika.

Fahadiovan'ny kajy

Ao amin'ny Haskell dia mihevitra isika fa ny kajy rehetra dia madio. Na izany aza, raha izany no zava-misy, dia tsy hanana fomba hanonta na inona na inona amin'ny efijery izahay. Na izany aza, madio malaina ny kajy fa tsy misy MADIO antony hanaovana kajy zavatra. Ny kajikajy rehetra mitranga ao amin'ny programa dia voatery miditra "maloto" monad IO.

Ny Monads dia fomba iray hanehoana ny kajy amin'ny TSY MAHOMBY ao Haskell. Ny fanazavana ny fomba fiasan'izy ireo dia ivelan'ny faritr'ity lahatsoratra ity. Ny famaritana tsara sy mazava dia azo vakiana amin'ny teny anglisy eto.

Eto dia tiako ny manamarika fa raha ny monads sasany, toy ny IO, dia ampiharina amin'ny alalan'ny majika compiler, saika ny hafa rehetra dia ampiharina amin'ny rindrambaiko ary madio avokoa ny kajy ao anatiny.

Betsaka ny effets ary samy manana ny monad ny tsirairay. Tena teoria matanjaka sy tsara tarehy ity: ny monads rehetra dia mampihatra ny interface mitovy. Hiresaka momba ireto monad telo manaraka ireto isika:

• Na ny ea dia kajy izay mamerina ny sandan'ny karazana a na manipy fanavahana karazana e. Ny fitondran-tenan'ity monad ity dia mitovy amin'ny fikarakarana manokana amin'ny fiteny imperative: azo tratrarina na ampitaina ny fahadisoana. Ny fahasamihafana lehibe dia ny hoe ny monad dia ampiharina tanteraka ao amin'ny tranomboky mahazatra ao Haskell, fa ny fiteny imperative dia matetika mampiasa mekanika rafitra miasa.
• State sa dia kajy izay mamerina ny sandan'ny karazana a ary afaka miditra amin'ny toetry ny karazana s.
• Angamba a. Ny Monad Maybe dia maneho kajy izay mety ho tapaka amin'ny fotoana rehetra amin'ny famerenana ny Tsy misy. Na izany aza, hiresaka momba ny fampiharana ny kilasy MonadPlus ho an'ny karazana Mety isika, izay maneho ny fiantraikany mifanohitra amin'izany: kajy izay mety ho tapaka amin'ny fotoana rehetra amin'ny famerenana sanda manokana.

Fampiharana ny algorithm

Manana karazana data roa izahay, Graph a sy Bigraph ab, ny voalohany dia maneho ny grafika misy vertices misy marika amin'ny soatoavin'ny karazana a, ary ny faharoa dia maneho ny bipartite grafika misy vertices ankavia misy marika amin'ny soatoavina karazana a sy havanana. - ireo vertices amin'ny sisiny misy marika karazana b.

Tsy karazana avy amin'ny tranomboky Alga ireo. Alga dia tsy manana solontena ho an'ny sarin'ny roa tonta. Nanao karazana toy izao aho mba hazava.

Mila asa mpanampy miaraka amin'ireto sonia manaraka ireto koa izahay:

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

Mora ny mahita fa raha nandritra ny fikarohana lalina-voalohany dia nahita sisiny mifanipaka isika, ny tsingerina hafahafa dia mipetraka eo an-tampon'ny stack recursion. Noho izany, mba hamerenana azy io, dia mila manapaka ny zava-drehetra manomboka amin'ny fitambaran'ny recursion ka hatramin'ny fisehoana voalohany amin'ny vertex farany.

Manatanteraka fikarohana lalina-voalohany izahay amin'ny alàlan'ny fikojakojana ny laharan'ny fizarana iombonana ho an'ny vertex tsirairay. Ny stack recursion dia hotazonina ho azy amin'ny alàlan'ny fampiharana ny kilasy Functor amin'ny monad nofidianay: tsy maintsy mametraka ny vertices rehetra avy amin'ny lalana mankany amin'ny valiny miverina avy amin'ny asa recursive fotsiny isika.

Ny hevitro voalohany dia ny fampiasana ny Either monad, izay toa mampihatra tsara ny vokatra ilaintsika. Ny fampiharana voalohany nosoratako dia tena akaiky an'io safidy io. Raha ny marina, nanana fampiharana dimy samihafa aho tamin'ny fotoana iray ary niorina tamin'ny iray hafa.

Voalohany, mila mitazona andiana mpizara mpizara isika - zavatra momba ny Fanjakana izany. Faharoa, mila afaka mijanona isika rehefa misy fifandirana hita. Ity dia mety ho Monad ho an'ny Either, na MonadPlus for Maybe. Ny tena maha samy hafa dia ny hoe Na afaka mamerina sanda iray raha toa ka tsy nijanona ny kajy, ary Angamba tsy mamerina afa-tsy vaovao momba izany amin'ity tranga ity. Koa satria tsy mila sanda mitokana ho an'ny fahombiazana (efa voatahiry ao amin'ny Fanjakana izany), dia misafidy angamba isika. Ary amin'izao fotoana izao rehefa mila manambatra ny fiantraikan'ny monads roa isika dia mivoaka izy ireo monad transformers, izay mitambatra tsara ireo vokatra ireo.

Nahoana aho no nifidy karazana sarotra toy izany? Antony roa. Voalohany, ny fampiharana dia mitovitovy amin'ny imperative. Faharoa, mila manodinkodina ny sandan'ny fiverenana isika raha misy fifandirana rehefa miverina avy amin'ny fiverenana mba hamerenana amin'ny laoniny ny loop hafahafa, izay mora kokoa ny manao ao amin'ny Monad.

Noho izany dia mahazo izany fampiharana izany isika.

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

Ny hoe block no fototry ny algorithm. Hiezaka aho hanazava ny zava-mitranga ao anatiny.

• inVertex dia ampahany amin'ny fikarohana lalina izay hitsidihantsika voalohany ny vertex. Eto izahay dia manome laharana fizarana amin'ny vertex ary mihazakazaka onEdge amin'ny mpifanolo-bodirindrina rehetra. Eo ihany koa no hamerenanay ny antso an-tariby: raha namerina sanda iray i msum, dia manosika ny vertex v any izahay.
• onEdge no ampahany hitsidihanay ny sisiny. Antsoina indroa isaky ny sisiny. Eto isika dia manamarina raha efa voatsidika ny vertex amin'ny ilany iray, ary tsidiho izany raha tsy izany. Raha tsidihina dia jereo raha mifanipaka ny sisiny. Raha izany no izy dia averinay ny sandany - ny tampony indrindra amin'ny stack recursion, izay hapetraka ny vertices hafa rehetra rehefa miverina.
• processVertex manamarina ny vertex tsirairay raha efa notsidihina ary mandeha amin'ny inVertex raha tsy izany.
• dfs dia mihazakazaka processVertex amin'ny vertex rehetra.

Izay ihany.

Ny tantaran'ny teny INLINE

Ny teny hoe INLINE dia tsy tao amin'ny fampiharana voalohany ny algorithm; niseho taty aoriana. Rehefa nanandrana nitady fampiharana tsara kokoa aho, dia hitako fa somary miadana kokoa ny dikan-teny tsy INLINE amin'ny grafika sasany. Raha jerena fa tokony hiasa mitovy amin'ny semantically ny asa, dia tena nahagaga ahy izany. Na dia vahiny aza, amin'ny milina hafa miaraka amin'ny dikan-teny GHC hafa dia tsy misy fahasamihafana hita maso.

Rehefa avy nandany herinandro namaky ny famoahana ny GHC Core aho dia afaka namaha ny olana tamin'ny andalana INLINE mazava. Tamin'ny fotoana iray teo anelanelan'ny GHC 8.4.4 sy GHC 8.6.5 dia nijanona tsy nanao izany irery ny optimizer.

Tsy nanantena ny hahita loto toy izany aho amin'ny fandaharana Haskell. Na izany aza, na dia amin'izao fotoana izao aza, manao fahadisoana indraindray ny optimizers, ary anjarantsika ny manome azy ireo torohevitra. Ohatra, eto isika dia mahafantatra fa ny asa dia tokony ho inlined satria inlined ao amin'ny dikan-imperative, ary izany no antony hanome ny compiler soso-kevitra.

Inona no nitranga taorian’izay?

Avy eo dia nampihatra ny algorithm Hopcroft-Karp niaraka tamin'ny monad hafa aho, ary izay no niafaran'ny fandaharana.

Noho ny Google Summer of Code, dia nahazo traikefa azo ampiharina amin'ny fandaharana miasa aho, izay tsy vitan'ny hoe nanampy ahy hahazo internship tao amin'ny Jane Street ny fahavaratra manaraka (tsy azoko antoka fa tena fantatry ny mpihaino an'i Habr ity toerana ity, fa iray ihany izy io. amin'ireo vitsy azonao atao mandritra ny fahavaratra mba hirotsaka amin'ny fandaharana miasa), fa nampahafantatra ahy ihany koa ny tontolo mahafinaritra amin'ny fampiharana ity paradigma ity amin'ny fampiharana, tsy mitovy amin'ny traikefako amin'ny fiteny nentim-paharazana.

Source: www.habr.com