Musim panas lalu saya mengambil bahagian Summer of Code Google - program untuk pelajar daripada Google. Setiap tahun, penganjur memilih beberapa projek Sumber Terbuka, termasuk daripada organisasi terkenal seperti Boost.org и Yayasan Linux. Google menjemput pelajar dari seluruh dunia untuk mengusahakan projek ini.

Sebagai peserta dalam Kod Musim Panas Google 2019, saya melakukan projek dalam perpustakaan Alga dengan organisasi Haskell.org, yang sedang membangunkan bahasa Haskell - salah satu bahasa pengaturcaraan berfungsi yang paling terkenal. Alga ialah perpustakaan yang mewakili taip selamat perwakilan untuk graf dalam Haskell. Ia digunakan, sebagai contoh, dalam semantik — perpustakaan Github yang membina pepohon semantik, graf panggilan dan pergantungan berdasarkan kod dan boleh membandingkannya. Projek saya adalah untuk menambah perwakilan jenis selamat untuk graf dwipartit dan algoritma untuk perwakilan itu.

Dalam siaran ini saya akan bercakap tentang pelaksanaan algoritma saya untuk menyemak graf untuk bipartiteness dalam Haskell. Walaupun algoritma adalah salah satu yang paling asas, melaksanakannya dengan cantik dalam gaya berfungsi membawa saya beberapa lelaran dan memerlukan banyak kerja. Akibatnya, saya memutuskan pelaksanaan dengan pengubah monad.

Mengenai Saya

Nama saya Vasily Alferov, saya pelajar tahun empat di St. Petersburg HSE. Tadi dalam blog saya tulis mengenai projek saya tentang algoritma parameter и tentang perjalanan ke ZuriHac. Sekarang saya sedang menjalani latihan amali di Universiti Bergen di Norway, di mana saya sedang mengusahakan pendekatan kepada masalah tersebut Mewarna Senarai. Minat saya termasuk algoritma berparameter dan pengaturcaraan berfungsi.

Mengenai pelaksanaan algoritma

Perutusan

Pelajar yang menyertai program ini amat digalakkan untuk membuat blog. Mereka menyediakan saya platform untuk blog Musim panas Haskell. Artikel ini adalah terjemahan Perkara, ditulis oleh saya di sana pada bulan Julai dalam bahasa Inggeris, dengan mukadimah ringkas.

Permintaan Tarik dengan kod berkenaan boleh didapati di sini.

Anda boleh membaca tentang hasil kerja saya (dalam bahasa Inggeris) di sini.

Catatan ini menganggap bahawa pembaca sudah biasa dengan konsep asas dalam pengaturcaraan berfungsi, walaupun saya akan cuba mengingati semua istilah yang digunakan apabila tiba masanya.

Menyemak graf untuk bipartit

Algoritma untuk menyemak graf untuk bipartiteness biasanya diberikan dalam kursus tentang algoritma sebagai salah satu algoritma graf yang paling mudah. Ideanya adalah mudah: mula-mula kita entah bagaimana meletakkan bucu di bahagian kiri atau kanan, dan apabila kelebihan bercanggah ditemui, kami menegaskan bahawa graf itu bukan dwipartit.

Sedikit lebih terperinci: mula-mula kita letakkan beberapa bucu di bahagian kiri. Jelas sekali, semua jiran puncak ini mesti terletak di lobus kanan. Selanjutnya, semua jiran jiran bucu ini mesti terletak di lobus kiri, dan seterusnya. Kami terus memberikan bahagian kepada bucu selagi masih terdapat bucu dalam komponen bucu yang disambungkan yang kita mulakan dengan yang belum kita tetapkan kepada jiran. Kami kemudian mengulangi tindakan ini untuk semua komponen yang disambungkan.

Jika terdapat kelebihan antara bucu yang jatuh ke dalam partition yang sama, tidak sukar untuk mencari kitaran ganjil dalam graf, yang diketahui secara meluas (dan agak jelas) mustahil dalam graf dwipartit. Jika tidak, kami mempunyai partition yang betul, yang bermaksud graf adalah bipartit.

Biasanya, algoritma ini dilaksanakan menggunakan keluasan pencarian pertama atau carian pertama mendalam. Dalam bahasa imperatif, carian depth-first biasanya digunakan kerana ia lebih mudah sedikit dan tidak memerlukan struktur data tambahan. Saya juga memilih carian mendalam-pertama kerana ia lebih tradisional.

