Geçen yaz ben de katıldım - Google'dan öğrenciler için bir program. Organizatörler her yıl, aralarında aşağıdaki gibi tanınmış kuruluşların da bulunduğu birçok Açık Kaynak projesi seçmektedir: и . Google, dünyanın her yerinden öğrencileri bu projeler üzerinde çalışmaya davet ediyor.
Google Summer of Code 2019 katılımcısı olarak kütüphane bünyesinde bir proje yaptım organizasyon ile , en ünlü fonksiyonel programlama dillerinden biri olan Haskell dilini geliştiriyor. Alga temsil eden bir kütüphanedir Haskell'deki grafiklerin gösterimi. Örneğin şuralarda kullanılır: — koda dayalı anlamsal ağaçlar, çağrı ve bağımlılık grafikleri oluşturan ve bunları karşılaştırabilen bir Github kütüphanesi. Projem, iki parçalı grafikler için tür açısından güvenli bir gösterim ve bu gösterime yönelik algoritmalar eklemekti.
Bu yazıda Haskell'de bir grafiğin iki taraflılığını kontrol etmek için bir algoritma uygulamamdan bahsedeceğim. Algoritma en temellerden biri olmasına rağmen onu işlevsel bir tarzda güzel bir şekilde uygulamak birkaç yinelemeyi gerektirdi ve oldukça fazla çalışma gerektirdi. Sonuç olarak monad transformatörlü bir uygulamaya karar verdim.
Hakkımda
Adım Vasily Alferov, St. Petersburg HSE'de dördüncü sınıf öğrencisiyim. Daha önce yazdığım blogda и . Şu anda stajyerlik yapıyorum Soruna yönelik yaklaşımlar üzerinde çalıştığım Norveç'te . İlgi alanlarım parametreli algoritmalar ve fonksiyonel programlamayı içermektedir.
Algoritmanın uygulanması hakkında
Önsöz
Programa katılan öğrencilerin blog yazmaları şiddetle teşvik edilmektedir. Bana blog için bir platform sağladılar . Bu makale bir çeviridir , kısa bir önsözle birlikte Temmuz ayında İngilizce olarak tarafımdan yazılmıştır.
Söz konusu kodla Çekme İsteği bulunabilir .
Çalışmamın sonuçlarını okuyabilirsiniz (İngilizce) .
Bu yazı, okuyucuyu fonksiyonel programlamadaki temel kavramlarla tanıştırmayı amaçlamaktadır, ancak zamanı geldiğinde kullanılan tüm terimleri hatırlamaya çalışacağım.
İki taraflılık için grafiklerin kontrol edilmesi
Bir grafiğin iki parçalılığını kontrol etmeye yönelik bir algoritma, genellikle en basit grafik algoritmalarından biri olarak algoritmalar üzerine bir derste verilir. Onun fikri basit: İlk önce bir şekilde sol veya sağ paylaşıma köşeler koyarız ve çelişen bir kenar bulunduğunda grafiğin iki parçalı olmadığını iddia ederiz.
Biraz daha detay: İlk önce soldaki paylaşıma bir miktar köşe noktası koyuyoruz. Açıkçası, bu tepe noktasının tüm komşuları sağ lobda yer almalıdır. Ayrıca, bu tepe noktasının komşularının tüm komşuları sol lobda yer almalıdır, vb. Başladığımız köşenin bağlantılı bileşeninde komşu atamadığımız köşeler olduğu sürece köşelere paylaşım atamaya devam ediyoruz. Daha sonra bu işlemi bağlı tüm bileşenler için tekrarlıyoruz.
Aynı bölüme düşen köşeler arasında bir kenar varsa, grafikte tek parçalı bir döngü bulmak zor değildir; bu, iki parçalı bir grafikte yaygın olarak bilinen (ve oldukça açık bir şekilde) imkansızdır. Aksi takdirde doğru bir bölümümüz olur, bu da grafiğin iki parçalı olduğu anlamına gelir.
Tipik olarak, bu algoritma kullanılarak uygulanır. veya . Zorunlu dillerde, biraz daha basit olduğundan ve ek veri yapıları gerektirmediğinden genellikle derinlik öncelikli arama kullanılır. Ayrıca daha geleneksel olduğu için derinlik öncelikli aramayı da seçtim.
Böylece aşağıdaki şemaya geldik. Grafiğin köşelerini derinlik öncelikli aramayı kullanarak geçiyoruz ve onlara paylaşımlar atayarak, kenar boyunca ilerledikçe paylaşım sayısını değiştiriyoruz. Halihazırda atanmış bir paylaşıma sahip bir köşeye paylaşım atamaya çalışırsak, grafiğin iki parçalı olmadığını rahatlıkla söyleyebiliriz. Tüm köşelere bir pay atandığı ve tüm kenarlara baktığımız anda iyi bir bölüme sahibiz.
Hesaplamaların saflığı
Haskell'de tüm hesaplamaların doğru olduğunu varsayıyoruz. temiz. Ancak durum gerçekten böyle olsaydı ekrana herhangi bir şey yazdırmanın bir yolu olmazdı. Kesinlikle, temiz hesaplamalar o kadar tembel ki bir tane bile yok saf bir şeyi hesaplamak için nedenler. Programda meydana gelen tüm hesaplamalar bir şekilde zorlanmaktadır. "kirli" monad IO.
Monadlar hesaplamaları temsil etmenin bir yoludur Etkileri Haskell'de. Nasıl çalıştıklarını açıklamak bu yazının kapsamı dışındadır. İyi ve net bir açıklama İngilizce olarak okunabilir .
Burada şunu belirtmek isterim ki, IO gibi bazı monadlar derleyici büyüsü aracılığıyla uygulanırken, diğerlerinin neredeyse tamamı yazılımla uygulanır ve içlerindeki tüm hesaplamalar saftır.
Pek çok efekt var ve her birinin kendi monadı var. Bu çok güçlü ve güzel bir teori: tüm monadlar aynı arayüzü uygular. Aşağıdaki üç monaddan bahsedeceğiz:
- ea, a türünde bir değer döndüren veya e türünde bir istisna atan bir hesaplamadır. Bu monadın davranışı zorunlu dillerdeki istisna işlemeye çok benzer: hatalar yakalanabilir veya aktarılabilir. Temel fark, monadın Haskell'deki standart kütüphanede tamamen mantıksal olarak uygulanması, zorunlu dillerin ise genellikle işletim sistemi mekanizmalarını kullanmasıdır.
- Durum sa, a türünde bir değer döndüren ve s türünün değiştirilebilir durumuna erişimi olan bir hesaplamadır.
- Belki bir. Maybe monad'ı, herhangi bir zamanda Hiçbir Şey döndürerek kesintiye uğratılabilecek bir hesaplamayı ifade eder. Ancak MonadPlus sınıfının Maybe türü için uygulanmasından bahsedeceğiz ki bu tam tersi etkiyi ifade eder: belirli bir değer döndürülerek istenildiği zaman kesintiye uğratılabilen bir hesaplamadır.
Algoritmanın uygulanması
İki veri tipimiz var: Graph a ve Bigraph ab; bunlardan ilki, a tipi değerlerle etiketlenmiş köşelere sahip grafikleri temsil eder ve ikincisi, a ve sağ tipi değerlerle etiketlenmiş, sol taraftaki köşelere sahip iki parçalı grafikleri temsil eder. -b tipi değerlerle etiketlenmiş yan köşeler.
Bunlar Alga kütüphanesindeki türler değil. Alga'nın yönlendirilmemiş iki parçalı grafikler için bir temsili yoktur. Netlik sağlamak için bu tür türleri yaptım.
Ayrıca aşağıdaki imzalara sahip yardımcı işlevlere de ihtiyacımız olacak:
-- Список соседей данной вершины.
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)Derinlik öncelikli arama sırasında çelişkili bir kenar bulursak, tek döngünün özyineleme yığınının en üstünde yer aldığını görmek kolaydır. Bu nedenle, onu geri yüklemek için özyineleme yığınından son köşenin ilk oluşumuna kadar her şeyi kesmemiz gerekir.
Her köşe için ilişkisel bir paylaşım numarası dizisini koruyarak derinlik öncelikli aramayı uyguluyoruz. Özyineleme yığını, seçtiğimiz monadın Functor sınıfının uygulanması yoluyla otomatik olarak korunacaktır: yalnızca yoldaki tüm köşeleri özyinelemeli işlevden döndürülen sonuca yerleştirmemiz gerekecektir.
İlk fikrim, tam olarak ihtiyacımız olan efektleri uygulayan Ya monadını kullanmaktı. İlk yazdığım uygulama bu seçeneğe çok yakındı. Aslında bir noktada beş farklı uygulama yaptım ve sonunda diğerine karar verdim.
İlk olarak, paylaşım tanımlayıcılarının ilişkisel bir dizisini korumamız gerekiyor - bu Durumla ilgili bir şeydir. İkinci olarak bir çatışma tespit edildiğinde durabilmemiz gerekiyor. Bu, Her İkisi için Monad veya Belki için MonadPlus olabilir. Temel fark, hesaplama durdurulmamışsa, İkisinin bir değer döndürebilmesi ve bu durumda Maybe'nin yalnızca bununla ilgili bilgileri döndürmesidir. Başarı için ayrı bir değere ihtiyacımız olmadığından (zaten State'te kayıtlıdır), Maybe'yi seçiyoruz. Ve iki monadın etkilerini birleştirmemiz gerektiğinde ortaya çıkıyorlar Bu etkileri tam olarak birleştiren.
Neden bu kadar karmaşık bir türü seçtim? İki sebep. İlk olarak, uygulamanın zorunlulukla çok benzer olduğu ortaya çıkıyor. İkinci olarak, tek döngüyü geri yüklemek için özyinelemeden geri dönerken çakışma durumunda dönüş değerini değiştirmemiz gerekir ki bunu Maybe monadında yapmak çok daha kolaydır.
Böylece bu uygulamayı elde ediyoruz.
{-# 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)
Where bloğu algoritmanın temelidir. İçinde neler olduğunu anlatmaya çalışacağım.
- inVertex, tepe noktasını ilk kez ziyaret ettiğimiz derinlik öncelikli aramanın parçasıdır. Burada köşeye bir paylaşım numarası atayıp onEdge'i tüm komşularda çalıştırıyoruz. Burası aynı zamanda çağrı yığınını da geri yüklediğimiz yerdir: eğer msum bir değer döndürdüyse, v tepe noktasını oraya iteriz.
- onEdge, edge'i ziyaret ettiğimiz kısımdır. Her kenar için iki kez çağrılır. Burada karşı taraftaki köşenin ziyaret edilip edilmediğini kontrol ediyoruz, ziyaret edilmemişse ziyaret ediyoruz. Ziyaret edilirse kenarın çakışıp çakışmadığını kontrol ederiz. Eğer öyleyse, değeri döndürürüz - özyineleme yığınının en tepesi, geri dönüşte diğer tüm köşelerin yerleştirileceği yer.
- ProcessVertex, her köşenin ziyaret edilip edilmediğini kontrol eder ve ziyaret edilmemişse inVertex'i çalıştırır.
- dfs, ProcessVertex'i tüm köşelerde çalıştırır.
Hepsi bu.
INLINE kelimesinin tarihi
INLINE kelimesi algoritmanın ilk uygulamasında yoktu; daha sonra ortaya çıktı. Daha iyi bir uygulama bulmaya çalıştığımda INLINE olmayan sürümün bazı grafiklerde belirgin şekilde daha yavaş olduğunu buldum. Anlamsal olarak işlevlerin aynı şekilde çalışması gerektiğini düşünürsek bu beni çok şaşırttı. Daha da tuhafı, farklı bir GHC sürümüne sahip başka bir makinede gözle görülür bir fark yoktu.
Bir haftayı GHC Core çıktısını okuyarak geçirdikten sonra, sorunu bir satır açık INLINE ile çözmeyi başardım. GHC 8.4.4 ile GHC 8.6.5 arasındaki bir noktada optimizer bunu kendi başına yapmayı bıraktı.
Haskell programlamasında bu kadar pislikle karşılaşmayı beklemiyordum. Ancak bugün bile optimize ediciler bazen hata yapabiliyor ve onlara ipuçları vermek bizim görevimiz. Örneğin, burada fonksiyonun satır içi olması gerektiğini biliyoruz çünkü emir kipinde satır içidir ve bu, derleyiciye bir ipucu vermek için bir nedendir.
Sonra ne oldu?
Daha sonra Hopcroft-Karp algoritmasını diğer monadlarla uyguladım ve bu programın sonu oldu.
Google Summer of Code sayesinde fonksiyonel programlama konusunda pratik deneyim kazandım ve bu sadece bir sonraki yaz Jane Street'te staj yapmamı sağlamakla kalmadı (buranın Habr'ın bilgili kitlesi arasında bile ne kadar iyi tanındığından emin değilim ama burası işlevsel programlamaya katılabileceğiniz az sayıdaki yerden) ama aynı zamanda beni, geleneksel dillerdeki deneyimimden önemli ölçüde farklı olan bu paradigmayı pratikte uygulamanın harika dünyasıyla tanıştırdı.
Kaynak: habr.com