Joan den udan parte hartu nuen Google Udako Kodea - Google-ko ikasleentzako programa. Urtero, antolatzaileek kode irekiko hainbat proiektu hautatzen dituzte, besteak beste, erakunde ezagunenak Boost.org и Linux Fundazioa. Googlek mundu osoko ikasleak gonbidatzen ditu proiektu hauetan lan egitera.

Google Summer of Code 2019ko parte-hartzaile gisa, liburutegiaren barruan proiektu bat egin nuen alga erakundearekin Haskell.org, Haskell lengoaia garatzen ari dena -programazio-lengoaia funtzional ospetsuenetako bat. Alga irudikatzen duen liburutegia da mota segurua grafikoetarako irudikapena Haskell-en. urtean erabiltzen da, adibidez semantikoa — Kodean oinarritutako zuhaitz semantikoak, dei eta menpekotasun grafikoak eraikitzen dituen Github liburutegia eta konparatu ditzakeena. Nire proiektua irudikapen hori bipartiteko grafikoetarako eta algoritmoetarako mota seguruko irudikapen bat gehitzea zen.

Post honetan Haskell-en grafiko bat bipartiteness egiaztatzeko algoritmo baten ezarpenari buruz hitz egingo dut. Nahiz eta algoritmoa oinarrizkoenetako bat den, estilo funtzional batean ederki ezartzeak hainbat iterazio eraman ninduen eta lan asko eskatzen zuen. Ondorioz, monada transformadoreekin inplementazio bat ezarri nuen.

Niri buruz

Nire izena Vasily Alferov da, San Petersburgo HSEko laugarren mailako ikaslea naiz. Lehenago idatzi nuen blogean parametrizatutako algoritmoei buruzko nire proiektuari buruz и ZuriHac-eko bidaiari buruz. Oraintxe bertan praktiketan nago Bergengo Unibertsitatea Norvegian, arazoari buruzko planteamenduak lantzen ari naiz Zerrenda koloreztatzea. Nire interesen artean algoritmo parametrizatuak eta programazio funtzionala daude.

Algoritmoaren ezarpenari buruz

hitzaurrea

Programan parte hartzen duten ikasleak bloga egitera gomendatzen dira. Blogerako plataforma bat eskaini didate Haskell-en uda. Artikulu hau itzulpen bat da Artikulua, nik han uztailean idatzia ingelesez, hitzaurre labur batekin.

Aipatutako kodea duen Pull Request aurki daiteke Hemen.

Nire lanaren emaitzak irakur ditzakezu (ingelesez) Hemen.

Argitalpen honek suposatzen du irakurleak programazio funtzionalaren oinarrizko kontzeptuak ezagutzen dituela, nahiz eta unea iristen denean erabiltzen diren termino guztiak gogoratzen saiatuko naizen.

Grafikoak egiaztatzea aldebikotasuna

Grafiko bat bipartiditatea egiaztatzeko algoritmo bat algoritmoei buruzko ikastaro batean eman ohi da grafikoaren algoritmo sinpleenetako bat bezala. Bere ideia zuzena da: lehenik, nolabait, ezkerreko edo eskuineko zatian erpinak jartzen ditugu, eta ertz gatazkatsu bat aurkitzen denean, grafikoa ez dela bipartidua baieztatzen dugu.

Xehetasun apur bat gehiago: lehenik ezkerreko partean erpin batzuk jarriko ditugu. Jakina, erpin honen bizilagun guztiak eskuineko lobuluan egon behar dira. Gainera, erpin honen auzokide guztiak ezkerreko lobuluan etzan behar dira, eta abar. Partekatzeak erpinei esleitzen jarraitzen dugu, hasi ginen erpinaren osagai konektatuan oraindik bizilagunak esleitu ez dizkiegun erpinak dauden bitartean. Ondoren, ekintza hau errepikatuko dugu konektatutako osagai guztientzat.

Partizio berean erortzen diren erpinen artean ertz bat badago, ez da zaila grafikoan ziklo bakoiti bat aurkitzea, oso ezaguna (eta argi eta garbi) ezinezkoa den grafiko bipartitu batean. Bestela, partizio zuzena dugu, hau da, grafikoa bipartikoa da.

Normalean, algoritmo hau erabiliz inplementatzen da zabalera lehen bilaketa edo sakoneko lehen bilaketa. Hizkuntz inperatiboetan, sakoneko bilaketa erabiltzen da normalean, zertxobait sinpleagoa baita eta ez baitu datu-egitura gehigarririk behar. Sakoneko lehen bilaketa ere aukeratu dut, tradizionalagoa baita.

