Keçən yay mən iştirak etdim - Google-dan tələbələr üçün proqram. Təşkilatçılar hər il bir neçə Açıq Mənbə layihəsini, o cümlədən tanınmış təşkilatlardan seçirlər и . Google bütün dünyadan olan tələbələri bu layihələr üzərində işləməyə dəvət edir.
Google Summer of Code 2019-un iştirakçısı kimi mən kitabxana daxilində bir layihə etdim təşkilatla , ən məşhur funksional proqramlaşdırma dillərindən biri olan Haskell dilini inkişaf etdirir. Alga təmsil edən kitabxanadır Haskelldə qrafiklər üçün təmsil. Bu, məsələn, istifadə olunur — kod əsasında semantik ağaclar, zənglər və asılılıq qrafikləri yaradan və onları müqayisə edə bilən Github kitabxanası. Mənim layihəm bu təqdimat üçün ikitərəfli qrafiklər və alqoritmlər üçün təhlükəsiz bir təqdimat əlavə etmək idi.
Bu yazıda Haskelldə ikitərəflilik üçün qrafiki yoxlamaq üçün alqoritmin tətbiqi haqqında danışacağam. Alqoritm ən əsaslardan biri olsa da, onu funksional üslubda gözəl şəkildə həyata keçirmək mənə bir neçə iterasiya etdi və kifayət qədər çox iş tələb etdi. Nəticədə, monad transformatorları ilə həyata keçirməyə qərar verdim.
About Me
Mənim adım Vasili Alferov, mən Sankt-Peterburq SƏTƏM-in dördüncü kurs tələbəsiyəm. Əvvəllər bloqda yazmışdım и . Hazırda stajdayam problemə yanaşmalar üzərində işlədiyim Norveçdə . Maraqlarım arasında parametrləşdirilmiş alqoritmlər və funksional proqramlaşdırma daxildir.
Alqoritmin həyata keçirilməsi haqqında
Müqəddimə
Proqramda iştirak edən tələbələr bloq yazmağa həvəsləndirilir. Mənə bloq üçün platforma təqdim etdilər . Bu məqalə tərcümədir , mənim tərəfimdən iyul ayında ingilis dilində qısa ön sözlə yazılmışdır.
Sözügedən kodla Pull Sorğunu tapa bilərsiniz .
İşimin nəticələri haqqında oxuya bilərsiniz (ingilis dilində) .
Bu yazı oxucunu funksional proqramlaşdırmanın əsas anlayışları ilə tanış etmək məqsədi daşıyır, baxmayaraq ki, vaxtı gələndə istifadə olunan bütün terminləri xatırlamağa çalışacağam.
Qrafiklərin ikitərəflilik üçün yoxlanılması
Qrafikin ikitərəfliliyin yoxlanılması alqoritmi adətən ən sadə qrafik alqoritmlərindən biri kimi alqoritmlər kursunda verilir. Onun fikri sadədir: əvvəlcə biz sol və ya sağ payda təpələri birtəhər qoyuruq və ziddiyyətli kənar tapıldıqda, qrafikin ikitərəfli olmadığını təsdiq edirik.
Bir az daha təfərrüat: əvvəlcə sol hissəyə bir zirvə qoyuruq. Aydındır ki, bu təpənin bütün qonşuları sağ lobda yatmalıdır. Bundan əlavə, bu təpənin qonşularının bütün qonşuları sol lobda yatmalıdır və s. Başladığımız təpənin əlaqəli komponentində qonşuları təyin etmədiyimiz təpələr olduğu müddətcə biz təpələrə pay təyin etməyə davam edirik. Sonra bu hərəkəti bütün bağlı komponentlər üçün təkrarlayırıq.
Eyni bölməyə düşən təpələr arasında kənar varsa, ikitərəfli qrafikdə geniş şəkildə məlum olan (və tamamilə açıq-aydın) qeyri-mümkün olan qrafikdə tək dövrə tapmaq çətin deyil. Əks halda, düzgün bölməmiz var, yəni qrafik ikitərəflidir.
Tipik olaraq, bu alqoritm istifadə edərək həyata keçirilir və ya . İmperativ dillərdə, bir az daha sadə olduğundan və əlavə məlumat strukturları tələb olunmadığından, ilk növbədə dərindən axtarış adətən istifadə olunur. Mən də daha ənənəvi olduğu üçün dərindən birinci axtarışı seçdim.
Beləliklə, aşağıdakı sxemə gəldik. Biz ilk olaraq dərinlik axtarışından istifadə edərək qrafikin təpələrini keçirik və onlara paylar təyin edirik, kənar boyunca hərəkət edərkən payın sayını dəyişirik. Artıq pay təyin edilmiş təpəyə pay təyin etməyə çalışsaq, qrafikin ikitərəfli olmadığını əminliklə deyə bilərik. Bütün təpələrə bir pay təyin edildiyi və bütün kənarlara baxdığımız anda yaxşı bir bölməmiz var.
Hesablamaların təmizliyi
Haskelldə bütün hesablamaların belə olduğunu güman edirik təmiz. Ancaq bu, həqiqətən də belə olsaydı, ekrana heç bir şey çap etmək üçün heç bir yolumuz olmazdı. Bütün, təmiz hesablamalar o qədər tənbəldir ki, biri yoxdur təmiz bir şeyi hesablamaq üçün səbəblər. Proqramda baş verən bütün hesablamalar birtəhər məcbur edilir "murdar" monad IO.
Monadlar hesablamaları təmsil etmək üçün bir yoldur effektləri Haskelldə. Onların necə işlədiyini izah etmək bu yazının əhatə dairəsi xaricindədir. Yaxşı və aydın təsviri ingilis dilində oxumaq olar .
Burada qeyd etmək istəyirəm ki, bəzi monadlar, məsələn, IO, kompilyator sehri vasitəsilə həyata keçirildiyi halda, demək olar ki, bütün digərləri proqram təminatında həyata keçirilir və onlarda bütün hesablamalar təmizdir.
Çoxlu effektlər var və hər birinin öz monadası var. Bu, çox güclü və gözəl nəzəriyyədir: bütün monadlar eyni interfeysi həyata keçirir. Aşağıdakı üç monad haqqında danışacağıq:
- Ya ea a tipli bir dəyəri qaytaran və ya e tipli bir istisna atan hesablamadır. Bu monadın davranışı imperativ dillərdə istisnaların idarə edilməsinə çox bənzəyir: səhvlər tutula və ya ötürülə bilər. Əsas fərq, monadın Haskelldəki standart kitabxanada tamamilə məntiqi şəkildə həyata keçirilməsidir, imperativ dillər isə adətən əməliyyat sistemi mexanizmlərindən istifadə edir.
- Sa vəziyyəti a tipli dəyəri qaytaran və s tipli dəyişkən vəziyyətə çıxışı olan hesablamadır.
- Bəlkə də a. Bəlkə monad heç bir şeyi qaytarmaqla istənilən vaxt kəsilə bilən hesablamanı ifadə edir. Bununla belə, əks effekti ifadə edən Maybe tipi üçün MonadPlus sinfinin həyata keçirilməsindən danışacağıq: bu, konkret dəyəri qaytarmaqla istənilən vaxt kəsilə bilən hesablamadır.
Alqoritmin həyata keçirilməsi
Bizdə iki məlumat növü var, Qrafik a və Bigraph ab, bunlardan birincisi a tipli dəyərlərlə etiketlənmiş təpələri olan qrafikləri, ikincisi isə a və sağ tipli qiymətlərlə etiketlənmiş sol tərəf təpələri olan ikitərəfli qrafikləri təmsil edir. -b tipli dəyərlərlə işarələnmiş yan təpələr.
Bunlar Alga kitabxanasındakı növlər deyil. Alqanın yönləndirilməmiş ikitərəfli qrafiklər üçün təmsili yoxdur. Aydınlıq üçün bu tipləri etdim.
Aşağıdakı imzaları olan köməkçi funksiyalara da ehtiyacımız olacaq:
-- Список соседей данной вершины.
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)Dərinlikdə ilk axtarış zamanı ziddiyyətli kənar tapsaq, tək dövrənin rekursiya yığınının üstündə olduğunu görmək asandır. Beləliklə, onu bərpa etmək üçün rekursiya yığınından sonuncu təpənin ilk meydana gəlməsinə qədər hər şeyi kəsməliyik.
Biz hər bir təpə üçün assosiativ pay nömrələri silsiləsi saxlamaqla ilk dərinlik axtarışını həyata keçiririk. Rekursiya yığını seçdiyimiz monadın Functor sinfinin həyata keçirilməsi ilə avtomatik olaraq saxlanılacaq: bizə yalnız rekursiv funksiyadan qaytarılan nəticəyə yoldan bütün təpələri yerləşdirmək lazımdır.
Mənim ilk fikrim Either monaddan istifadə etmək idi ki, bu da bizə lazım olan effektləri reallaşdırır. Yazdığım ilk tətbiq bu varianta çox yaxın idi. Əslində, bir anda beş fərqli tətbiqim var idi və nəticədə başqa birinə qərar verdim.
Birincisi, biz pay identifikatorlarının assosiativ massivini saxlamalıyıq - bu, Dövlətə aid bir şeydir. İkincisi, münaqişə aşkarlananda dayanmağı bacarmalıyıq. Bu ya Monad ola bilər, ya da MonadPlus Bəlkə üçün. Əsas fərq ondan ibarətdir ki, Ya hesablama dayandırılmadıqda dəyəri qaytara bilər və Bəlkə də bu halda yalnız bu barədə məlumat qaytarır. Müvəffəqiyyət üçün ayrıca dəyərə ehtiyacımız olmadığı üçün (bu, artıq Dövlətdə saxlanılır), biz Ola bilər seçirik. Və iki monadın təsirlərini birləşdirməyimiz lazım olan anda onlar çıxır , bu təsirləri dəqiq birləşdirən.
Niyə belə mürəkkəb bir növü seçdim? İki səbəb. Birincisi, həyata keçirilməsi imperativə çox bənzəyir. İkincisi, tək döngəni bərpa etmək üçün rekursiyadan geri qayıdarkən konflikt halında qaytarma dəyərini manipulyasiya etməliyik, bunu Maybe monadında etmək daha asandır.
Beləliklə, bu tətbiqi əldə edirik.
{-# 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)
Harada bloku alqoritmin əsasını təşkil edir. Onun daxilində baş verənləri izah etməyə çalışacağam.
- inVertex, təpəyə ilk dəfə baş çəkdiyimiz dərinlik-ilk axtarışın bir hissəsidir. Burada biz təpəyə pay nömrəsi təyin edirik və bütün qonşularda onEdge-i işə salırıq. Bu, həmçinin zəng yığınını bərpa etdiyimiz yerdir: əgər msum dəyəri qaytardısa, v vertexini oraya itələyirik.
- onEdge kənarı ziyarət etdiyimiz hissədir. Hər kənar üçün iki dəfə çağırılır. Burada biz qarşı tərəfdəki təpənin ziyarət edilib-edilmədiyini yoxlayırıq və əgər yoxsa ziyarət edirik. Əgər ziyarət etsəniz, kənarın ziddiyyətli olub olmadığını yoxlayırıq. Əgər belədirsə, biz dəyəri qaytarırıq - rekursiya yığınının ən yuxarı hissəsi, burada bütün digər təpələr qayıtdıqdan sonra yerləşdiriləcəkdir.
- processVertex hər bir təpənin ziyarət edilib-edilmədiyini yoxlayır və əgər yoxsa, onun üzərində inVertex işləyir.
- dfs bütün təpələrdə processVertex-i işə salır.
Vəssalam.
INLINE sözünün tarixi
INLINE sözü alqoritmin ilk tətbiqində deyildi, daha sonra ortaya çıxdı. Daha yaxşı bir tətbiq tapmağa çalışarkən, qeyri-INLINE versiyasının bəzi qrafiklərdə nəzərəçarpacaq dərəcədə yavaş olduğunu gördüm. Semantik olaraq funksiyaların eyni işləməli olduğunu nəzərə alsaq, bu məni çox təəccübləndirdi. Hətta qəribə olsa da, GHC-nin fərqli versiyası olan başqa bir maşında nəzərəçarpacaq fərq yox idi.
GHC Core çıxışını oxumaq üçün bir həftə sərf etdikdən sonra problemi bir sətir açıq INLINE ilə həll edə bildim. GHC 8.4.4 və GHC 8.6.5 arasında bir nöqtədə optimallaşdırıcı bunu öz başına dayandırdı.
Haskell proqramlaşdırmasında belə bir kirlə qarşılaşacağımı gözləmirdim. Bununla belə, bu gün belə, optimallaşdırıcılar bəzən səhvlər edirlər və onlara göstərişlər vermək bizim işimizdir. Məsələn, burada bilirik ki, funksiya imperativ versiyada daxil olduğu üçün daxilə daxil edilməlidir və bu, kompilyatora ipucu vermək üçün səbəbdir.
Sonra nə oldu?
Sonra digər monadlarla birlikdə Hopcroft-Karp alqoritmini tətbiq etdim və bu proqramın sonu oldu.
Google Summer of Code sayəsində mən funksional proqramlaşdırma üzrə praktiki təcrübə qazandım, bu, nəinki növbəti yay Jane Street-də təcrübə keçməyə kömək etdi (bu yerin hətta Habrın məlumatlı auditoriyası arasında nə qədər tanındığından əmin deyiləm, lakin bu, birdir. funksional proqramlaşdırma ilə məşğul ola biləcəyiniz bir neçə yerdən), həm də məni ənənəvi dillərdəki təcrübəmdən əhəmiyyətli dərəcədə fərqlənən bu paradiqmanı praktikada tətbiq etməyin gözəl dünyası ilə tanış etdi.
Mənbə: www.habr.com