Musim panas lalu saya ikut serta Google Summer of Code - program untuk pelajar dari Google. Setiap tahun, penyelenggara memilih beberapa proyek Open Source, termasuk dari organisasi ternama seperti Meningkatkan.org и Yayasan Linux. Google mengundang siswa dari seluruh dunia untuk mengerjakan proyek ini.

Sebagai peserta Google Summer of Code 2019, saya mengerjakan proyek di dalam perpustakaan Ganggang dengan organisasi Haskell.org, yang mengembangkan bahasa Haskell - salah satu bahasa pemrograman fungsional paling terkenal. Alga adalah perpustakaan yang mewakili mengetik aman representasi untuk grafik di Haskell. Ini digunakan, misalnya, di semantik — perpustakaan Github yang membuat pohon semantik, grafik panggilan dan ketergantungan berdasarkan kode dan dapat membandingkannya. Proyek saya adalah menambahkan representasi tipe-aman untuk grafik bipartit dan algoritma untuk representasi tersebut.

Dalam posting ini saya akan berbicara tentang implementasi algoritma untuk memeriksa grafik bipartit di Haskell. Meskipun algoritme ini merupakan salah satu algoritme yang paling mendasar, penerapannya dengan indah dalam gaya fungsional memerlukan beberapa kali pengulangan dan memerlukan banyak kerja keras. Sebagai hasilnya, saya memilih implementasi dengan transformator monad.

Tentang diri saya

Nama saya Vasily Alferov, saya mahasiswa tahun keempat di HSE St. Sebelumnya di blog yang saya tulis tentang proyek saya tentang algoritma berparameter и tentang perjalanan ke ZuriHac. Saat ini saya sedang magang di Universitas Bergen di Norwegia, tempat saya berupaya melakukan pendekatan terhadap masalah ini Daftar Mewarnai. Minat saya mencakup algoritma berparameter dan pemrograman fungsional.

Tentang implementasi algoritma

kata pengantar

Siswa yang berpartisipasi dalam program ini sangat dianjurkan untuk membuat blog. Mereka memberi saya platform untuk blog Musim Panas Haskell. Artikel ini adalah terjemahannya Artikel, ditulis oleh saya di sana pada bulan Juli dalam bahasa Inggris, dengan kata pengantar singkat.

Pull Request dengan kode yang dimaksud dapat ditemukan di sini.

Anda dapat membaca tentang hasil pekerjaan saya (dalam bahasa Inggris) di sini.

Posting ini dimaksudkan untuk membiasakan pembaca dengan konsep dasar pemrograman fungsional, meskipun saya akan mencoba mengingat semua istilah yang digunakan ketika saatnya tiba.

Memeriksa grafik untuk bipartit

Algoritma untuk memeriksa suatu graf untuk bipartititas biasanya diberikan dalam kursus tentang algoritma sebagai salah satu algoritma graf yang paling sederhana. Idenya sangat jelas: pertama-tama kita menempatkan simpul-simpul di bagian kiri atau kanan, dan ketika ditemukan sisi yang bertentangan, kita menegaskan bahwa graf tersebut bukan bipartit.

Sedikit lebih detail: pertama kita letakkan beberapa titik di bagian kiri. Jelasnya, semua tetangga dari simpul ini harus terletak di lobus kanan. Selanjutnya, semua tetangga dari tetangga simpul ini harus terletak di lobus kiri, dan seterusnya. Kami terus menugaskan pembagian ke simpul-simpul selama masih ada simpul-simpul di komponen terhubung dari simpul yang kami mulai dan belum kami tetapkan tetangganya. Kami kemudian mengulangi tindakan ini untuk semua komponen yang terhubung.

Jika terdapat sisi di antara simpul-simpul yang berada dalam partisi yang sama, tidaklah sulit untuk menemukan siklus ganjil dalam graf tersebut, yang diketahui secara luas (dan jelas sekali) tidak mungkin dilakukan dalam graf bipartit. Jika tidak, kami memiliki partisi yang benar, yang berarti grafiknya bipartit.

Biasanya algoritma ini diimplementasikan menggunakan luasnya pencarian pertama или pencarian mendalam pertama. Dalam bahasa imperatif, pencarian mendalam pertama biasanya digunakan karena sedikit lebih sederhana dan tidak memerlukan struktur data tambahan. Saya juga memilih pencarian mendalam pertama karena lebih tradisional.

