Өткөн жайда мен катыштым - Google'дун студенттери үчүн программа. Жыл сайын уюштуруучулар бир нече Open Source долбоорлорун, анын ичинде белгилүү уюмдардан тандап алышат и . Google дүйнө жүзүндөгү студенттерди бул долбоорлордун үстүндө иштөөгө чакырат.
Google Summer of Code 2019 программасынын катышуучусу катары мен китепкананын ичинде долбоор жасадым уюм менен , Хаскелл тилин иштеп чыгууда - эң белгилүү функционалдык программалоо тилдеринин бири. «Алга» деген китепкана болуп саналат Хаскеллде графиктер үчүн өкүлчүлүк. Ал, мисалы, колдонулат — коддун негизинде семантикалык дарактарды, чакыруу жана көз карандылык графиктерин курган жана аларды салыштыра алган Github китепканасы. Менин долбоорум эки тараптуу графиктер жана ал өкүлчүлүк үчүн алгоритмдер үчүн типтүү коопсуз өкүлчүлүктү кошуу болчу.
Бул постто мен Хаскеллде эки тараптуулуктун графигин текшерүү үчүн алгоритмди ишке ашыруум жөнүндө сүйлөшөм. Алгоритм эң негизгилеринин бири болгонуна карабастан, аны функционалдык стилде кооз ишке ашыруу мен үчүн бир нече итерацияны талап кылды жана абдан көп эмгекти талап кылды. Натыйжада, мен монаддык трансформаторлор менен ишке ашырууну чечтим.
Өзү жөнүндө
Менин атым Василий Алферов, мен Санкт-Петербургдагы HSE 4-курсунун студентимин. Буга чейин блогдо жазган элем и . Мен азыр стажировкадамын Норвегияда, мен проблемага мамиле кылуунун үстүндө иштеп жатам . Менин кызыгууларым параметрленген алгоритмдерди жана функционалдык программалоону камтыйт.
Алгоритмдин ишке ашырылышы жөнүндө
сөздөр
Программага катышкан студенттерге блог жазуу сунушталат. Алар мага блог үчүн аянтча менен камсыз кылышты . Бул макала котормо болуп саналат , Мен ал жерде июль айында англис тилинде жазган, кыска кириш сөз менен.
Каралып жаткан код менен Тартуу өтүнүчүн табууга болот .
Менин ишимдин жыйынтыгы тууралуу окуй аласыз (англис тилинде) .
Бул пост окурманды функционалдык программалоодогу негизги түшүнүктөр менен тааныштыруу үчүн арналган, бирок мен убагы келгенде колдонулган бардык терминдерди эстеп калууга аракет кылам.
Графиктердин эки тараптуулугун текшерүү
Графиктин эки тараптуулугун текшерүү алгоритми, адатта, эң жөнөкөй график алгоритмдеринин бири катары алгоритмдер боюнча курста берилет. Анын идеясы жөнөкөй: адегенде сол же оң үлүшкө чокуларды коебуз, ал эми карама-каршы чети табылганда, график эки тараптуу эмес деп ырастайбыз.
Бир аз көбүрөөк маалымат: адегенде сол бөлүккө бир топ чокуларды салабыз. Албетте, бул чокусунун бардык кошуналары оң бөлүктө жатышы керек. Андан ары, бул чокусу кошуналардын бардык кошуналары сол лобунда жатышы керек, ж.б.у.с. Биз баштаган чокусунун туташкан компонентинде кошуналарды дайындабаган чокулар дагы эле бар болсо, биз чокуларга үлүштөрдү дайындоону уланта беребиз. Андан кийин бул аракетти бардык туташкан компоненттер үчүн кайталайбыз.
Эгерде бир эле бөлүккө кирген чокулардын ортосунда чек бар болсо, анда эки тараптуу графикте кеңири белгилүү болгон (жана айкын) графта так циклди табуу кыйын эмес. Болбосо, бизде туура бөлүм бар, бул график эки тараптуу дегенди билдирет.
Эреже катары, бул алгоритм колдонуу менен ишке ашырылат же . Императивдик тилдерде, адатта, тереңдиктен биринчи издөө колдонулат, анткени ал бир аз жөнөкөй жана кошумча маалымат структураларын талап кылбайт. Мен дагы салттуураак болгондуктан, биринчи издөөнү тандадым.
Ошентип, биз төмөнкү схемага келдик. Биз графиктин чокуларын тереңдик боюнча биринчи издөөнү колдонуп, аларга үлүштөрдү дайындайбыз, четинен жылган сайын үлүштүн санын өзгөртөбүз. Эгерде биз үлүшү ыйгарылган чокуга үлүшүн дайындоого аракет кылсак, график эки тараптуу эмес деп ишенимдүү айта алабыз. Бардык чокуларга үлүш берилген учурда жана биз бардык четтерин карап чыкканда, бизде жакшы бөлүм бар.
Эсептөөлөрдүн тазалыгы
Хаскеллде биз бардык эсептөөлөр деп ойлойбуз таза. Бирок, эгер чындап эле ушундай болсо, экранга эч нерсе басып чыгарууга эч кандай жолубуз жок болмок. Таптакыр, таза Эсептөөлөр ушунчалык жалкоо болгондуктан, бирөө да жок таза бир нерсени эсептөө үчүн себептер. Программада болгон бардык эсептөөлөр кандайдыр бир жол менен мажбурланат "таза эмес" monad IO.
Монадалар эсептөөлөрдү көрсөтүүнүн бир жолу эффекттер Хаскеллде. Алардын кантип иштээрин түшүндүрүү бул посттун алкагына кирбейт. Жакшы жана так сүрөттөлүшү англис тилинде окуса болот .
Бул жерде мен белгилеп кетким келет, кээ бир монадалар, мисалы IO, компилятордук сыйкыр аркылуу ишке ашырылса, дээрлик бардык башкалары программалык камсыздоодо ишке ашырылат жана алардагы бардык эсептөөлөр таза.
Эффекттер көп жана ар биринин өзүнүн монадасы бар. Бул абдан күчтүү жана кооз теория: бардык монадалар бирдей интерфейсти ишке ашырышат. Биз төмөнкү үч монада жөнүндө сүйлөшөбүз:
- Же ea - бул а түрүндөгү маанини кайтарган же e түрүндөгү өзгөчөлүктү таштаган эсептөө. Бул монаддын жүрүм-туруму императивдик тилдердеги өзгөчөлүктү иштетүүгө абдан окшош: каталар кармалып же өтүп кетиши мүмкүн. Негизги айырмасы, монад Хаскеллдеги стандарттуу китепканада толугу менен логикалык түрдө ишке ашырылган, ал эми императивдик тилдер, адатта, операциялык системанын механизмдерин колдонушат.
- Са абалы - а түрүнүн маанисин кайтарган жана s түрүнүн өзгөрүлмө абалына мүмкүнчүлүк алган эсептөө.
- Балким, а. Мүмкүн монада Эч нерсе кайтаруу менен каалаган убакта үзгүлтүккө учура турган эсептөөнү билдирет. Бирок, биз MonadPlus классын мүмкүн түрү үчүн ишке ашыруу жөнүндө сүйлөшөбүз, ал карама-каршы эффектти билдирет: бул белгилүү бир маанини кайтаруу менен каалаган убакта үзгүлтүккө учура турган эсептөө.
Алгоритмдин ишке ашырылышы
Бизде эки маалымат түрү бар, Graph a жана Bigraph ab, алардын биринчиси а түрүнүн маанилери менен белгиленген чокулары бар графиктерди, ал эми экинчиси а жана оң тибинин маанилери менен белгиленген сол жак чокулары бар эки тараптуу графиктерди билдирет. - б түрүндөгү маанилер менен белгиленген каптал чокулары.
Бул «Алга» китепканасынан алынган турлер эмес. Алгада эки жактуу багытталбаган графиктер үчүн өкүлчүлүк жок. Түшүнүктүү болуш үчүн ушул сыяктуу түрлөрүн жасадым.
Бизге төмөнкү кол тамгалар менен жардамчы функциялар да керек болот:
-- Список соседей данной вершины.
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 классын ишке ашыруу аркылуу автоматтык түрдө сакталат: биз рекурсивдүү функциядан кайтарылган натыйжага жолдун бардык чокуларын гана коюшубуз керек.
Менин биринчи идеям же монадды колдонуу болду, ал бизге керектүү эффекттерди ишке ашырат. Мен жазган биринчи ишке ашыруу бул вариантка абдан жакын болгон. Чынында, мен бир учурда беш түрдүү ишке ашырууга ээ болуп, акыры башкасына чечтим.
Биринчиден, биз үлүш идентификаторлорунун ассоциативдик массивине ээ болушубуз керек - бул мамлекет жөнүндө. Экинчиден, чыр-чатак аныкталганда токтото алышыбыз керек. Бул же Monad же мүмкүн үчүн MonadPlus болушу мүмкүн. Негизги айырмачылык, эгерде эсептөө токтотула элек болсо, Ei бир маанини кайтара алат жана Мүмкүн бул учурда бул тууралуу маалыматты гана кайтарат. Бизге ийгилик үчүн өзүнчө маани керек болбогондуктан (ал штатта сакталган), биз Мүмкүн дегенди тандайбыз. Ал эми эки монаданын эффекттерин айкалыштыруу керек болгон учурда алар чыгат , бул эффекттерди так айкалыштырган.
Эмне үчүн мен мындай татаал типти тандадым? Эки себеп. Биринчиден, ишке ашыруу императивге абдан окшош болуп чыгат. Экинчиден, так циклди калыбына келтирүү үчүн рекурсиядан кайтып келгенде, конфликт болгон учурда кайтаруу маанисин манипуляциялашыбыз керек, муну мүмкүн монадасында жасоо оңой.
Ошентип, биз бул ишке ээ.
{-# 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 программасынын аркасында мен функционалдык программалоо боюнча практикалык тажрыйбага ээ болдум, бул мага кийинки жайда Джейн Стритте стажировкадан өтүүгө гана жардам бербестен (бул жер Хабрдын билимдүү аудиториясынын арасында канчалык белгилүү экенин билбейм, бирок бул жайкы функционалдык программалоо менен алектене ала турган бир нече жерден), бирок ошол эле учурда мени салттуу тилдердеги тажрыйбамдан бир топ айырмаланып, бул парадигманы практикада колдонуунун керемет дүйнөсү менен тааныштырды.
Source: www.habr.com