L'estiu passat hi vaig participar - un programa per a estudiants de Google. Cada any, els organitzadors seleccionen diversos projectes de codi obert, inclòs d'organitzacions tan conegudes com и . Google convida estudiants d'arreu del món a treballar en aquests projectes.
Com a participant de Google Summer of Code 2019, vaig fer un projecte dins de la biblioteca amb l'organització , que està desenvolupant el llenguatge Haskell, un dels llenguatges de programació funcionals més famosos. Alga és una biblioteca que representa representació de gràfics en Haskell. S'utilitza, per exemple, en — una biblioteca de Github que construeix arbres semàntics, gràfics de trucades i dependències basats en codi i els pot comparar. El meu projecte era afegir una representació segura de tipus per a gràfics bipartits i algorismes per a aquesta representació.
En aquesta entrada parlaré de la meva implementació d'un algorisme per comprovar la bipartitivitat d'un gràfic a Haskell. Tot i que l'algoritme és un dels més bàsics, implementar-lo amb un estil funcional em va portar diverses iteracions i va requerir força feina. Com a resultat, em vaig decidir per una implementació amb transformadors de mónades.
Quant a mi
Em dic Vasily Alferov, sóc un estudiant de quart curs a l'HSE de Sant Petersburg. Abans al blog vaig escriure и . Ara mateix estic fent pràctiques a a Noruega, on estic treballant en enfocaments del problema . Els meus interessos inclouen algorismes parametritzats i programació funcional.
Sobre la implementació de l'algorisme
Prefaci
Es recomana als estudiants que participen en el programa que facin un blog. Em van proporcionar una plataforma per al bloc . Aquest article és una traducció , escrit per mi allà al juliol en anglès, amb un breu prefaci.
Es pot trobar Pull Request amb el codi en qüestió .
Podeu llegir els resultats del meu treball (en anglès) .
Aquesta entrada suposa que el lector està familiaritzat amb els conceptes bàsics de la programació funcional, tot i que intentaré recordar tots els termes utilitzats quan arribi el moment.
Comprovació de gràfics per bipartitisme
Un algorisme per comprovar la bipartitivitat d'un gràfic se sol donar en un curs sobre algorismes com un dels algorismes de gràfics més senzills. La seva idea és senzilla: primer posem d'alguna manera vèrtexs a la part esquerra o dreta, i quan es troba una aresta en conflicte, afirmem que el gràfic no és bipartit.
Una mica més de detall: primer posem algun vèrtex a la part esquerra. Evidentment, tots els veïns d'aquest vèrtex han de situar-se al lòbul dret. A més, tots els veïns dels veïns d'aquest vèrtex s'han de situar al lòbul esquerre, etc. Continuem assignant accions a vèrtexs sempre que encara hi hagi vèrtexs en el component connectat del vèrtex amb què hem començat que no hem assignat veïns. A continuació, repetim aquesta acció per a tots els components connectats.
Si hi ha una vora entre vèrtexs que cauen a la mateixa partició, no és difícil trobar un cicle imparell al gràfic, cosa que és àmpliament coneguda (i força òbvia) impossible en un gràfic bipartit. En cas contrari, tenim una partició correcta, el que significa que el gràfic és bipartit.
Normalment, aquest algorisme s'implementa utilitzant o . En els idiomes imperatius, la cerca en profunditat s'utilitza normalment, ja que és una mica més senzilla i no requereix estructures de dades addicionals. També vaig triar la cerca en profunditat ja que és més tradicional.
Així, vam arribar al següent esquema. Travessem els vèrtexs del gràfic mitjançant la cerca en profunditat i els assignem accions, canviant el número de la part a mesura que ens movem per la vora. Si intentem assignar una part a un vèrtex que ja té una part assignada, podem dir amb seguretat que el gràfic no és bipartit. En el moment en què tots els vèrtexs tenen assignat una part i hem mirat totes les vores, tenim una bona partició.
Puresa de càlculs
A Haskell suposem que tots els càlculs són net. Tanmateix, si aquest fos realment el cas, no tindríem cap manera d'imprimir res a la pantalla. En absolut, net els càlculs són tan mandrosos que no n'hi ha cap net raons per calcular alguna cosa. Tots els càlculs que es produeixen al programa es veuen obligats d'alguna manera "brut" mónada IO.
Les mónades són una manera de representar càlculs amb efectes a Haskell. Explicar com funcionen està fora de l'abast d'aquesta publicació. Es pot llegir una descripció bona i clara en anglès .
Aquí vull assenyalar que, mentre que algunes mónades, com ara IO, s'implementen mitjançant la màgia del compilador, gairebé totes les altres s'implementen en programari i tots els càlculs en elles són purs.
Hi ha molts efectes i cadascun té la seva pròpia mónada. Aquesta és una teoria molt forta i bonica: totes les mónades implementen la mateixa interfície. Parlarem de les tres monades següents:
- O ea és un càlcul que retorna un valor de tipus a o llança una excepció de tipus e. El comportament d'aquesta mónada és molt semblant al maneig d'excepcions en llenguatges imperatius: els errors es poden detectar o transmetre. La diferència principal és que la mónada s'implementa completament lògicament a la biblioteca estàndard d'Haskell, mentre que els llenguatges imperatius solen utilitzar mecanismes del sistema operatiu.
- L'estat sa és un càlcul que retorna un valor de tipus a i té accés a un estat mutable de tipus s.
- Potser a. La mónada Potser expressa un càlcul que es pot interrompre en qualsevol moment retornant Nothing. Tanmateix, parlarem de la implementació de la classe MonadPlus per al tipus Maybe, que expressa l'efecte contrari: és un càlcul que es pot interrompre en qualsevol moment retornant un valor concret.
Implementació de l'algorisme
Tenim dos tipus de dades, Graph a i Bigraph ab, el primer dels quals representa gràfics amb vèrtexs etiquetats amb valors de tipus a, i el segon representa gràfics bipartits amb vèrtexs esquerre etiquetats amb valors de tipus a i dret. - vèrtexs laterals etiquetats amb valors de tipus b.
Aquests no són tipus de la biblioteca Alga. Alga no té una representació per a gràfics bipartits no dirigits. Vaig fer els tipus com aquest per a més claredat.
També necessitarem funcions d'ajuda amb les següents signatures:
-- Список соседей данной вершины.
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)És fàcil veure que si durant la recerca en profunditat trobem una vora conflictiva, el cicle imparell es troba a la part superior de la pila de recursivitat. Per tant, per restaurar-lo, hem de tallar tot, des de la pila de recursivitat fins a la primera ocurrència de l'últim vèrtex.
Implementem la cerca en profunditat mantenint una matriu associativa de números d'accions per a cada vèrtex. La pila de recursivitat es mantindrà automàticament mitjançant la implementació de la classe Functor de la mónada que hem escollit: només caldrà posar tots els vèrtexs del camí en el resultat retornat per la funció recursiva.
La meva primera idea va ser utilitzar la mónada Either, que sembla implementar exactament els efectes que necessitem. La primera implementació que vaig escriure va ser molt propera a aquesta opció. De fet, vaig tenir cinc implementacions diferents en un moment i finalment em vaig conformar amb un altre.
En primer lloc, hem de mantenir una matriu associativa d'identificadors de compartició; això és una cosa sobre l'estat. En segon lloc, hem de poder aturar-nos quan es detecta un conflicte. Pot ser Monad per Either o MonadPlus per Maybe. La diferència principal és que Qualsevol pot retornar un valor si el càlcul no s'ha aturat, i Potser només retorna informació sobre això en aquest cas. Com que no necessitem un valor separat per tenir èxit (ja està emmagatzemat a State), triem Potser. I en el moment en què hem de combinar els efectes de dues mónades, surten , que precisament combinen aquests efectes.
Per què vaig triar un tipus tan complex? Dues raons. En primer lloc, la implementació resulta molt semblant a l'imperativa. En segon lloc, hem de manipular el valor de retorn en cas de conflicte quan tornem de recursivitat per restaurar el bucle imparell, que és molt més fàcil de fer a la mónada Maybe.
Així obtenim aquesta implementació.
{-# 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)
El bloc on és el nucli de l'algorisme. Intentaré explicar què hi passa dins.
- inVertex és la part de la cerca en profunditat on visitem el vèrtex per primera vegada. Aquí assignem un número de compartició al vèrtex i executem onEdge a tots els veïns. Aquí també és on restaurem la pila de trucades: si msum retorna un valor, introduïm el vèrtex v allà.
- onEdge és la part on visitem la vora. Es diu dues vegades per a cada aresta. Aquí comprovem si s'ha visitat el vèrtex de l'altre costat, i si no el visitem. Si es visita, comprovem si la vora és conflictiva. Si és així, retornem el valor: la part superior de la pila de recursivitat, on tots els altres vèrtexs es col·locaran després de retornar.
- processVertex comprova cada vèrtex si s'ha visitat i s'executa inVertex en ell si no.
- dfs executa processVertex a tots els vèrtexs.
Això és tot.
Història de la paraula INLINE
La paraula INLINE no es trobava a la primera implementació de l'algorisme; va aparèixer més tard. Quan vaig intentar trobar una implementació millor, vaig trobar que la versió no INLINE era notablement més lenta en alguns gràfics. Tenint en compte que semànticament les funcions haurien de funcionar igual, això em va sorprendre molt. Encara més estrany, en una altra màquina amb una versió diferent de GHC no hi havia cap diferència notable.
Després de passar una setmana llegint la sortida GHC Core, vaig poder solucionar el problema amb una línia d'INLINE explícita. En algun moment entre GHC 8.4.4 i GHC 8.6.5, l'optimitzador va deixar de fer-ho tot sol.
No esperava trobar tanta brutícia a la programació Haskell. Tanmateix, fins i tot avui, els optimitzadors de vegades s'equivoquen i la nostra feina és donar-los consells. Per exemple, aquí sabem que la funció s'hauria d'inserir perquè està integrada a la versió imperativa, i aquesta és una raó per donar una pista al compilador.
Què va passar després?
Llavors vaig implementar l'algorisme Hopcroft-Karp amb altres mónades, i això va ser el final del programa.
Gràcies a Google Summer of Code, vaig adquirir experiència pràctica en programació funcional, la qual cosa no només em va ajudar a fer pràctiques a Jane Street l'estiu següent (no estic segur de com de conegut és aquest lloc fins i tot entre el públic ben informat de Habr, però és un dels pocs on pots estiuejar per dedicar-te a la programació funcional), però també em va introduir en el meravellós món d'aplicar aquest paradigma a la pràctica, molt diferent de la meva experiència en llengües tradicionals.
Font: www.habr.com