Oleh itu, kami datang ke skema berikut. Kami merentasi bucu graf menggunakan carian mendalam-pertama dan memberikan bahagian kepada mereka, menukar nombor bahagian semasa kami bergerak di sepanjang tepi. Jika kita cuba menetapkan bahagian pada puncak yang sudah mempunyai bahagian yang ditetapkan, kita boleh mengatakan dengan selamat bahawa graf itu bukan dwipartit. Apabila semua bucu diberikan bahagian dan kami telah melihat semua tepi, kami mempunyai partition yang baik.

Kesucian pengiraan

Dalam Haskell kami menganggap bahawa semua pengiraan adalah bersih. Walau bagaimanapun, jika ini benar-benar berlaku, kami tidak akan mempunyai cara untuk mencetak apa-apa ke skrin. sama sekali, bersih pengiraan sangat malas sehingga tidak ada satu pun bersih sebab untuk mengira sesuatu. Semua pengiraan yang berlaku dalam program ini entah bagaimana dipaksa masuk "najis" monad IO.

Monad ialah cara untuk mewakili pengiraan dengan kesan dalam Haskell. Menjelaskan cara mereka berfungsi adalah di luar skop siaran ini. Penerangan yang baik dan jelas boleh dibaca dalam bahasa Inggeris di sini.

Di sini saya ingin menunjukkan bahawa walaupun beberapa monad, seperti IO, dilaksanakan melalui sihir pengkompil, hampir semua yang lain dilaksanakan dalam perisian dan semua pengiraan di dalamnya adalah tulen.

Terdapat banyak kesan dan masing-masing mempunyai monad sendiri. Ini adalah teori yang sangat kuat dan cantik: semua monad melaksanakan antara muka yang sama. Kami akan bercakap tentang tiga monad berikut:

Sama ada ea ialah pengiraan yang mengembalikan nilai jenis a atau membuang pengecualian jenis e. Tingkah laku monad ini sangat serupa dengan pengendalian pengecualian dalam bahasa imperatif: ralat boleh ditangkap atau diteruskan. Perbezaan utama ialah monad dilaksanakan sepenuhnya secara logik dalam perpustakaan standard di Haskell, manakala bahasa imperatif biasanya menggunakan mekanisme sistem pengendalian.
Keadaan sa ialah pengiraan yang mengembalikan nilai jenis a dan mempunyai akses kepada keadaan boleh ubah jenis s.
Mungkin a. Monad Maybe menyatakan pengiraan yang boleh diganggu pada bila-bila masa dengan tidak mengembalikan Apa-apa. Walau bagaimanapun, kita akan bercakap tentang pelaksanaan kelas MonadPlus untuk jenis Maybe, yang menyatakan kesan yang bertentangan: ia adalah pengiraan yang boleh diganggu pada bila-bila masa dengan mengembalikan nilai tertentu.

Pelaksanaan algoritma

Kami mempunyai dua jenis data, Graf a dan Bigraph ab, yang pertama mewakili graf dengan bucu yang dilabelkan dengan nilai jenis a, dan yang kedua mewakili graf dwipartit dengan bucu sebelah kiri yang dilabelkan dengan nilai jenis a dan kanan. -bucu sisi dilabelkan dengan nilai jenis b.

Ini bukan jenis daripada perpustakaan Alga. Alga tidak mempunyai perwakilan untuk graf dwipartit tidak terarah. Saya membuat jenis seperti ini untuk kejelasan.

Kami juga memerlukan fungsi pembantu dengan tandatangan 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)

Adalah mudah untuk melihat bahawa jika semasa carian mendalam-pertama kami menemui kelebihan yang bercanggah, kitaran ganjil terletak di atas timbunan ulangan. Oleh itu, untuk memulihkannya, kita perlu memotong segala-galanya daripada timbunan rekursi sehingga kejadian pertama puncak terakhir.

Kami melaksanakan carian mendalam-pertama dengan mengekalkan tatasusunan bersekutu nombor bahagian untuk setiap bucu. Tindanan rekursi akan dikekalkan secara automatik melalui pelaksanaan kelas Functor monad yang telah kami pilih: kami hanya perlu meletakkan semua bucu dari laluan ke dalam hasil yang dikembalikan daripada fungsi rekursif.

Idea pertama saya ialah menggunakan Either monad, yang nampaknya melaksanakan dengan tepat kesan yang kita perlukan. Pelaksanaan pertama yang saya tulis sangat dekat dengan pilihan ini. Malah, saya mempunyai lima pelaksanaan berbeza pada satu ketika dan akhirnya menyelesaikan satu lagi.