Horrela, hurrengo eskemara iritsi ginen. Grafikoaren erpinak sakonera-lehenengo bilaketa erabiliz zeharkatzen ditugu eta akzioak esleitzen dizkiegu, ertzetik mugitzen garen heinean akzio kopurua aldatuz. Dagoeneko partaidetza esleituta duen erpin bati akzio bat esleitzen saiatzen bagara, seguru esan dezakegu grafikoa ez dela bipartita. Erpin guztiei partekatzea esleitzen zaien momentuan eta ertz guztiak aztertu ditugun unean, partizio ona dugu.

Kalkuluen garbitasuna

Haskell-en kalkulu guztiak direla suposatzen dugu garbi. Hala ere, hau benetan horrela balitz, ez genuke pantailan ezer inprimatzeko modurik izango. Batere, garbi kalkuluak hain alferrak dira, ezen bat ere ez garbi zerbait kalkulatzeko arrazoiak. Programan gertatzen diren kalkulu guztiak behartuta daude nolabait "zikina" monada IO.

Monadak kalkuluak irudikatzeko modu bat dira ondorioak Haskell-en. Nola funtzionatzen duten azaltzea argitalpen honen esparrutik kanpo dago. Deskribapen ona eta argia irakur daiteke ingelesez Hemen.

Hemen adierazi nahi dut monada batzuk, IO adibidez, konpiladorearen magiaren bidez inplementatzen diren bitartean, beste ia guztiak softwarean inplementatzen direla eta horietan kalkulu guztiak hutsak direla.

Efektu asko daude eta bakoitzak bere monada du. Hau oso teoria sendoa eta ederra da: monada guztiek interfaze bera ezartzen dute. Hiru monadei buruz hitz egingo dugu:

Edo a motako balio bat itzultzen duen kalkulu bat da edo e motako salbuespena ematen duena. Monada honen portaera hizkuntza inperatiboetan salbuespenen kudeaketaren oso antzekoa da: akatsak atzeman edo transmititu daitezke. Desberdintasun nagusia da monada guztiz logikoki inplementatuta dagoela Haskell-eko liburutegi estandarrean, eta hizkuntza inperatiboek normalean sistema eragilearen mekanismoak erabiltzen dituzte.
Egoera sa a motako balio bat itzultzen duen eta s motako egoera aldagarrirako sarbidea duen kalkulua da.
Agian a. Agian monadak Nothing itzuliz edozein unetan eten daitekeen konputazio bat adierazten du. Hala ere, Agian motarako MonadPlus klasearen inplementazioaz hitz egingo dugu, kontrako efektua adierazten duena: balio zehatz bat itzuliz edozein unetan eten daitekeen kalkulua da.

Algoritmoaren ezarpena

Bi datu mota ditugu, Graph a eta Bigraph ab, lehenengoak a motako balioekin etiketatutako erpinak dituzten grafikoak adierazten ditu, eta bigarrenak ezkerreko erpinak a eta eskuineko balioekin etiketatutako grafiko bipartituak adierazten ditu. -b motako balioekin etiketatutako alboko erpinak.

Hauek ez dira Alga liburutegiko motak. Algak ez du biderik gabeko grafiko bipartituetarako irudikapenik. Horrelako motak egin ditut argitasunerako.

Laguntza-funtzioak ere beharko ditugu sinadura hauekin:

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

Erraz ikusten da sakoneko lehen bilaketan ertz gatazkatsu bat aurkitzen badugu, ziklo bakoitia errekurtsio-pilaren gainean dagoela. Horrela, leheneratzeko, errekurtsio pilatik azken erpinaren lehen agerraldiraino dena moztu behar dugu.

Sakoneko lehen bilaketa inplementatzen dugu erpin bakoitzeko partekatze-zenbakien matrize asoziatiboa mantenduz. Errekurtsio pila automatikoki mantenduko da aukeratu dugun monadaren Functor klasearen ezarpenaren bidez: bideko erpin guztiak funtzio errekurtsibotik itzultzen den emaitzan bakarrik jarri beharko ditugu.

Nire lehenengo ideia Either monada erabiltzea izan zen, badirudi behar ditugun efektuak zehatz-mehatz ezartzen dituela. Idatzi nuen lehen inplementazioa aukera honetatik oso gertu zegoen. Izan ere, bost inplementazio ezberdin izan nituen une batean eta azkenean beste batean finkatu nintzen.