Jadi, kami sampai pada skema berikut. Kami melintasi simpul-simpul grafik menggunakan pencarian depth-first dan menetapkan pembagian padanya, mengubah jumlah pembagian saat kami bergerak di sepanjang tepinya. Jika kita mencoba menugaskan suatu bagian ke suatu titik yang telah mempunyai bagian yang ditetapkan, kita dapat mengatakan bahwa graf tersebut bukan graf bipartit. Saat semua simpul diberi bagian dan kita telah melihat semua sisinya, kita memiliki partisi yang bagus.

Kemurnian perhitungan

Di Haskell kami berasumsi bahwa semua perhitungan adalah bersih. Namun, jika ini benar-benar terjadi, kita tidak akan bisa mencetak apa pun ke layar. Sama sekali, bersih kalkulasinya males banget sampai gak ada satu pun membersihkan alasan untuk menghitung sesuatu. Semua perhitungan yang terjadi dalam program entah bagaimana dipaksakan "najis" monad IO.

Monads adalah cara untuk merepresentasikan perhitungan efek di Haskell. Menjelaskan cara kerjanya berada di luar cakupan postingan ini. Uraian yang baik dan jelas dapat dibaca dalam bahasa Inggris di sini.

Di sini saya ingin menunjukkan bahwa meskipun beberapa monad, seperti IO, diimplementasikan melalui sihir kompiler, hampir semua monad lainnya diimplementasikan dalam perangkat lunak dan semua perhitungan di dalamnya murni.

Ada banyak efek dan masing-masing memiliki monadnya sendiri. Ini adalah teori yang sangat kuat dan indah: semua monad mengimplementasikan antarmuka yang sama. Kami akan berbicara tentang tiga monad berikut:

Entah ea adalah perhitungan yang mengembalikan nilai tipe a atau memunculkan pengecualian tipe e. Perilaku monad ini sangat mirip dengan penanganan pengecualian dalam bahasa imperatif: kesalahan dapat ditangkap atau diteruskan. Perbedaan utamanya adalah monad diimplementasikan sepenuhnya secara logis di perpustakaan standar Haskell, sedangkan bahasa imperatif biasanya menggunakan mekanisme sistem operasi.
Status sa adalah kalkulasi yang mengembalikan nilai bertipe a dan memiliki akses ke status bertipe s yang bisa berubah.
Mungkin. Monad Maybe mengungkapkan komputasi yang dapat diinterupsi kapan saja dengan mengembalikan Nothing. Namun, kita akan membahas implementasi kelas MonadPlus untuk tipe Maybe, yang menyatakan efek sebaliknya: ini adalah perhitungan yang dapat dihentikan kapan saja dengan mengembalikan nilai tertentu.

Implementasi algoritma

Kita mempunyai dua tipe data yaitu Graf a dan Bigraph ab, yang pertama merepresentasikan graf yang simpul-simpulnya berlabel nilai bertipe a, dan yang kedua mewakili graf bipartit yang simpul-simpul sisi kirinya berlabel nilai bertipe a dan kanan. -simpul samping diberi label dengan nilai tipe b.

Ini bukan tipe dari perpustakaan Alga. Alga tidak memiliki representasi untuk graf bipartit tidak berarah. Saya membuat tipe seperti ini untuk kejelasan.

Kita juga memerlukan fungsi pembantu dengan tanda tangan berikut:

-- Список соседей данной вершины.
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)

Sangat mudah untuk melihat bahwa jika selama pencarian mendalam pertama kami menemukan tepi yang bertentangan, siklus ganjil terletak di atas tumpukan rekursi. Jadi, untuk memulihkannya, kita perlu memotong semuanya mulai dari tumpukan rekursi hingga kemunculan pertama dari simpul terakhir.

Kami menerapkan penelusuran yang mengutamakan kedalaman dengan mempertahankan larik asosiatif nomor-nomor yang dibagikan untuk setiap simpul. Tumpukan rekursi akan secara otomatis dipertahankan melalui implementasi kelas Functor dari monad yang telah kita pilih: kita hanya perlu memasukkan semua simpul dari jalur ke dalam hasil yang dikembalikan dari fungsi rekursif.

Ide pertama saya adalah menggunakan kedua monad, yang sepertinya mengimplementasikan efek yang kita perlukan. Implementasi pertama yang saya tulis sangat mirip dengan opsi ini. Faktanya, saya memiliki lima implementasi berbeda pada satu titik dan akhirnya memilih implementasi lainnya.

