O le taumafanafana talu ai na ou auai ai - se polokalame mo tamaiti aoga mai Google. O tausaga taʻitasi, e filifilia ai e le au faʻatulagaina ni poloketi Open Source, e aofia ai mai faʻalapotopotoga taʻutaʻua e pei o и . Google vala'aulia tamaiti a'oga mai le lalolagi atoa e galulue i nei galuega.
I le avea ai ma se tagata auai i le Google Summer of Code 2019, sa ou faia se galuega faatino i totonu o le faletusi ma le faalapotopotoga , lea o lo'o atia'e le gagana Haskell - o se tasi o gagana ta'uta'ua fa'atino polokalame. Alga o se faletusi e fai ma sui fa'atusa mo kalafi i Haskell. E faʻaaogaina, mo se faʻataʻitaʻiga, i - o se faletusi Github e fausia ai semantic trees, telefoni ma faʻalagolago i kalafi e faʻavae i luga ole code ma mafai ona faʻatusatusa i latou. O la'u poloketi o le fa'aopoopoina lea o se fa'atusa-saogalemu fa'atusa mo kalafi e lua ma algorithms mo lena fa'atusa.
I lenei pou o le a ou talanoa e uiga i laʻu faʻatinoga o se algorithm mo le siakiina o se kalafi mo le bipartiteness i Haskell. E ui lava o le algorithm o se tasi o mea sili ona taua, o le faʻatinoina ma le matagofie i se faiga faʻaogaina na ou maua ai le tele o faʻamatalaga ma manaʻomia ai le tele o galuega. O le iʻuga, na ou faʻamautu i luga o se faʻatinoga faʻatasi ma monad transformers.
E uiga ia te aʻu lava ia
O lo'u igoa o Vasily Alferov, o a'u o se tagata aoga lona fa tausaga i St. Petersburg HSE. Muamua i le blog na ou tusia и . O le taimi nei o loo ou i ai i se galuega faataitai i i Nouei, lea o loo ou galue ai i auala i le faafitauli . O aʻu mea e fiafia i ai e aofia ai faʻasologa algorithms ma polokalame faʻatino.
E uiga i le faʻatinoina o le algorithm
Upu Tomua
O tamaiti aoga o loʻo auai i le polokalame e faʻamalosia malosi e blog. Na latou tuʻuina mai ia te aʻu se faʻavae mo le blog . O lenei tusiga o se faaliliuga , na ou tusia iina ia Iulai i le Igilisi, ma se faatomuaga puupuu.
Toso Talosaga ma le code o loʻo fesiligia e mafai ona maua .
E mafai ona e faitau e uiga i taunuuga o laʻu galuega (i le Igilisi) .
O lenei pou e faʻamoemoe e faʻamasani ai le tagata faitau i mataupu faavae i polokalame faʻatinoga, e ui lava o le a ou taumafai e manatua uma faaupuga faʻaaogaina pe a oʻo mai le taimi.
Siakiina kalafi mo le vaeluaga
O se algorithm mo le siakiina o se kalafi mo le bipartiteness e masani lava ona tuʻuina atu i se kosi i algorithms o se tasi o algorithms kalafi sili ona faigofie. O lona manatu e tuusaʻo: muamua matou te tuʻuina ni vertices i le itu agavale poʻo le taumatau, ma a maua se itu feteenai, matou te fai atu o le kalafi e le o se vaega lua.
O sina fa'amatalaga atili: muamua matou te tu'u se pito i le itu agavale. E manino lava, o tuaoi uma o lenei vertex e tatau ona taoto i le pito taumatau. E le gata i lea, o tuaoi uma o tuaoi o lenei vertex e tatau ona taoto i le itu tauagavale, ma isi. O lo'o fa'aauau pea le tu'uina atu o sea i vertex pe'ā iai pea fa'ailoga i totonu o le vaega feso'ota'i o le vertex na tatou amata ai e le'i tofia i ai ni tuaoi. Ona matou toe faia lea o lenei gaioiga mo vaega uma e fesoʻotaʻi.
Afai ei ai se pito i le va o vertices e pa'u i totonu o le vaeluaga e tasi, e le faigata ona maua se taamilosaga uiga ese i le kalafi, lea e lauiloa lautele (ma e matua manino lava) e le mafai i se kalafi bipartite. A leai, e iai la matou vaeluaga sa'o, o lona uiga o le kalafi e lua.
E masani lava, o lenei algorithm e faʻaaogaina poʻo . I gagana fa'atauva'a, e masani ona fa'aoga le su'esu'ega loloto-muamua ona e fai si faigofie ma e le mana'omia ni fa'amaumauga fa'aopoopo. Sa ou filifilia fo'i le loloto-muamua su'esu'e ona e sili atu ona masani.
O lea, na matou oʻo mai i le polokalame lea. Matou te sopoia pito o le kalafi e faʻaaoga ai le loloto-muamua suʻesuʻega ma tuʻuina atu sea ia i latou, suia le numera o le faʻasoa aʻo matou agai i luga o le pito. Afai tatou te taumafai e tuʻuina atu se sea i se vertex ua uma ona tuʻuina atu se sea, e mafai ona tatou fai atu ma le saogalemu o le kalafi e le o se vaega lua. O le taimi lava e tu'u uma ai vertices se fa'asoa ma tatou va'ai i pito uma, e lelei la tatou vaeluaga.
Mama o fa'atatauga
I Haskell tatou te manatu o faʻatusatusaga uma e mama. Ae peita'i, afai o le tulaga moni lea, e leai se matou auala e lolomi ai se mea i le lau. O na uma lava, mama e matua’i paie lava fa’atatau e leai se tasi mama mafuaaga e fuafua ai se mea. O fa'atusatusaga uma o lo'o tutupu i totonu o le polokalame e fa'amalosia i totonu "le mama" monad IO.
Monads o se auala e faʻatusalia ai faʻatusatusaga ma aafiaga i Haskell. O le fa'amatalaina pe fa'apefea ona latou galulue e sili atu i le lautele o lenei pou. O se faʻamatalaga lelei ma manino e mafai ona faitau ile Igilisi .
O iinei ou te fia faailoa atu ai e ui o nisi monads, e pei o le IO, o loʻo faʻatinoina e ala i le tuʻufaʻatasiga togafiti, toetoe lava o isi uma o loʻo faʻatinoina i polokalama ma faʻatusatusa uma i totonu e mama.
E tele a'afiaga ma e tofu lava ma lona monad. O se manatu malosi ma matagofie lenei: o monads uma e faʻaogaina le faʻaoga tutusa. O le a tatou talanoa e uiga i monads nei e tolu:
- Po'o le ea o se fa'atusatusaga e toe fa'afo'i mai ai le tau o le ituaiga a po'o le togiina o se tuusaunoaga o le ituaiga e. O le amio a lenei monad e talitutusa lava ma le faʻaogaina o le faʻaogaina i gagana faʻapitoa: e mafai ona maua mea sese pe pasi. O le eseesega tele o le monad o loʻo faʻatinoina lelei i totonu o le faletusi masani i Haskell, ae o gagana faʻapitoa e masani ona faʻaogaina masini faʻaogaina.
- State sa o se fa'atusatusaga e toe fa'afo'i mai ai se tau o le ituaiga a ma maua ai le avanoa i le fa'aliliuina tulaga o le ituaiga s.
- Atonu a. O le Maybe monad o loʻo faʻaalia se faʻatusatusaga e mafai ona faʻalavelaveina i soo se taimi e ala i le toe faʻafoʻi Leai se mea. Ae ui i lea, o le a tatou talanoa e uiga i le faʻatinoina o le vasega MonadPlus mo le ituaiga Atonu, lea e faʻaalia ai le faʻafeagai o aʻafiaga: o se faʻatusatusaga e mafai ona faʻalavelaveina i soʻo se taimi e ala i le toe faʻafoʻiina o se tau faʻapitoa.
Faʻatinoina o le algorithm
E lua a matou ituaiga faʻamaumauga, Graph a ma Bigraph ab, o le muamua o loʻo faʻatusalia kalafi ma vertices ua faʻailogaina i tulaga taua o le ituaiga a, ma le lona lua o loʻo faʻatusalia kalafi e lua faʻatasi ma pito agavale o loʻo faʻailogaina i tulaga taua o le ituaiga a ma le taumatau. -itu pito o lo'o fa'ailogaina i tulaga taua o le ituaiga b.
E le o ni ituaiga mai le faletusi Alga. Alga e leai se fa'atusa mo kalafi fa'atasi lua. Sa ou faia ituaiga e pei o lenei mo le manino.
Matou te manaʻomia foʻi galuega fesoasoani ma saini 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)E faigofie ona iloa afai i le taimi o le suʻesuʻega loloto-muamua na matou maua ai se pito feteʻenaʻi, o le taʻamilosaga ese o loʻo taoto i luga o le faʻaputuga faʻasolosolo. O le mea lea, ina ia toe faʻafoʻisia, e manaʻomia ona tatou tipi ese mea uma mai le faʻapipiʻi faʻapipiʻi seia oʻo i le mea muamua na tupu i le pito mulimuli.
Matou te fa'atinoina le su'esu'ega loloto-muamua e ala i le fa'atumauina o fa'atasiga fa'atasi o numera fa'asoa mo pito ta'itasi. O le a otometi lava ona tausia le faʻaputuga toe faʻaleleia e ala i le faʻatinoina o le vasega Functor o le monad ua matou filifilia: e naʻo matou manaʻomia e tuʻu uma vertice mai le ala i le iʻuga na toe faʻafoʻi mai le galuega toe faʻaleleia.
O loʻu manatu muamua o le faʻaaogaina lea o le Either monad, lea e foliga mai e faʻatino tonu aʻafiaga tatou te manaʻomia. O le faʻatinoga muamua na ou tusia na latalata tele i lenei filifiliga. O le mea moni, e lima aʻu faʻatinoga eseese i le tasi taimi ma mulimuli ane faʻamautu i le isi.
Muamua, tatou te manaʻomia le faʻatumauina o se faʻalapotopotoga tuʻufaʻatasia o faʻamatalaga faʻasoa - o se mea lea e uiga i le Setete. Lona lua, e tatau ona mafai ona tatou taofi pe a iloa se feeseeseaiga. E mafai ona avea lea ma Monad mo Po'o se tasi, po'o MonadPlus mo Masalo. O le eseesega tele o le mafai lea e Either ona toe faafoi se tau pe afai e leʻi taofia le faʻatusatusaga, ma Atonu e toe faʻafoʻi mai naʻo faʻamatalaga e uiga i lenei tulaga. Talu ai matou te le manaʻomia se tau faʻapitoa mo le manuia (ua uma ona teuina i le Setete), matou te filifili Masalo. Ma i le taimi e manaʻomia ai ona tuʻufaʻatasia aʻafiaga o monads e lua, latou te oʻo mai , lea e tu'ufa'atasia tonu ai nei a'afiaga.
Aisea na ou filifilia ai se ituaiga lavelave faapena? E lua mafuaaga. Muamua, o le faʻatinoga e foliga mai e tutusa lelei ma le taua. Lona lua, e tatau ona tatou faʻaogaina le tau toe faʻafoʻi i le tulaga o feeseeseaiga pe a toe foʻi mai le toe faʻafoʻi e toe faʻafoʻi le matasele uiga ese, lea e sili atu ona faigofie ona fai i le May monad.
O lea ua tatou maua ai lenei faatinoga.
{-# 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)
Ole poloka ole mea ole autu ole algorithm. O le a ou taumafai e faʻamatala le mea o loʻo tupu i totonu.
- inVertex o le vaega o le loloto-muamua su'esu'ega lea tatou te asiasi ai i le tumutumu mo le taimi muamua. O iinei matou te tuʻuina atu ai se numera faʻasoa i le pito ma taʻavale i luga o le Edge i tuaoi uma. O le mea foi lea tatou te toe faʻafoʻi ai le faʻapipiʻi telefoni: afai e toe faʻafoʻi e msum se tau, tatou te tuleia le vertex v iina.
- onEdge o le vaega lea matou te asiasi ai i le pito. E ta'ua faalua mo pito taitasi. O iinei tatou te siaki ai pe o le vertex i le isi itu na asia, ma asiasi i ai pe a leai. Afai e asia, matou te siaki pe fete'ena'i le pito. Afai o lea, matou te toe faʻafoʻi le tau - o le pito i luga o le faʻaputuga, lea o le a tuʻu uma ai isi vertice pe a toe foʻi.
- E siaki e processVertex ia pito ta'itasi pe na asia ma fa'asolo ile Vertex pe a leai.
- dfs e fa'asolo le processVertex i luga o pito uma.
Pau lava lena.
Tala'aga o le upu INLINE
O le upu INLINE e leʻi i ai i le faʻatinoga muamua o le algorithm; na faʻaalia mulimuli ane. Ina ua ou taumafai e suʻe se faʻatinoga sili atu, na ou iloa ai o le faʻaogaina e le INLINE sa faʻagesegese tele i luga o nisi kalafi. Mafaufau i le faʻaogaina o galuega e tatau ona galue tutusa, o lenei mea na matua faateia ai aʻu. E oo lava i tagata ese, i luga o se isi masini e ese le GHC e leai se eseesega iloga.
Ina ua uma le faʻaaluina o le vaiaso e faitau ai le GHC Core, sa mafai ona ou faʻaleleia le faʻafitauli i se laina e tasi o INLINE manino. I se taimi i le va o le GHC 8.4.4 ma le GHC 8.6.5 na taofia e le optimizer le faia o ia lava.
Ou te leʻi faʻamoemoe e faʻafeiloaʻi ia palapala i le polokalame Haskell. Ae ui i lea, e oʻo lava i aso nei, o nisi taimi e faia ai e le au faʻamaonia mea sese, ma o la tatou galuega le tuʻuina atu ia i latou o faʻamatalaga. Mo se faʻataʻitaʻiga, o iinei tatou te iloa ai o le galuega e tatau ona faʻapipiʻiina ona o loʻo faʻapipiʻiina i le faʻamatalaga taua, ma o se mafuaʻaga lea e tuʻuina atu ai i le tagata faʻapipiʻi se faʻamatalaga.
O le a le mea na sosoo ai?
Ona ou faʻatinoina lea o le Hopcroft-Karp algorithm ma isi monads, ma o le faaiuga lena o le polokalama.
Fa'afetai i Google Summer of Code, na ou maua ai le poto masani i polokalame fa'atino, lea e le gata na fesoasoani ia te a'u e maua ai se galuega faataitai i Jane Street i le taumafanafana na sosoo ai (Ou te le o mautinoa po o le a le lauiloa o lenei nofoaga e oo lava i le au maimoa a Habr, ae tasi lava. o nai mea e mafai ona e mafanafana e auai i polokalame faʻatino), ae faʻafeiloaʻi foi aʻu i le lalolagi matagofie o le faʻaaogaina o lenei faʻataʻitaʻiga i le faʻatinoga, e matua ese lava mai loʻu poto masani i gagana masani.
puna: www.habr.com