Noong nakaraang tag-araw ay nakibahagi ako - isang programa para sa mga mag-aaral mula sa Google. Bawat taon, pinipili ng mga organizer ang ilang mga Open Source na proyekto, kabilang ang mula sa mga kilalang organisasyon tulad ng ΠΈ . Iniimbitahan ng Google ang mga mag-aaral mula sa buong mundo na magtrabaho sa mga proyektong ito.
Bilang isang kalahok sa Google Summer of Code 2019, gumawa ako ng proyekto sa loob ng library kasama ang organisasyon , na nagpapaunlad ng wikang Haskell - isa sa pinakatanyag na functional programming language. Ang Alga ay isang aklatan na kumakatawan representasyon para sa mga graph sa Haskell. Ito ay ginagamit, halimbawa, sa β isang Github library na bumubuo ng mga semantic tree, call at dependency graph batay sa code at maihahambing ang mga ito. Ang aking proyekto ay magdagdag ng isang uri-ligtas na representasyon para sa mga bipartite na graph at algorithm para sa representasyong iyon.
Sa post na ito ay magsasalita ako tungkol sa aking pagpapatupad ng isang algorithm para sa pagsuri ng isang graph para sa bipartiteness sa Haskell. Kahit na ang algorithm ay isa sa mga pinaka-basic, ang pagpapatupad nito nang maganda sa isang functional na istilo ay tumagal sa akin ng ilang mga pag-ulit at nangangailangan ng maraming trabaho. Bilang resulta, nagpasya ako sa isang pagpapatupad sa mga transformer ng monad.
Tungkol sa aking sarili
Ang pangalan ko ay Vasily Alferov, ako ay isang pang-apat na taong mag-aaral sa St. Petersburg HSE. Kanina sa blog na sinulat ko ΠΈ . Sa ngayon ay nasa internship ako sa sa Norway, kung saan ako gumagawa ng mga diskarte sa problema . Kasama sa mga interes ko ang mga parameterized na algorithm at functional programming.
Tungkol sa pagpapatupad ng algorithm
paunang salita
Ang mga mag-aaral na kalahok sa programa ay mahigpit na hinihikayat na mag-blog. Binigyan nila ako ng platform para sa blog . Ang artikulong ito ay isang pagsasalin , na isinulat ko doon noong Hulyo sa Ingles, na may maikling paunang salita.
Matatagpuan ang Pull Request kasama ang code na pinag-uusapan .
Maaari mong basahin ang tungkol sa mga resulta ng aking trabaho (sa Ingles) .
Ang post na ito ay inilaan upang gawing pamilyar ang mambabasa sa mga pangunahing konsepto sa functional programming, bagama't susubukan kong alalahanin ang lahat ng mga terminong ginamit pagdating ng panahon.
Sinusuri ang mga graph para sa bipartiteness
Ang isang algorithm para sa pagsuri ng isang graph para sa bipartiteness ay karaniwang ibinibigay sa isang kurso sa mga algorithm bilang isa sa mga pinakasimpleng algorithm ng graph. Ang kanyang ideya ay diretso: una, kahit papaano ay naglalagay kami ng mga vertex sa kaliwa o kanang bahagi, at kapag may nakitang magkasalungat na gilid, iginiit namin na ang graph ay hindi bipartite.
Kaunting detalye: inilagay muna namin ang ilang vertex sa kaliwang bahagi. Malinaw, ang lahat ng mga kapitbahay ng vertex na ito ay dapat na nakahiga sa kanang lobe. Dagdag pa, ang lahat ng mga kapitbahay ng mga kapitbahay ng tuktok na ito ay dapat na nakahiga sa kaliwang lobe, at iba pa. Patuloy kaming nagtatalaga ng mga bahagi sa mga vertex hangga't mayroon pa ring mga vertex sa konektadong bahagi ng vertex na sinimulan namin na hindi namin itinalagang mga kapitbahay. Pagkatapos ay ulitin namin ang pagkilos na ito para sa lahat ng konektadong bahagi.
Kung mayroong isang gilid sa pagitan ng mga vertice na nahuhulog sa parehong partition, hindi mahirap makahanap ng kakaibang cycle sa graph, na malawak na kilala (at medyo malinaw) imposible sa isang bipartite graph. Kung hindi, mayroon kaming tamang partition, na nangangahulugang ang graph ay bipartite.
Karaniwan, ang algorithm na ito ay ipinatupad gamit o . Sa mga imperative na wika, kadalasang ginagamit ang depth-first search dahil medyo mas simple ito at hindi nangangailangan ng mga karagdagang istruktura ng data. Pinili ko rin ang depth-first search dahil mas tradisyonal ito.
Kaya, dumating kami sa sumusunod na pamamaraan. Binabaybay namin ang mga vertice ng graph gamit ang depth-first na paghahanap at nagtatalaga ng mga bahagi sa kanila, binabago ang bilang ng bahagi habang lumilipat kami sa gilid. Kung susubukan naming magtalaga ng bahagi sa isang vertex na mayroon nang nakatalagang bahagi, ligtas naming masasabi na ang graph ay hindi bipartite. Sa sandaling ang lahat ng vertices ay itinalaga ng isang bahagi at tiningnan namin ang lahat ng mga gilid, mayroon kaming isang magandang partition.
Kadalisayan ng mga kalkulasyon
Sa Haskell ipinapalagay namin na ang lahat ng mga kalkulasyon ay malinis. Gayunpaman, kung ito ang tunay na kaso, wala kaming paraan upang mag-print ng anuman sa screen. sa lahat, malinis ang mga kalkulasyon ay napakatamad na walang isa malinis dahilan para kalkulahin ang isang bagay. Ang lahat ng mga kalkulasyon na nagaganap sa programa ay sa anumang paraan ay pinilit "marumi" monad IO.
Ang mga monad ay isang paraan upang kumatawan sa mga kalkulasyon gamit ang epekto sa Haskell. Ang pagpapaliwanag kung paano gumagana ang mga ito ay lampas sa saklaw ng post na ito. Ang isang mahusay at malinaw na paglalarawan ay mababasa sa Ingles .
Dito gusto kong ituro na habang ang ilang monad, tulad ng IO, ay ipinatupad sa pamamagitan ng compiler magic, halos lahat ng iba ay ipinatupad sa software at lahat ng mga kalkulasyon sa mga ito ay dalisay.
Mayroong maraming mga epekto at bawat isa ay may sariling monad. Ito ay isang napakalakas at magandang teorya: lahat ng monad ay nagpapatupad ng parehong interface. Pag-uusapan natin ang sumusunod na tatlong monad:
- Ang alinman sa e a ay isang kalkulasyon na nagbabalik ng halaga ng uri a o nagtatapon ng pagbubukod ng uri ng e. Ang pag-uugali ng monad na ito ay halos kapareho sa paghawak ng exception sa mga imperative na wika: maaaring mahuli o maipasa ang mga error. Ang pangunahing pagkakaiba ay ang monad ay ganap na lohikal na ipinatupad sa karaniwang aklatan sa Haskell, habang ang mga kinakailangang wika ay karaniwang gumagamit ng mga mekanismo ng operating system.
- Ang state s a ay isang kalkulasyon na nagbabalik ng value ng type a at may access sa nababagong estado ng type s.
- Siguro a. Ang Maybe monad ay nagpapahayag ng computation na maaaring maputol anumang oras sa pamamagitan ng pagbabalik ng Wala. Gayunpaman, pag-uusapan natin ang tungkol sa pagpapatupad ng klase ng MonadPlus para sa uri ng Maybe, na nagpapahayag ng kabaligtaran na epekto: ito ay isang pagkalkula na maaaring maantala anumang oras sa pamamagitan ng pagbabalik ng isang partikular na halaga.
Pagpapatupad ng algorithm
Mayroon kaming dalawang uri ng data, Graph a at Bigraph a b, ang una ay kumakatawan sa mga graph na may vertices na may label na mga value ng type a, at ang pangalawa ay kumakatawan sa mga bipartite graph na may left-side vertices na may label na mga value ng type a at right. -side vertices na may label na mga halaga ng uri b.
Ang mga ito ay hindi mga uri mula sa Alga library. Walang representasyon ang Alga para sa mga hindi direktang bipartite na graph. Ginawa ko ang mga uri na ganito para sa kalinawan.
Kakailanganin din namin ang mga function ng helper na may mga sumusunod na lagda:
-- Π‘ΠΏΠΈΡΠΎΠΊ ΡΠΎΡΠ΅Π΄Π΅ΠΉ Π΄Π°Π½Π½ΠΎΠΉ Π²Π΅ΡΡΠΈΠ½Ρ.
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)Madaling makita na kung sa panahon ng depth-first search nakakita kami ng magkasalungat na gilid, ang kakaibang cycle ay nasa ibabaw ng recursion stack. Kaya, upang maibalik ito, kailangan nating putulin ang lahat mula sa recursion stack hanggang sa unang paglitaw ng huling vertex.
Nagpapatupad kami ng depth-first na paghahanap sa pamamagitan ng pagpapanatili ng magkakaugnay na hanay ng mga share number para sa bawat vertex. Awtomatikong mapapanatili ang recursion stack sa pamamagitan ng pagpapatupad ng Functor class ng monad na napili namin: kakailanganin lang naming ilagay ang lahat ng vertices mula sa path patungo sa resulta na ibinalik mula sa recursive function.
Ang una kong ideya ay ang paggamit ng Either monad, na tila nagpapatupad ng eksaktong mga epekto na kailangan natin. Ang unang pagpapatupad na isinulat ko ay napakalapit sa opsyong ito. Sa katunayan, mayroon akong limang magkakaibang mga pagpapatupad sa isang punto at kalaunan ay nanirahan sa isa pa.
Una, kailangan nating magpanatili ng magkakaugnay na hanay ng mga share identifier - ito ay tungkol sa Estado. Pangalawa, kailangan nating huminto kapag may nakitang salungatan. Ito ay maaaring alinman sa Monad para sa Alinman, o MonadPlus para sa Siguro. Ang pangunahing pagkakaiba ay ang alinman ay maaaring magbalik ng isang halaga kung ang pagkalkula ay hindi napigilan, at Marahil ay nagbabalik lamang ng impormasyon tungkol dito sa kasong ito. Dahil hindi namin kailangan ng hiwalay na halaga para sa tagumpay (naka-imbak na ito sa Estado), pipiliin namin ang Siguro. At sa sandaling kailangan nating pagsamahin ang mga epekto ng dalawang monad, lumalabas ang mga ito , na tiyak na pinagsasama ang mga epektong ito.
Bakit ko pinili ang ganitong kumplikadong uri? Dalawang dahilan. Una, ang pagpapatupad ay lumalabas na halos kapareho sa kailangan. Pangalawa, kailangan nating manipulahin ang return value kung sakaling magkaroon ng conflict kapag bumalik mula sa recursion para ibalik ang kakaibang loop, na mas madaling gawin sa Maybe monad.
Kaya nakuha namin ang pagpapatupad na ito.
{-# 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)
Ang kung saan block ay ang core ng algorithm. Susubukan kong ipaliwanag kung ano ang nangyayari sa loob nito.
- Ang inVertex ay ang bahagi ng depth-first search kung saan binisita namin ang vertex sa unang pagkakataon. Dito kami nagtatalaga ng share number sa vertex at nagpapatakbo ng onEdge sa lahat ng kapitbahay. Dito rin namin nire-restore ang call stack: kung nagbalik ng value ang msum, itutulak namin ang vertex v doon.
- Ang onEdge ay ang bahagi kung saan binibisita namin ang gilid. Ito ay tinatawag na dalawang beses para sa bawat gilid. Dito ay sinusuri namin kung ang vertex sa kabilang panig ay binisita, at bisitahin ito kung hindi. Kung binisita, tinitingnan namin kung magkasalungat ang gilid. Kung ito ay, ibinabalik namin ang halaga - ang pinakatuktok ng recursion stack, kung saan ang lahat ng iba pang vertices ay ilalagay sa pagbabalik.
- Ang processVertex ay nagsusuri para sa bawat vertex kung ito ay binisita at tumatakbo sa inVertex dito kung hindi.
- Ang dfs ay nagpapatakbo ng processVertex sa lahat ng vertices.
Iyan na ang lahat.
Kasaysayan ng salitang INLINE
Ang salitang INLINE ay wala sa unang pagpapatupad ng algorithm; ito ay lumitaw sa ibang pagkakataon. Nang sinubukan kong maghanap ng mas mahusay na pagpapatupad, nalaman kong ang di-INLINE na bersyon ay kapansin-pansing mas mabagal sa ilang mga graph. Isinasaalang-alang na ang semantically ang mga function ay dapat gumana nang pareho, ito ay lubos na nagulat sa akin. Kahit na estranghero, sa isa pang makina na may ibang bersyon ng GHC ay walang kapansin-pansing pagkakaiba.
Pagkatapos gumugol ng isang linggo sa pagbabasa ng GHC Core na output, naayos ko ang problema sa isang linya ng tahasang INLINE. Sa ilang mga punto sa pagitan ng GHC 8.4.4 at GHC 8.6.5 ang optimizer ay tumigil sa paggawa nito nang mag-isa.
Hindi ko inaasahan na makatagpo ng ganitong dumi sa Haskell programming. Gayunpaman, kahit ngayon, nagkakamali minsan ang mga optimizer, at trabaho natin na bigyan sila ng mga pahiwatig. Halimbawa, dito alam natin na ang function ay dapat na naka-inline dahil ito ay naka-inline sa imperative na bersyon, at ito ay isang dahilan upang bigyan ang compiler ng isang pahiwatig.
Ano ang susunod na nangyari?
Pagkatapos ay ipinatupad ko ang algorithm ng Hopcroft-Karp sa iba pang mga monad, at iyon ang katapusan ng programa.
Salamat sa Google Summer of Code, nakakuha ako ng praktikal na karanasan sa functional programming, na hindi lamang nakatulong sa akin na makakuha ng internship sa Jane Street sa sumunod na tag-araw (Hindi ako sigurado kung gaano kakilala ang lugar na ito kahit na sa mga may kaalamang audience ni Habr, ngunit isa ito sa iilan kung saan maaari kang mag-summer upang makisali sa functional programming), ngunit ipinakilala rin sa akin ang kahanga-hangang mundo ng paglalapat ng paradigm na ito sa pagsasanay, na makabuluhang naiiba sa aking karanasan sa mga tradisyonal na wika.
Pinagmulan: www.habr.com