Pertama, kita perlu mengekalkan tatasusunan bersekutu pengecam bahagian - ini adalah sesuatu tentang Negeri. Kedua, kita perlu boleh berhenti apabila konflik dikesan. Ini boleh sama ada Monad untuk Sama ada, atau MonadPlus untuk Mungkin. Perbezaan utama ialah Sama ada boleh mengembalikan nilai jika pengiraan tidak dihentikan, dan Mungkin hanya mengembalikan maklumat tentang perkara ini dalam kes ini. Memandangkan kami tidak memerlukan nilai yang berasingan untuk kejayaan (ia sudah disimpan dalam Negeri), kami memilih Mungkin. Dan pada masa ini apabila kita perlu menggabungkan kesan dua monad, ia keluar pengubah monad, yang menggabungkan kesan ini dengan tepat.

Mengapa saya memilih jenis yang kompleks? Dua sebab. Pertama, pelaksanaannya ternyata sangat serupa dengan imperatif. Kedua, kita perlu memanipulasi nilai pulangan sekiranya berlaku konflik apabila kembali dari rekursi untuk memulihkan gelung ganjil, yang lebih mudah dilakukan dalam monad Maybe.

Oleh itu kita mendapat pelaksanaan 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 di mana adalah teras algoritma. Saya akan cuba menerangkan apa yang berlaku di dalamnya.

inVertex ialah bahagian carian pertama mendalam di mana kami melawati bucu untuk kali pertama. Di sini kami memberikan nombor kongsi ke puncak dan menjalankan onEdge pada semua jiran. Di sini juga kami memulihkan timbunan panggilan: jika msum mengembalikan nilai, kami menolak vertex v di sana.
onEdge ialah bahagian di mana kita melawat tepi. Ia dipanggil dua kali untuk setiap tepi. Di sini kita menyemak sama ada bucu di sisi lain telah dilawati, dan melawatinya jika tidak. Jika dilawati, kami menyemak sama ada kelebihan itu bercanggah. Jika ya, kami mengembalikan nilai - bahagian paling atas timbunan rekursi, di mana semua bucu lain kemudiannya akan diletakkan apabila dikembalikan.
processVertex menyemak setiap bucu sama ada ia telah dilawati dan menjalankan inVertex padanya jika tidak.
dfs menjalankan processVertex pada semua bucu.

Itu sahaja.

Sejarah perkataan INLINE

Perkataan INLINE bukan dalam pelaksanaan pertama algoritma; ia muncul kemudian. Apabila saya cuba mencari pelaksanaan yang lebih baik, saya mendapati bahawa versi bukan DALAM TALIAN nyata lebih perlahan pada sesetengah graf. Memandangkan secara semantik fungsi harus berfungsi sama, ini sangat mengejutkan saya. Lebih asing lagi, pada mesin lain dengan versi GHC yang berbeza tidak ada perbezaan yang ketara.

Selepas menghabiskan seminggu membaca output Teras GHC, saya dapat menyelesaikan masalah dengan satu baris INLINE eksplisit. Pada satu ketika antara GHC 8.4.4 dan GHC 8.6.5 pengoptimum berhenti melakukan ini sendiri.

Saya tidak menjangka akan menghadapi kotoran seperti itu dalam pengaturcaraan Haskell. Walau bagaimanapun, walaupun pada hari ini, pengoptimum kadangkala melakukan kesilapan, dan menjadi tugas kita untuk memberi petunjuk kepada mereka. Sebagai contoh, di sini kita tahu bahawa fungsi itu harus sebaris kerana ia sebaris dalam versi imperatif, dan ini adalah sebab untuk memberi petunjuk kepada pengkompil.

Apa yang berlaku seterusnya?

Kemudian saya melaksanakan algoritma Hopcroft-Karp dengan monad lain, dan itu adalah penghujung program.

Terima kasih kepada Kod Musim Panas Google, saya memperoleh pengalaman praktikal dalam pengaturcaraan berfungsi, yang bukan sahaja membantu saya mendapat latihan di Jane Street pada musim panas berikutnya (saya tidak pasti betapa terkenal tempat ini walaupun dalam kalangan penonton Habr yang berpengetahuan, tetapi ia adalah satu daripada beberapa tempat di mana anda boleh musim panas untuk terlibat dalam pengaturcaraan berfungsi), tetapi juga memperkenalkan saya kepada dunia yang mengagumkan dalam menerapkan paradigma ini dalam amalan, jauh berbeza daripada pengalaman saya dalam bahasa tradisional.

Sumber: www.habr.com

GSoC 2019: Menyemak graf untuk transformer dwipartit dan monad