Usum panas kamari kuring milu - program pikeun siswa ti Google. Unggal taun, panitia milih sababaraha proyék Open Source, kalebet ti organisasi anu terkenal sapertos и . Google ngajak murid ti sakumna dunya pikeun ngerjakeun proyék ieu.
Salaku pamilon dina Google Summer of Code 2019, kuring ngalakukeun proyék di jero perpustakaan jeung organisasi , nu ngembangkeun basa Haskell - salah sahiji basa programming fungsional nu kawentar. Alga mangrupakeun perpustakaan anu ngagambarkeun ngagambarkeun grafik dina Haskell. Hal ieu dipaké, contona, dina - perpustakaan Github anu ngawangun tangkal semantik, panggero jeung kagumantungan grafik dumasar kana kode sarta bisa ngabandingkeun aranjeunna. Proyék kuring nyaéta pikeun nambihan perwakilan anu aman pikeun grafik bipartit sareng algoritma pikeun perwakilan éta.
Dina tulisan ieu kuring bakal ngobrol ngeunaan palaksanaan algoritma kuring pikeun mariksa grafik pikeun bipartiteness di Haskell. Sanaos algoritmana mangrupikeun salah sahiji anu paling dasar, ngalaksanakeunana sacara saé dina gaya fungsional nyandak sababaraha iterasi sareng peryogi seueur padamelan. Hasilna, kuring netep dina palaksanaan sareng trafo monad.
ngeunaan Kuring
Nami abdi Vasily Alferov, abdi murid taun kaopat di St. Petersburg HSE. Tadi dina blog kuring nulis и . Ayeuna abdi nuju magang di di Norwégia, dimana Kuring keur dipake dina pendekatan kana masalah . Kapentingan kuring kalebet algoritma parameter sareng program fungsional.
Ngeunaan palaksanaan algoritma
foreword
Siswa anu milu dina program éta didorong pisan pikeun blog. Aranjeunna masihan kuring platform pikeun blog . Artikel ieu mangrupa tarjamahan , ditulis ku kuring aya dina bulan Juli dina basa Inggris, kalawan pramuka pondok.
Tarik Request kalawan kode sual bisa kapanggih .
Anjeun tiasa maca ngeunaan hasil pagawéan kuring (dina basa Inggris) .
Tulisan ieu dimaksudkeun pikeun familiarize pamaca sareng konsép dasar dina program fungsional, sanaos kuring bakal nyobian ngelingan sadaya istilah anu dianggo nalika waktosna.
Mariksa grafik pikeun bipartiteness
Algoritma pikeun mariksa grafik pikeun bipartiteness biasana dirumuskeun dina kursus ngeunaan algoritma salaku salah sahiji algoritma grafik pangbasajanna. Ide na lugas: kahiji urang kumaha bae nempatkeun vertices dina babagi kénca atawa katuhu, sarta lamun tepi conflicting kapanggih, urang negeskeun yén grafik teu bipartite.
A saeutik leuwih jéntré: mimiti urang nempatkeun sababaraha vertex dina dibagikeun kénca. Jelas, sadaya tatanggana tina vertex ieu kedah tempatna di lobus katuhu. Salajengna, sadaya tatanggana tatanggana vertex ieu kudu tempatna di lobus kénca, jeung saterusna. Urang neruskeun assigning biasa mun vertex salami aya kénéh vertex dina komponén disambungkeun tina vertex kami dimimitian ku nu urang teu ditugaskeun tatanggana. Urang lajeng ngulang aksi ieu pikeun sakabéh komponén disambungkeun.
Lamun aya an tepi antara vertex nu digolongkeun kana partisi sarua, teu hese neangan hiji siklus ganjil dina grafik, nu geus dipikawanoh lega (jeung rada écés) teu mungkin dina grafik bipartite. Upami teu kitu, urang gaduh partisi anu leres, anu hartosna grafikna bipartit.
Biasana, algoritma ieu dilaksanakeun nganggo atawa . Dina basa imperatif, pilarian jero-heula biasana dipaké sabab rada basajan tur teu merlukeun struktur data tambahan. Kuring ogé milih pilarian jero-heula sabab leuwih tradisional.
Ku kituna, urang datang ka skéma handap. Urang nyebrang titik-titik tina grafik ngagunakeun pilarian jero-heula tur napelkeun biasa ka aranjeunna, ngarobah jumlah dibagikeun nalika urang mindahkeun sapanjang tepi. Lamun urang nyoba napelkeun dibagikeun ka vertex nu geus boga dibagikeun ditugaskeun, urang aman bisa disebutkeun yen grafik teu bipartite. Momen sadaya vertices ditugaskeun dibagikeun sarta kami geus melong sagala edges, urang boga partisi alus.
Purity tina itungan
Dina Haskell kami nganggap yén sakabéh itungan téh beresih. Nanging, upami ieu leres-leres, urang moal gaduh cara pikeun nyitak nanaon kana layar. Sakabehna, bersih itungan nu puguh teu aya beresih alesan keur ngitung hiji hal. Kabéh itungan lumangsung dina program nu kumaha bae kapaksa kana "najis" monyét IO.
Monads mangrupakeun cara pikeun ngagambarkeun itungan kalawan épék di Haskell. Ngajelaskeun kumaha aranjeunna jalanna saluareun ruang lingkup tulisan ieu. Katerangan anu saé sareng jelas tiasa dibaca dina basa Inggris .
Di dieu abdi hoyong nunjuk kaluar yén bari sababaraha monads, kayaning IO, dilaksanakeun ngaliwatan magic kompiler, ampir kabéh séjén dilaksanakeun dina software sarta sakabeh itungan di antarana murni.
Aya seueur épék sareng masing-masing gaduh monad sorangan. Ieu mangrupikeun téori anu kuat sareng éndah: sadaya monad ngalaksanakeun antarmuka anu sami. Urang bakal ngobrol ngeunaan tilu monads ieu:
- Boh ea mangrupakeun itungan nu balik hiji nilai tipe a atanapi throws iwal tipe e. Paripolah monad ieu mirip pisan sareng penanganan iwal dina basa imperatif: kasalahan tiasa kapendak atanapi diteruskeun. Beda utama nyaéta monad sacara logis dilaksanakeun dina perpustakaan standar di Haskell, sedengkeun basa imperatif biasana ngagunakeun mékanisme sistem operasi.
- Nagara sa nyaéta itungan nu mulih hiji nilai tipe a sarta miboga aksés ka kaayaan mutable tipe s.
- Meureun a. The Mungkin monad expresses itungan nu bisa interrupted iraha wae ku mulang Euweuh. Najan kitu, urang bakal ngobrol ngeunaan palaksanaan kelas MonadPlus pikeun tipe Meureun, nu expresses efek sabalikna: eta mangrupakeun itungan nu bisa interrupted iraha wae ku balik hiji nilai husus.
Palaksanaan algoritma
Kami ngagaduhan dua jinis data, Graph a sareng Bigraph ab, anu kahiji ngagambarkeun grafik kalayan titik-titik anu dilabélan nilai-nilai tipe a, sareng anu kadua ngagambarkeun grafik bipartit sareng titik-titik sisi kénca dilabélan ku nilai-nilai tipe a sareng katuhu. - titik sisi dilabélan ku nilai tipe b.
Ieu sanés jinis ti perpustakaan Alga. Alga teu gaduh perwakilan pikeun grafik bipartit anu teu diarahkeun. Kuring ngadamel jinis sapertos kieu pikeun kajelasan.
Urang ogé peryogi fungsi pembantu kalayan tanda tangan ieu:
-- Список соседей данной вершины.
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)Ieu gampang pikeun nempo yén lamun salila pilarian jero-heula kami kapanggih tepi conflicting, siklus ganjil perenahna di luhureun tumpukan recursion. Ku kituna, pikeun mulangkeun eta, urang kudu neukteuk off sagalana ti tumpukan recursion nepi ka lumangsungna mimiti vertex panungtungan.
Urang ngalaksanakeun pilarian jero-heula ku ngajaga hiji Asép Sunandar Sunarya associative angka dibagikeun pikeun tiap vertex. Tumpukan recursion bakal otomatis dijaga ngaliwatan palaksanaan kelas Functor tina monad kami geus dipilih: urang ngan bakal perlu nempatkeun sagala vertex ti jalur kana hasil balik ti fungsi recursive.
Gagasan munggaran kuring nyaéta ngagunakeun Boh monad, anu sigana ngalaksanakeun épék anu urang peryogikeun. Palaksanaan munggaran kuring nyerat caket pisan kana pilihan ieu. Kanyataanna, kuring kungsi lima palaksanaan béda dina hiji titik sarta ahirna netep dina hiji sejen.
Firstly, urang kudu ngajaga hiji Asép Sunandar Sunarya associative of share identifiers - ieu hal ngeunaan Nagara. Kadua, urang kedah tiasa ngeureunkeun nalika aya konflik dideteksi. Ieu tiasa janten Monad pikeun Boh, atanapi MonadPlus pikeun Meureun. Beda utama nyaeta Boh bisa balik nilai a lamun itungan teu dieureunkeun, sarta Meureun balik ngan informasi ngeunaan ieu dina hal ieu. Kusabab urang henteu peryogi nilai anu misah pikeun suksés (éta parantos disimpen di Nagara), urang milih Meureun. Sareng dina waktos urang kedah ngagabungkeun épék dua monad, aranjeunna kaluar , nu persis ngagabungkeun épék ieu.
Naha kuring milih jinis kompleks sapertos kitu? Dua alesan. Firstly, palaksanaan tétéla pisan sarupa imperatif. Kadua, urang kedah ngamanipulasi nilai balik bisi konflik nalika balik deui ti recursion mulangkeun loop ganjil, nu loba gampang ngalakukeun dina meureun monad.
Ku kituna urang meunang palaksanaan ieu.
{-# 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 dimana mangrupikeun inti algoritma. Kuring bakal nyobian ngajelaskeun naon anu lumangsung di jerona.
- inVertex mangrupikeun bagian tina pamilarian anu paling jero dimana urang nganjang ka vertex pikeun kahiji kalina. Di dieu urang napelkeun angka dibagikeun ka vertex tur ngajalankeun onEdge on sakabeh tatanggana. Ieu oge dimana urang balikkeun tumpukan panggero: lamun msum balik nilai a, urang nyorong vertex v aya.
- onEdge teh bagian dimana urang didatangan tepi. Disebut dua kali pikeun unggal sisi. Di dieu urang pariksa lamun vertex di sisi séjén geus dilongok, sarta didatangan eta lamun henteu. Mun dilongok, urang pariksa naha tepi ka conflicting. Lamun kitu, urang balikkeun nilai - pisan luhureun tumpukan recursion, dimana sakabeh vertices séjén lajeng bakal disimpen kana balik.
- processVertex pariksa keur unggal vertex naha éta geus dilongok tur ngajalankeun inVertex dina eta lamun henteu.
- dfs ngajalankeun processVertex dina sakabéh vertex.
Éta hungkul.
Sajarah kecap INLINE
Kecap INLINE henteu aya dina palaksanaan mimiti algoritma; éta muncul engké. Nalika kuring diusahakeun neangan palaksanaan hadé, Kuring manggihan yén versi non-INLINE éta noticeably laun dina sababaraha grafik. Tempo yén semantically fungsi kedah dianggo sami, ieu greatly kaget kuring. Malah muhrim, dina mesin sejen kalawan versi béda tina GHC euweuh bédana noticeable.
Saatos nyéépkeun saminggu pikeun maca kaluaran GHC Core, kuring tiasa ngalereskeun masalah sareng hiji garis INLINE anu eksplisit. Di sawatara titik antara GHC 8.4.4 sarta GHC 8.6.5 optimizer eureun ngalakukeun ieu sorangan.
Kuring teu nyangka sapatemon kokotor misalna dina programming Haskell. Sanajan kitu, sanajan kiwari, optimizers kadang nyieun kasalahan, sarta éta tugas urang pikeun masihan aranjeunna petunjuk. Contona, di dieu urang terang yén fungsi kudu inlined sabab geus inlined dina versi imperatif, sarta ieu alesan pikeun masihan kompiler hint a.
Naon anu lumangsung saterusna?
Teras kuring ngalaksanakeun algoritma Hopcroft-Karp sareng monad anu sanés, sareng éta tungtung program.
Hatur nuhun kana Google Summer of Code, abdi nampi pangalaman praktis dina program fungsional, anu henteu ngan ukur ngabantosan abdi magang di Jane Street dina usum panas di handap ieu (Kuring henteu yakin kumaha kawéntar tempat ieu bahkan diantara pamiarsa Habr anu terang, tapi éta salah sahiji tina sababaraha dimana anjeun tiasa usum panas pikeun kalibet dina programming hanca), tapi ogé ngawanohkeun kuring ka dunya éndah nerapkeun paradigma ieu dina prakna, nyata béda ti pangalaman kuring dina basa tradisional.
sumber: www.habr.com