Síðasta sumar tók ég þátt í - forrit fyrir nemendur frá Google. Á hverju ári velja skipuleggjendur nokkur Open Source verkefni, þar á meðal frá svo þekktum samtökum eins og и . Google býður nemendum alls staðar að úr heiminum að vinna að þessum verkefnum.
Sem þátttakandi í Google Summer of Code 2019 vann ég verkefni á bókasafninu við samtökin , sem er að þróa Haskell tungumálið - eitt frægasta hagnýta forritunarmálið. Alga er bókasafn sem táknar framsetning fyrir línurit í Haskell. Það er notað til dæmis í - Github bókasafn sem byggir merkingartré, kalla- og ósjálfstæðisgraf byggt á kóða og getur borið þau saman. Verkefnið mitt var að bæta við gerð öruggri framsetningu fyrir tvíhliða línurit og reiknirit fyrir þá framsetningu.
Í þessari færslu mun ég tala um útfærslu mína á reiknirit til að athuga línurit fyrir tvískiptingu í Haskell. Jafnvel þó að reikniritið sé eitt það grundvallaratriði, tók það mig nokkrar endurtekningar að útfæra það fallega í hagnýtum stíl og krafðist talsverðrar vinnu. Þar af leiðandi settist ég á útfærslu með mónaspennum.
Um mig
Ég heiti Vasily Alferov, ég er fjórða árs nemandi við St. Petersburg HSE. Fyrr á blogginu skrifaði ég и . Núna er ég í starfsnámi kl í Noregi þar sem ég er að vinna að nálgun á vandanum . Áhugamál mín eru meðal annars reiknirit með færibreytum og hagnýtri forritun.
Um innleiðingu reikniritsins
Formáli
Nemendur sem taka þátt í náminu eru eindregið hvattir til að blogga. Þeir gáfu mér vettvang fyrir bloggið . Þessi grein er þýðing , skrifað af mér þar í júlí á ensku, með stuttum formála.
Pull Request með umræddum kóða er að finna .
Þú getur lesið um niðurstöður vinnu minnar (á ensku) .
Þessari færslu er ætlað að kynna lesandann grunnhugtökin í hagnýtri forritun, þó ég reyni að rifja upp öll hugtökin sem notuð eru þegar þar að kemur.
Athugaðu línurit fyrir tvíhliða
Reiknirit til að athuga línurit fyrir tvískiptingu er venjulega gefið í námskeiði um reiknirit sem eitt einfaldasta grafalgrímið. Hugmyndin hans er einföld: fyrst setjum við einhvern veginn hornpunkta í vinstri eða hægri deilingu, og þegar mótandi brún finnst, fullyrðir við að grafið sé ekki tvíhliða.
Smá smáatriði: fyrst setjum við hornpunkt í vinstri hlutann. Augljóslega verða allir nágrannar þessa hornpunkts að liggja í hægra blaðinu. Ennfremur verða allir nágrannar nágranna þessa hornpunkts að liggja í vinstri blaðsíðunni, og svo framvegis. Við höldum áfram að úthluta hlutum á hornpunkta svo framarlega sem það eru enn hornpunktar í tengda hluta hornpunktsins sem við byrjuðum á sem við höfum ekki úthlutað nágranna til. Við endurtökum síðan þessa aðgerð fyrir alla tengda íhluti.
Ef það er brún á milli hornpunkta sem falla inn í sama skipting er ekki erfitt að finna oddalotu í línuritinu, sem er víða þekkt (og alveg augljóslega) ómögulegt í tvíhliða línuriti. Annars höfum við rétta skiptingu, sem þýðir að grafið er tvíþætt.
Venjulega er þetta reiknirit útfært með því að nota eða . Í mikilvægum tungumálum er dýpt-fyrsta leit venjulega notuð þar sem hún er aðeins einfaldari og krefst ekki viðbótargagnaskipulags. Ég valdi líka dýpt-fyrst leit þar sem hún er hefðbundnari.
Þannig komum við að eftirfarandi kerfi. Við förum yfir hornpunkta línuritsins með því að nota dýpt-fyrstu leit og úthluta þeim hlutum og breytum númeri hlutarins þegar við förum eftir brúninni. Ef við reynum að úthluta hlutdeild á hornpunkt sem hefur þegar úthlutað hlutdeild, getum við örugglega sagt að grafið sé ekki tvíhliða. Um leið og öllum hornpunktum er úthlutað hlutdeild og við höfum skoðað allar brúnir, höfum við gott skipting.
Hreinleiki útreikninga
Í Haskell gerum við ráð fyrir að allir útreikningar séu hreint. Hins vegar, ef þetta væri sannarlega raunin, hefðum við enga leið til að prenta neitt á skjáinn. Alls, hreint útreikningar eru svo latir að þeir eru ekki til hreint ástæður til að reikna eitthvað út. Allir útreikningar sem eiga sér stað í forritinu eru einhvern veginn þvingaðir inn "óhreinn" mónad IO.
Monads eru leið til að tákna útreikninga með áhrifum í Haskell. Að útskýra hvernig þeir virka er utan ramma þessarar færslu. Góða og skýra lýsingu má lesa á ensku .
Hér vil ég benda á að á meðan sumar mónadur, eins og IO, eru útfærðar með þýðandagaldur, eru nánast allar aðrar útfærðar í hugbúnaði og allir útreikningar í þeim eru hreinir.
Það eru fullt af áhrifum og hver hefur sína mónad. Þetta er mjög sterk og falleg kenning: allar mónadur útfæra sama viðmótið. Við munum tala um eftirfarandi þrjár mónadur:
- Annaðhvort er ea útreikningur sem skilar gildi af gerð a eða kastar undantekningu af gerð e. Hegðun þessarar mónadar er mjög svipuð og meðhöndlun undantekninga í mikilvægum tungumálum: villur geta verið gripnar eða sendar áfram. Helsti munurinn er sá að mónadinn er fullkomlega rökrétt útfærður í venjulegu bókasafninu í Haskell, á meðan nauðsynleg tungumál nota venjulega stýrikerfiskerfi.
- State sa er útreikningur sem skilar gildi af gerð a og hefur aðgang að breytilegu ástandi af gerð s.
- Kannski a. Kannski mónadinn tjáir útreikning sem hægt er að rjúfa hvenær sem er með því að skila Ekkert. Hins vegar munum við tala um útfærslu MonadPlus bekkjarins fyrir Maybe tegundina, sem lýsir öfug áhrif: það er útreikningur sem hægt er að trufla hvenær sem er með því að skila tilteknu gildi.
Innleiðing reikniritsins
Við höfum tvær gagnagerðir, graf a og bigraph ab, sú fyrri sýnir línurit með hornpunktum merktum gildum af gerð a, og sú síðari táknar tvíhliða línurit með hornpunktum til vinstri merkt gildum af gerð a og hægri -hliðarpunktar merktir með gildum af gerð b.
Þetta eru ekki tegundir úr Þörungabókasafninu. Alga hefur ekki framsetningu fyrir óstýrð tvíhliða línurit. Ég gerði þessar tegundir til glöggvunar.
Við þurfum líka hjálparaðgerðir með eftirfarandi undirskriftum:
-- Список соседей данной вершины.
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)Það er auðvelt að sjá að ef við fundum misvísandi brún við fyrstu dýptarleitina, þá liggur staka hringrásin ofan á endurkomustaflanum. Þannig, til að endurheimta það, þurfum við að skera allt frá endurkomustafla upp að fyrsta tilviki síðasta hornpunktsins.
Við innleiðum dýpt-fyrstu leit með því að viðhalda samtengdu fylki hlutanúmera fyrir hvern hornpunkt. Endurkvæmisstaflanum verður sjálfkrafa viðhaldið með útfærslu Functor flokks móndunnar sem við höfum valið: við þurfum aðeins að setja alla hornpunkta frá slóðinni inn í niðurstöðuna sem skilað er frá endurkvæmu fallinu.
Fyrsta hugmynd mín var að nota Annaðhvort mónduna, sem virðist útfæra nákvæmlega þau áhrif sem við þurfum. Fyrsta útfærslan sem ég skrifaði var mjög nálægt þessum möguleika. Reyndar var ég með fimm mismunandi útfærslur á einum tímapunkti og settist að lokum á aðra.
Í fyrsta lagi þurfum við að viðhalda tengslaflokki hlutaauðkenna - þetta snýst eitthvað um ríkið. Í öðru lagi þurfum við að geta stöðvað þegar átök greinast. Þetta getur verið annað hvort Monad fyrir annað hvort eða MonadPlus fyrir Kannski. Helsti munurinn er sá að Hvort getur skilað gildi ef útreikningurinn hefur ekki verið stöðvaður og Maybe skilar aðeins upplýsingum um þetta í þessu tilfelli. Þar sem við þurfum ekki sérstakt gildi til að ná árangri (það er þegar geymt í State), veljum við Kannski. Og á því augnabliki sem við þurfum að sameina áhrif tveggja mónaða koma þær út , sem einmitt sameina þessi áhrif.
Af hverju valdi ég svona flókna gerð? Tvær ástæður. Í fyrsta lagi reynist útfærslan vera mjög svipuð og nauðsynleg. Í öðru lagi þurfum við að hagræða afturgildinu ef átök koma upp þegar við snúum til baka frá endurkomu til að endurheimta odda lykkjuna, sem er miklu auðveldara að gera í Kannski mónadunni.
Þannig fáum við þessa útfærslu.
{-# 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)
Hvar blokkin er kjarninn í reikniritinu. Ég mun reyna að útskýra hvað er að gerast inni í henni.
- inVertex er hluti af dýpt-fyrstu leit þar sem við heimsækjum hornpunktinn í fyrsta skipti. Hér gefum við hlutanúmeri á hornpunktinn og keyrum onEdge á alla nágranna. Þetta er líka þar sem við endurheimtum kallstaflann: ef msum skilaði gildi, ýtum við hornpunkti v þangað.
- onEdge er sá hluti sem við heimsækjum brúnina. Það er kallað tvisvar fyrir hverja brún. Hér athugum við hvort hornpunkturinn hinum megin hafi verið heimsóttur, og skoðum hann ef ekki. Ef farið er í heimsókn athugum við hvort brúnin stangist á. Ef svo er, þá skilum við gildinu - efst á endurtekningarstaflanum, þar sem allir aðrir hornpunktar verða síðan settir við endurkomu.
- processVertex athugar fyrir hvern hornpunkt hvort hann hafi verið heimsóttur og keyrir inVertex á hann ef ekki.
- dfs keyrir processVertex á öllum hornpunktum.
Það er allt og sumt.
Saga orðsins INLINE
Orðið INLINE var ekki í fyrstu útfærslu reikniritsins; það birtist síðar. Þegar ég reyndi að finna betri útfærslu fann ég að útgáfan sem er ekki INLINE var áberandi hægari á sumum línuritum. Miðað við að merkingarlega ættu aðgerðir að virka eins, kom þetta mér mjög á óvart. Jafnvel skrítnara, á annarri vél með annarri útgáfu af GHC var enginn merkjanlegur munur.
Eftir að hafa eytt viku í að lesa GHC Core úttakið gat ég lagað vandamálið með einni línu af skýrri INLINE. Einhvern tíma á milli GHC 8.4.4 og GHC 8.6.5 hætti fínstillingartækið að gera þetta á eigin spýtur.
Ég bjóst ekki við að lenda í svona óhreinindum í Haskell forritun. Hins vegar, jafnvel í dag, gera fínstillingarmenn stundum mistök og það er okkar hlutverk að gefa þeim vísbendingar. Til dæmis, hér vitum við að aðgerðin ætti að vera inlined vegna þess að hún er inlined í imperative útgáfunni, og það er ástæða til að gefa þýðandanum vísbendingu.
Hvað gerðist næst?
Síðan innleiddi ég Hopcroft-Karp reikniritið með öðrum mónuðum, og þar með lauk forritinu.
Þökk sé Google Summer of Code öðlaðist ég hagnýta reynslu í hagnýtri forritun, sem ekki aðeins hjálpaði mér að fá starfsnám á Jane Street sumarið eftir (ég er ekki viss um hversu vel þekktur þessi staður er jafnvel meðal fróðra áhorfenda Habr, en hann er einn. af fáum þar sem þú getur sumarið til að taka þátt í hagnýtri forritun), en kynnti mér líka þann dásamlega heim að beita þessari hugmyndafræði í reynd, verulega frábrugðinn reynslu minni í hefðbundnum tungumálum.
Heimild: www.habr.com