Lehenik eta behin, partekatze-identifikatzaileen sorta elkartua mantendu behar dugu - hau Estatuari buruzko zerbait da. Bigarrenik, gatazka bat detektatzen denean gelditzeko gai izan behar dugu. Hau Monad Either edo MonadPlus Maybe izan daiteke. Desberdintasun nagusia hauxe da: Biek balio bat itzul dezakeela kalkulua gelditu ez bada, eta Agian kasu honetan honi buruzko informazioa soilik itzultzen du. Arrakastarako balio bereizirik behar ez dugunez (dagoeneko Estatuan gordeta dago), Agian aukeratzen dugu. Eta bi monadaren ondorioak uztartu behar ditugun momentuan, ateratzen dira monada transformadoreak, hain zuzen efektu horiek konbinatzen dituztenak.

Zergatik aukeratu nuen mota hain konplexua? Bi arrazoi. Lehenik eta behin, ezarpena ezinbestekoaren oso antzekoa da. Bigarrenik, gatazkaren kasuan itzuleraren balioa manipulatu behar dugu errekurtsiotik itzultzean, begizta bakoitia berreskuratzeko, eta hori askoz errazagoa da Agian monadan.

Horrela, inplementazio hau lortzen dugu.

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

Non blokea algoritmoaren muina da. Barruan zer gertatzen den azaltzen saiatuko naiz.

inVertex erpina lehen aldiz bisitatzen dugun sakonera-lehenengo bilaketaren zatia da. Hemen partekatze-zenbaki bat esleitzen diogu erpinari eta onEdge exekutatzen dugu auzokide guztietan. Hemen ere dei-pila berreskuratzen dugu: msum-ek balio bat itzultzen badu, v erpinera bultzatzen dugu hor.
onEdge ertza bisitatzen dugun zatia da. Bi aldiz deitzen zaio ertz bakoitzeko. Hemen egiaztatuko dugu ea beste aldean dagoen erpina bisitatu den, eta bisitatzen ez bada. Bisitatuz gero, ertza gatazkatsua den egiaztatzen dugu. Hala bada, balioa itzuliko dugu - errekurtsio-pilaren goiko aldea, non beste erpin guztiak itzultzean jarriko diren.
processVertex-ek erpin bakoitza bisitatu den egiaztatzen du eta bertan inVertex exekutatzen du, hala ez bada.
dfs processVertex erpin guztietan exekutatzen du.

Hori da dena.

INLINE hitzaren historia

INLINE hitza ez zegoen algoritmoaren lehen inplementazioan; geroago agertu zen. Inplementazio hobea bilatzen saiatu nintzenean, INLINE ez zen bertsioa grafiko batzuetan nabarmen motelagoa zela ikusi nuen. Kontuan izanik semantikoki funtzioek berdin funtzionatu behar dutela, horrek asko harritu ninduen. Are arraroa, GHC-ren bertsio ezberdina zuen beste makina batean ez zegoen alde nabarmenik.

Astebete GHC Core irteera irakurtzen igaro ondoren, INLINE esplizitu lerro batekin arazoa konpondu ahal izan nuen. GHC 8.4.4 eta GHC 8.6.5 artean uneren batean optimizatzaileak hau egiteari utzi zion bere kabuz.

Ez nuen espero Haskell programazioan halako zikinkeria topatzea. Hala ere, gaur egun ere, optimizatzaileek batzuetan akatsak egiten dituzte, eta gure lana da haiei aholkuak ematea. Adibidez, hemen badakigu funtzioak lerrokatuta egon behar duela, ezinbesteko bertsioan sartuta dagoelako, eta hau da konpilatzaileari aholku bat emateko arrazoia.

Zer gertatu zen gero?

Gero Hopcroft-Karp algoritmoa inplementatu nuen beste monada batzuekin, eta hori izan zen programaren amaiera.

Google Summer of Code-ri esker, programazio funtzionalean esperientzia praktikoa lortu nuen, eta horrek hurrengo udan Jane Street-en praktikak egiten lagundu zidan ez ezik (ez nago ziur leku hau zein den ezaguna Habr-en entzule jakinaren artean ere, baina bat da. programazio funtzionalean aritzeko udan dezakezun gutxien artean), baina paradigma hau praktikan aplikatzearen mundu zoragarrian sartu ninduen, hizkuntza tradizionaletan dudan esperientziatik nabarmen desberdina.

Iturria: www.habr.com

GSoC 2019: Bipartiteness eta monada transformadoreetarako grafikoak egiaztatzea