Өнгөрсөн зун би оролцсон - Google-ийн оюутнуудад зориулсан програм. Зохион байгуулагчид жил бүр хэд хэдэн Нээлттэй эхийн төслийг сонгон шалгаруулж, тэр дундаа алдартай байгууллагуудаас шалгаруулдаг и . Google нь дэлхийн өнцөг булан бүрээс оюутнуудыг эдгээр төсөл дээр ажиллахыг урьж байна.
Google Summer of Code 2019-д оролцогчийн хувьд би номын санд төсөл хэрэгжүүлсэн байгууллагатай хамт , Хаскелл хэлийг хөгжүүлж байгаа нь хамгийн алдартай функциональ програмчлалын хэлнүүдийн нэг юм. Алга бол төлөөлж буй номын сан юм Хаскелл дахь графикуудын дүрслэл. Энэ нь жишээлбэл, онд хэрэглэгддэг — код дээр үндэслэн семантик мод, дуудлага, хамаарлын графикийг бүтээдэг, тэдгээрийг харьцуулах боломжтой Github номын сан. Миний төсөл бол хоёр талт графикууд болон тэдгээр дүрслэлд зориулсан алгоритмуудын төрлийн аюулгүй дүрслэлийг нэмэх явдал байв.
Энэ нийтлэлд би Хаскелл дахь хоёр талт байдлын графикийг шалгах алгоритмын хэрэгжилтийн талаар ярих болно. Хэдийгээр алгоритм нь хамгийн энгийн алгоритмуудын нэг боловч үүнийг функциональ хэв маягаар сайхан хэрэгжүүлэх нь надад хэд хэдэн давталт авч, маш их хөдөлмөр шаарддаг. Үүний үр дүнд би монад трансформатортай хэрэгжүүлэхээр шийдсэн.
Миний тухай
Намайг Василий Алферов гэдэг, би Санкт-Петербургийн ХАБЭА-н дөрөвдүгээр дамжааны оюутан. Би өмнө нь блогтоо бичсэн и . Яг одоо би дадлага хийж байна Норвегид би асуудалд хандах арга барил дээр ажиллаж байна . Миний сонирхол бол параметржүүлсэн алгоритм, функциональ програмчлал юм.
Алгоритмыг хэрэгжүүлэх тухай
Өмнөх үг
Хөтөлбөрт хамрагдаж буй оюутнуудыг блог хөтлөхийг маш их уриалж байна. Тэд надад блог хийх платформоор хангасан . Энэ нийтлэл нь орчуулга юм , XNUMX-р сард тэнд миний бичсэн англи хэл дээр, товч оршилтой.
Асууж буй код бүхий татах хүсэлтийг олж болно .
Та миний ажлын үр дүнгийн талаар уншиж болно (англи хэл дээр) .
Энэ нийтлэл нь уншигчдад функциональ програмчлалын үндсэн ойлголтуудтай танилцах зорилготой боловч би цаг нь ирэхэд ашигласан бүх нэр томъёог эргэн санахыг хичээх болно.
Графикуудыг хоёр талт байдлыг шалгаж байна
Графикийн хоёр талт байдлыг шалгах алгоритмыг ихэвчлэн алгоритмын курст хамгийн энгийн график алгоритмуудын нэг болгон өгдөг. Түүний санаа нь маш энгийн: эхлээд бид зүүн эсвэл баруун хэсэгт оройнуудыг байрлуулж, зөрчилдөх ирмэг олдвол график нь хоёр талт биш гэдгийг баталж байна.
Бага зэрэг дэлгэрэнгүй: эхлээд бид зүүн хэсэгт зарим оройг байрлуулна. Мэдээжийн хэрэг, энэ оройн бүх хөршүүд баруун дэлбээнд хэвтэж байх ёстой. Цаашилбал, энэ оройн хөршүүдийн бүх хөршүүд зүүн дэлбээнд хэвтэж байх ёстой гэх мэт. Бидний эхлүүлсэн оройн холболтын бүрэлдэхүүн хэсэгт хөршүүдээ оноогоогүй оройнууд байсаар л байвал бид оройнуудад хувьцаа оноож байна. Дараа нь бид бүх холбогдсон бүрэлдэхүүн хэсгүүдийн хувьд энэ үйлдлийг давтана.
Хэрэв нэг хуваалтад орох оройнуудын хооронд ирмэг байгаа бол графикаас сондгой мөчлөгийг олоход хэцүү биш бөгөөд энэ нь хоёр талт графикт өргөн тархсан (мөн маш ойлгомжтой) боломжгүй юм. Үгүй бол бид зөв хуваалттай байгаа бөгөөд энэ нь график хоёр талт гэсэн үг юм.
Ихэвчлэн энэ алгоритмыг ашиглан хэрэгжүүлдэг буюу . Зайлшгүй шаардлагатай хэлүүдэд гүнээс эхлээд хайлтыг ихэвчлэн ашигладаг, учир нь энэ нь арай хялбар бөгөөд нэмэлт өгөгдлийн бүтэц шаарддаггүй. Би мөн илүү уламжлалт тул гүнзгийрүүлсэн хайлтыг сонгосон.
Тиймээс бид дараах схемд ирлээ. Бид графикийн оройг гүнзгийрүүлсэн хайлтыг ашиглан гаталж, тэдгээрт хувьцаа оноож, ирмэгийн дагуу шилжихдээ хувьцааны тоог өөрчилдөг. Хэрэв бид хувьцааг аль хэдийн хуваарилсан орой руу хуваарилахыг оролдвол график нь хоёр талт биш гэдгийг баттай хэлж чадна. Бүх оройгуудад хувьцаа оноож, бүх ирмэгийг нь харвал бидэнд сайн хуваалт байна.
Тооцооллын цэвэр байдал
Haskell-д бид бүх тооцоолол хийгдсэн гэж үздэг цэвэрхэн. Гэсэн хэдий ч хэрэв энэ нь үнэхээр байсан бол бид дэлгэцэн дээр юу ч хэвлэх боломжгүй байх байсан. Бүх, цэвэр Тооцоолол маш залхуу тул нэг ч байхгүй цэвэрхэн ямар нэг зүйлийг тооцоолох шалтгаан. Хөтөлбөрт гарч буй бүх тооцоог ямар нэгэн байдлаар албадан хийдэг "цэвэр бус" monad IO.
Монадууд нь тооцооллыг илэрхийлэх арга юм нөлөө Хаскеллд. Тэдний хэрхэн ажилладаг талаар тайлбарлах нь энэ нийтлэлийн хамрах хүрээнээс гадуур юм. Сайн бөгөөд ойлгомжтой тайлбарыг англи хэл дээр уншиж болно .
IO гэх мэт зарим монадыг хөрвүүлэгчийн ид шидээр хэрэгжүүлдэг бол бусад нь бараг бүх программ хангамжид хэрэгждэг бөгөөд тэдгээрийн доторх бүх тооцоо нь цэвэр гэдгийг энд онцлон тэмдэглэхийг хүсч байна.
Маш олон эффектүүд байдаг бөгөөд тус бүр өөрийн гэсэн монадтай. Энэ бол маш хүчтэй, үзэсгэлэнтэй онол юм: бүх монадууд ижил интерфейсийг хэрэгжүүлдэг. Бид дараах гурван монадын тухай ярих болно.
- ea-ийн аль нэг нь a төрлийн утгыг буцаадаг эсвэл e төрлийн үл хамаарах зүйлийг гаргадаг тооцоолол юм. Энэ монадын зан байдал нь зайлшгүй хэл дээрх онцгой тохиолдлуудыг зохицуулахтай маш төстэй: алдааг барьж эсвэл дамжуулж болно. Гол ялгаа нь монад нь Хаскелл дахь стандарт номын санд бүрэн логикоор хэрэгжсэн байдаг бол зайлшгүй хэлүүд нь ихэвчлэн үйлдлийн системийн механизмуудыг ашигладаг.
- Төлөв sa нь a төрлийн утгыг буцаадаг тооцоолол бөгөөд s төрлийн хувирах төлөвт хандах боломжтой.
- Магадгүй а. Магадгүй монад нь Nothing гэж буцаах замаар ямар ч үед тасалдаж болох тооцооллыг илэрхийлдэг. Гэсэн хэдий ч, бид магадгүй төрлийн MonadPlus ангиллын хэрэгжилтийн талаар ярих болно, энэ нь эсрэг нөлөөг илэрхийлдэг: энэ нь тодорхой утгыг буцаах замаар ямар ч үед тасалдаж болох тооцоо юм.
Алгоритмыг хэрэгжүүлэх
Бидэнд График a ба Bigraph ab гэсэн хоёр төрлийн өгөгдлийн төрөл байгаа бөгөөд эхнийх нь a төрлийн утгуудаар тэмдэглэгдсэн оройтой графикуудыг, хоёр дахь нь a ба баруун талын утгуудаар тэмдэглэгдсэн зүүн талын оройтой хоёр талт графикуудыг төлөөлдөг. - b төрлийн утгуудаар тэмдэглэгдсэн хажуугийн оройнууд.
Эдгээр нь Алга номын сангийн төрөл биш юм. Алгад чиглүүлээгүй хоёр талт графикуудын төлөөлөл байхгүй. Би тодорхой болгохын тулд иймэрхүү төрлүүдийг хийсэн.
Мөн бидэнд дараах гарын үсэг бүхий туслах функцүүд хэрэгтэй болно.
-- Список соседей данной вершины.
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)Хэрэв гүн гүнзгий хайлт хийх явцад бид зөрчилтэй ирмэгийг олсон бол сондгой мөчлөг нь рекурсын стекийн дээд талд байрладаг болохыг харахад хялбар байдаг. Тиймээс үүнийг сэргээхийн тулд бид рекурсын стекээс эхлээд сүүлчийн оройн анхны тохиолдол хүртэлх бүх зүйлийг таслах хэрэгтэй.
Бид орой тус бүрийн хувьцааны дугаарын ассоциатив массивыг хадгалах замаар эхлээд гүнзгийрүүлсэн хайлтыг хэрэгжүүлдэг. Бидний сонгосон монадын Functor классыг хэрэгжүүлснээр рекурсын стек автоматаар хадгалагдах болно: бид зөвхөн рекурсив функцээс буцаж ирсэн үр дүнд зам дээрх бүх оройг оруулахад л хангалттай.
Миний анхны санаа бол "Either monad"-ыг ашиглах явдал байсан бөгөөд энэ нь яг бидэнд хэрэгтэй эффектүүдийг хэрэгжүүлдэг бололтой. Миний бичсэн анхны хэрэгжүүлэлт энэ сонголттой маш ойрхон байсан. Үнэн хэрэгтээ би нэг удаад таван өөр хэрэгжилттэй байсан бөгөөд эцэст нь өөр нэгийг нь шийдсэн.
Нэгдүгээрт, бид хувьцаа таниулагчдын ассоциатив массивыг хадгалах хэрэгтэй - энэ бол Төрийн тухай зүйл юм. Хоёрдугаарт, зөрчил илэрсэн үед зогсоож чаддаг байх хэрэгтэй. Энэ нь аль нэг нь Monad эсвэл магадгүй MonadPlus байж болно. Гол ялгаа нь аль нэг нь тооцооллыг зогсоогүй тохиолдолд утгыг буцаах боломжтой бөгөөд магадгүй энэ тохиолдолд зөвхөн энэ тухай мэдээллийг буцаана. Амжилтанд хүрэхийн тулд тусдаа үнэ цэнэ хэрэггүй (энэ нь аль хэдийн мужид хадгалагдсан) учраас бид магадгүй-г сонгоно. Мөн хоёр монадын нөлөөг хослуулах шаардлагатай үед тэд гарч ирдэг , эдгээр нөлөөг нарийн хослуулсан.
Би яагаад ийм нарийн төвөгтэй төрлийг сонгосон юм бэ? Хоёр шалтгаан. Нэгдүгээрт, хэрэгжилт нь зайлшгүй шаардлагатай төстэй юм. Хоёрдугаарт, сондгой гогцоог сэргээхийн тулд рекурсаас буцаж ирэхэд зөрчил гарсан тохиолдолд буцах утгыг өөрчлөх шаардлагатай бөгөөд энэ нь магадгүй монад хийхэд илүү хялбар байдаг.
Тиймээс бид энэ хэрэгжилтийг олж авдаг.
{-# 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)
хаана блок нь алгоритмын цөм юм. Би түүний дотор юу болж байгааг тайлбарлахыг хичээх болно.
- inVertex нь бид анх удаа орой руугаа зочилж буй гүнээс эхлээд хайлтын хэсэг юм. Энд бид орой руу хуваалцах дугаар оноож, бүх хөршүүд дээр onEdge-ийг ажиллуулдаг. Энэ нь мөн дуудлагын стекийг сэргээх газар юм: хэрэв msum утга буцаавал бид v оройг тэнд дарна.
- onEdge бол бидний ирмэг дээр очдог хэсэг юм. Энэ нь ирмэг бүрийн хувьд хоёр удаа дуудагддаг. Энд бид нөгөө талын орой дээр очсон эсэхийг шалгаж, үгүй бол зочилно. Хэрэв зочилсон бол бид ирмэг нь зөрчилдөж байгаа эсэхийг шалгана. Хэрэв тийм бол бид утгыг буцаана - рекурсын стекийн хамгийн дээд хэсэгт буцаж ирэхэд бусад бүх оройнууд тавигдах болно.
- processVertex нь орой бүрийг зочилсон эсэхийг шалгадаг бөгөөд хэрэв үгүй бол inVertex-ийг ажиллуулдаг.
- dfs нь processVertex-ийг бүх орой дээр ажиллуулдаг.
Тэгээд л болоо.
INLINE гэдэг үгийн түүх
INLINE гэдэг үг нь алгоритмын анхны хэрэгжилтэд байгаагүй, дараа нь гарч ирсэн. Би илүү сайн хэрэгжилтийг хайж байхдаа INLINE бус хувилбар нь зарим график дээр мэдэгдэхүйц удаашралтай байгааг олж мэдсэн. Утга зүйн хувьд функцууд нь адилхан ажиллах ёстой гэж үзвэл энэ нь намайг их гайхшруулсан. Гадных нь хувьд GHC-ийн өөр хувилбартай өөр машин дээр мэдэгдэхүйц ялгаа байсангүй.
GHC Core-ийн гаралтыг уншаад долоо хоног зарцуулсны дараа би нэг мөр INLINE-ийн тусламжтайгаар асуудлыг шийдэж чадсан. GHC 8.4.4 болон GHC 8.6.5-ын хооронд зарим үед оновчтой болгогч өөрөө үүнийг хийхээ больсон.
Би Хаскелл програмчлалд ийм бохирдолтой тулгарна гэж бодоогүй. Гэсэн хэдий ч өнөөдрийг хүртэл оновчтой болгогчид заримдаа алдаа гаргадаг бөгөөд тэдэнд зөвлөгөө өгөх нь бидний үүрэг юм. Жишээлбэл, энд функц нь императив хувилбарт доторлогддог тул доторлогоотой байх ёстой гэдгийг бид мэдэж байгаа бөгөөд энэ нь хөрвүүлэгчид зөвлөгөө өгөх шалтгаан юм.
Дараа нь юу болсон бэ?
Дараа нь би Hopcroft-Karp алгоритмыг бусад монадын хамт хэрэгжүүлсэн бөгөөд энэ нь програмын төгсгөл болсон.
Google Summer of Code-ийн ачаар би функциональ програмчлалын практик туршлага хуримтлуулсан бөгөөд энэ нь дараа зун Жэйн Стрийтэд дадлага хийхэд надад тусалсан төдийгүй (Энэ газар Хабрын мэдлэгтэй үзэгчдийн дунд хэр алдартай болохыг би сайн мэдэхгүй байна, гэхдээ энэ нь нэг юм. Зуны улиралд функциональ програмчлалд хамрагдах боломжтой цөөхөн хэдэн газруудын нэг) мөн энэ парадигмыг практикт хэрэгжүүлэх гайхалтай ертөнцийг надад танилцуулсан нь уламжлалт хэл дээрх туршлагаасаа эрс ялгаатай.
Эх сурвалж: www.habr.com