Musim panas kepungkur aku melu - program kanggo siswa saka Google. Saben taun, panitia milih sawetara proyek Open Source, kalebu saka organisasi sing kondhang kayata и . Google ngajak para siswa saka sak ndonya kanggo nggarap proyek kasebut.
Minangka peserta ing Google Summer of Code 2019, aku nindakake proyek ing perpustakaan karo organisasi , sing ngembangake basa Haskell - salah sawijining basa pemrograman fungsional sing paling misuwur. Alga minangka perpustakaan sing makili perwakilan kanggo grafik ing Haskell. Kang digunakake, contone, ing - perpustakaan Github sing mbangun wit semantik, telpon lan grafik dependensi adhedhasar kode lan bisa mbandhingaké. Proyekku yaiku nambah perwakilan jinis-aman kanggo grafik bipartit lan algoritma kanggo perwakilan kasebut.
Ing kirim iki aku bakal ngomong babagan implementasine saka algoritma kanggo mriksa grafik kanggo bipartiteness ing Haskell. Sanajan algoritma kasebut minangka salah sawijining sing paling dhasar, ngetrapake kanthi apik ing gaya fungsional njupuk sawetara iterasi lan mbutuhake akeh karya. Akibaté, aku mapan ing implementasine karo trafo monad.
Babagan aku
Jenengku Vasily Alferov, aku mahasiswa taun papat ing St. Petersburg HSE. Sadurungé ing blog aku nulis и . Saiki aku lagi magang ing ing Norwegia, ngendi aku nggarap pendekatan kanggo masalah . Kapentinganku kalebu algoritma parameter lan pemrograman fungsional.
Babagan implementasine saka algoritma
Pambuka
Siswa sing melu program kasebut dianjurake banget kanggo blog. Dheweke menehi kula platform kanggo blog . Artikel iki minangka terjemahan , ditulis dening kula ana ing Juli ing Inggris, karo pambuka singkat.
Narik Request karo kode ing pitakonan bisa ditemokaké .
Sampeyan bisa maca babagan asil karyaku (ing basa Inggris) .
Posting iki dimaksudaké kanggo familiarize maca karo konsep dhasar ing program fungsional, sanajan aku bakal nyoba kanggo ngelingi kabeh istilah digunakake nalika teka wektu.
Priksa grafik kanggo bipartiteness
Algoritma kanggo mriksa grafik kanggo bipartiteness biasane diwenehake ing kursus babagan algoritma minangka salah sawijining algoritma grafik sing paling gampang. Ide dheweke langsung: pisanan kita sijine vertex ing sisih kiwa utawa tengen, lan nalika pinggiran konflik ditemokake, kita negesake yen grafik kasebut ora bipartit.
A sethitik liyane rinci: pisanan kita sijine sawetara vertex ing sisih kiwa. Temenan, kabeh tanggi saka vertex iki kudu dumunung ing lobus tengen. Luwih, kabeh tanggi saka tanggi saka vertex iki kudu dumunung ing lobus kiwa, lan ing. We terus nemtokake Enggo bareng kanggo vertex anggere isih ana vertex ing komponen disambungake saka vertex kita miwiti karo sing kita wis ora diutus tanggi kanggo. Banjur baleni tumindak iki kanggo kabeh komponen sing disambungake.
Yen ana pinggiran antarane vertices sing tiba ing pemisahan padha, iku ora angel kanggo nemokake siklus aneh ing graph, kang dikenal (lan cukup temenan) mokal ing grafik bipartit. Yen ora, kita duwe partisi sing bener, tegese grafik kasebut bipartit.
Biasane, algoritma iki dileksanakake nggunakake utawa . Ing basa imperatif, telusuran paling jero biasane digunakake amarga rada prasaja lan ora mbutuhake struktur data tambahan. Aku uga milih depth-first search amarga luwih tradisional.
Mangkono, kita teka ing skema ing ngisor iki. Kita ngliwati verteks grafik kanthi nggunakake telusuran sing paling jero lan nemtokake saham kasebut, ngganti jumlah panggabungan nalika kita pindhah ing pinggir. Yen kita nyoba nemtokake bagean menyang vertex sing wis duwe bagean sing ditugasake, kita bisa ngomong kanthi aman yen grafik kasebut ora bipartit. Wayahe kabeh vertices diutus nuduhake lan kita wis katon ing kabeh sudhut, kita duwe pemisahan apik.
Kemurnian petungan
Ing Haskell kita nganggep yen kabeh petungan resik. Nanging, yen iki pancene, kita ora duwe cara kanggo nyithak apa wae ing layar. Sakabehe, resik petungan dadi kesed sing ora ana siji resik alasan kanggo ngetung soko. Kabeh petungan sing kedadeyan ing program kasebut kudu ditindakake "najis" monggo IO.
Monad minangka cara kanggo makili petungan efek ing Haskell. Nerangake cara kerjane ngluwihi ruang lingkup kiriman iki. Katrangan sing apik lan jelas bisa diwaca nganggo basa Inggris .
Ing kene aku pengin nuduhake manawa sawetara monad, kayata IO, dileksanakake liwat sihir kompiler, meh kabeh liyane dileksanakake ing piranti lunak lan kabeh kalkulasi kasebut murni.
Ana akeh efek lan saben duwe monad dhewe. Iki minangka teori sing kuwat lan apik banget: kabeh monad ngetrapake antarmuka sing padha. Kita bakal ngomong babagan telung monad ing ngisor iki:
- Salah siji e a minangka pitungan sing ngasilake nilai saka jinis a utawa mbuwang pangecualian saka jinis e. Prilaku monad iki meh padha karo penanganan pangecualian ing basa imperatif: kesalahan bisa kejiret utawa diterusake. Bentenane utama yaiku monad rampung kanthi logis ing perpustakaan standar ing Haskell, dene basa imperatif biasane nggunakake mekanisme sistem operasi.
- State s a minangka pitungan sing ngasilake nilai jinis a lan nduweni akses menyang negara sing bisa diganti saka jinis s.
- Mungkin a. Monad Mungkin nyatakake komputasi sing bisa diselani sawayah-wayah kanthi mbalekake Apa-apa. Nanging, kita bakal pirembagan bab implementasine saka kelas MonadPlus kanggo jinis Mungkin, kang nuduhake efek ngelawan: iku pitungan sing bisa diselani sawayah-wayah kanthi ngasilake nilai tartamtu.
Implementasi algoritma
Kita duwe rong jinis data, Graph a lan Bigraph a b, sing pisanan nggambarake grafik kanthi titik-titik sing dilabeli karo nilai-nilai tipe a, lan nomer loro nuduhake grafik bipartit kanthi titik-titik sisih kiwa sing dilabeli karo nilai tipe a lan tengen. - vertex sisih diwenehi label karo nilai saka jinis b.
Iki dudu jinis perpustakaan Alga. Alga ora duwe perwakilan kanggo grafik bipartit sing ora diarahake. Aku nggawe jinis kaya iki kanggo gamblang.
Kita uga butuh fungsi helper kanthi tandha tangan ing ngisor iki:
-- Список соседей данной вершины.
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)Iku gampang kanggo ndeleng yen nalika panelusuran ambane-pisanan kita nemokake pinggiran konflik, siklus aneh dumunung ing ndhuwur tumpukan rekursi. Mangkono, kanggo mulihake, kita kudu ngilangi kabeh saka tumpukan rekursi nganti kedadeyan pisanan saka vertex pungkasan.
Kita ngleksanakake telusuran sing paling jero kanthi njaga nomer panggabungan asosiatif kanggo saben vertex. Tumpukan recursion bakal kanthi otomatis maintained liwat implementasine saka Functor kelas monad kita wis milih: kita mung kudu sijine kabeh vertex saka path menyang asil bali saka fungsi rekursif.
Ide pisananku yaiku nggunakake monad Salah siji, sing kayane ngetrapake efek sing dibutuhake. Implementasi pisanan sing daktulis cedhak banget karo pilihan iki. Nyatane, aku duwe limang implementasine beda ing sawijining titik lan pungkasane mapan ing siji liyane.
Kaping pisanan, kita kudu njaga macem-macem pengenal saham asosiatif - iki babagan Negara. Kapindho, kita kudu bisa mandheg nalika konflik dideteksi. Iki bisa dadi Monad kanggo Salah siji, utawa MonadPlus kanggo Mungkin. Bentenipun utama iku Salah siji bisa bali Nilai yen pitungan wis ora mandegake, lan Mungkin bali mung informasi bab iki ing kasus iki. Awit kita ora perlu Nilai kapisah kanggo sukses (iku wis disimpen ing Negara), kita milih Mungkin. Lan nalika kita kudu nggabungake efek saka rong monad, dheweke metu , sing sabenere nggabungake efek kasebut.
Kenapa aku milih jinis sing kompleks? Loro alasan. Kaping pisanan, implementasine meh padha karo imperatif. Kapindho, kita kudu ngapusi Nilai bali ing cilik saka konflik nalika bali saka recursion kanggo mulihake daur ulang aneh, kang luwih gampang kanggo nindakake ing Mungkin monad.
Mangkono kita entuk implementasine iki.
{-# 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)
Blok ngendi minangka inti saka algoritma. Aku bakal nyoba nerangake apa sing kedadeyan ing njero.
- inVertex minangka bagean saka telusuran sing paling jero ing ngendi kita ngunjungi puncak kanggo pisanan. Kene kita nemtokake nomer nuduhake menyang vertex lan mbukak onEdge ing kabeh tanggi. Iki uga ngendi kita mulihake tumpukan telpon: yen msum bali Nilai, kita push vertex v ana.
- onEdge minangka bagean ing ngendi kita ngunjungi pinggiran. Iki diarani kaping pindho kanggo saben pinggiran. Kene kita mriksa apa vertex ing sisih liyane wis dibukak, lan ngunjungi yen ora. Yen dibukak, kita mriksa apa pinggiran konflik. Yen iku, kita bali Nilai - ndhuwur banget tumpukan recursion, ngendi kabeh vertex liyane banjur bakal diselehake marang bali.
- processVertex mriksa saben vertex apa wis dibukak lan mbukak ing Vertex yen ora.
- dfs mbukak processVertex ing kabeh vertex.
Iku kabeh.
Sajarah tembung INLINE
Tembung INLINE ora ana ing implementasi pisanan saka algoritma kasebut; banjur muncul. Nalika aku nyoba kanggo golek implementasine luwih, Aku ketemu sing versi non-INLINE noticeably alon ing sawetara grafik. Ngelingi manawa fungsi semantik kudu padha, iki kaget banget. Malah wong liyo, ing mesin liyane karo versi GHC beda ora ana prabédan ngelingke.
Sawise nggunakake minggu maca output GHC inti, Aku bisa ndandani masalah karo siji baris INLINE eksplisit. Ing sawetara titik antarane GHC 8.4.4 lan GHC 8.6.5 optimizer mandheg nindakake iki ing dhewe.
Aku ora nyana nemokke rereget kuwi ing program Haskell. Nanging, sanajan saiki, pangoptimal kadhangkala nggawe kesalahan, lan tugas kita menehi pitunjuk. Contone, ing kene kita ngerti yen fungsi kasebut kudu inlined amarga inlined ing versi imperatif, lan iki minangka alasan kanggo menehi petunjuk marang compiler.
Apa sing kedadeyan sabanjure?
Banjur aku ngetrapake algoritma Hopcroft-Karp karo monad liyane, lan pungkasane program kasebut.
Thanks kanggo Google Summer of Code, aku entuk pengalaman praktis ing pemrograman fungsional, sing ora mung nulungi aku magang ing Jane Street ing musim panas sabanjure (Aku ora yakin manawa papan iki uga dikenal ing antarane para pamirsa Habr, nanging mung siji. saka sawetara ngendi sampeyan bisa panas kanggo melu program fungsi), nanging uga ngenalaken kula kanggo donya apik saka nglamar paradigma iki ing laku, Ngartekno beda saka pengalaman ing basa tradisional.
Source: www.habr.com