Pertama, kita perlu mempertahankan rangkaian pengidentifikasi saham yang asosiatif - ini adalah sesuatu tentang Negara. Kedua, kita harus bisa berhenti ketika konflik terdeteksi. Ini bisa berupa Monad untuk Salah Satunya, atau MonadPlus untuk Mungkin. Perbedaan utamanya adalah bahwa keduanya dapat mengembalikan nilai jika penghitungan belum dihentikan, dan mungkin hanya mengembalikan informasi tentang hal ini dalam kasus ini. Karena kita tidak memerlukan nilai terpisah untuk sukses (sudah disimpan di State), kita pilih Mungkin. Dan pada saat kita perlu menggabungkan efek dari dua monad, efek tersebut keluar transformator monad, yang secara tepat menggabungkan efek-efek ini.

Mengapa saya memilih tipe yang rumit? Dua alasan. Pertama, implementasinya ternyata sangat mirip dengan keharusan. Kedua, kita perlu memanipulasi nilai yang dikembalikan jika terjadi konflik saat kembali dari rekursi untuk memulihkan loop ganjil, yang lebih mudah dilakukan di monad Maybe.

Jadi kami mendapatkan implementasi ini.

{-# 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 Where adalah inti dari algoritma. Saya akan mencoba menjelaskan apa yang terjadi di dalamnya.

inVertex adalah bagian pencarian depth-first di mana kita mengunjungi vertex untuk pertama kalinya. Di sini kami menetapkan nomor berbagi ke simpul dan menjalankan onEdge pada semua tetangga. Di sinilah kita juga memulihkan tumpukan panggilan: jika msum mengembalikan nilai, kita mendorong vertex v di sana.
onEdge adalah bagian di mana kita mengunjungi edge. Ini dipanggil dua kali untuk setiap sisi. Di sini kita memeriksa apakah simpul di sisi lain telah dikunjungi, dan mengunjunginya jika belum. Jika dikunjungi, kami memeriksa apakah tepinya bertentangan. Jika ya, kami mengembalikan nilainya - bagian paling atas dari tumpukan rekursi, tempat semua simpul lainnya akan ditempatkan saat kembali.
processVertex memeriksa setiap simpul apakah telah dikunjungi dan menjalankan inVertex jika belum.
dfs menjalankan processVertex di semua simpul.

Itu saja.

Sejarah kata INLINE

Kata INLINE tidak ada dalam implementasi algoritma yang pertama; namun muncul kemudian. Ketika saya mencoba mencari implementasi yang lebih baik, saya menemukan bahwa versi non-INLINE terasa lebih lambat pada beberapa grafik. Mengingat secara semantik fungsinya harus bekerja sama, ini sangat mengejutkan saya. Lebih anehnya lagi, pada mesin lain dengan versi GHC yang berbeda tidak ada perbedaan yang mencolok.

Setelah menghabiskan seminggu membaca keluaran GHC Core, saya dapat memperbaiki masalah dengan satu baris INLINE eksplisit. Pada titik tertentu antara GHC 8.4.4 dan GHC 8.6.5, pengoptimal berhenti melakukan ini dengan sendirinya.

Saya tidak menyangka akan menemukan hal-hal buruk seperti itu dalam pemrograman Haskell. Namun, bahkan saat ini, pengoptimal terkadang membuat kesalahan, dan tugas kita adalah memberi mereka petunjuk. Misalnya, di sini kita tahu bahwa fungsi tersebut harus disisipkan karena disisipkan dalam versi imperatif, dan ini adalah alasan untuk memberikan petunjuk kepada kompiler.

Apa yang terjadi selanjutnya?

Kemudian saya mengimplementasikan algoritma Hopcroft-Karp dengan monad lain dan itulah akhir dari program.

Berkat Google Summer of Code, saya memperoleh pengalaman praktis dalam pemrograman fungsional, yang tidak hanya membantu saya mendapatkan magang di Jane Street pada musim panas berikutnya (saya tidak yakin seberapa terkenal tempat ini bahkan di kalangan pembaca Habr yang berpengetahuan luas, tapi itu salah satunya dari sedikit di mana Anda dapat terlibat dalam pemrograman fungsional di musim panas), tetapi juga memperkenalkan saya pada dunia indah dalam menerapkan paradigma ini dalam praktik, yang sangat berbeda dari pengalaman saya dalam bahasa tradisional.

Sumber: www.habr.com

GSoC 2019: Memeriksa grafik untuk trafo bipartit dan monad