Անցյալ ամառ մասնակցել էի - ծրագիր ուսանողների համար Google-ից: Ամեն տարի կազմակերպիչներն ընտրում են բաց կոդով մի քանի նախագծեր, այդ թվում՝ այնպիսի հայտնի կազմակերպություններից, ինչպիսիք են и . Google-ը հրավիրում է ուսանողներին ամբողջ աշխարհից աշխատելու այս նախագծերի վրա:
Որպես Google Summer of Code 2019-ի մասնակից, ես նախագիծ արեցի գրադարանի ներսում կազմակերպության հետ , որը զարգացնում է Haskell լեզուն՝ ամենահայտնի ֆունկցիոնալ ծրագրավորման լեզուներից մեկը։ Alga-ն գրադարան է, որը ներկայացնում է Հասքելում գրաֆիկների ներկայացում: Այն օգտագործվում է, օրինակ, ք — Github գրադարան, որը կառուցում է իմաստային ծառեր, զանգերի և կախվածության գրաֆիկներ՝ հիմնված կոդի վրա և կարող է համեմատել դրանք: Իմ նախագիծն էր՝ ավելացնել տիպի անվտանգ ներկայացում երկակողմ գրաֆիկների և ալգորիթմների համար այդ ներկայացման համար:
Այս գրառման մեջ ես կխոսեմ Haskell-ում երկակողմանիության գրաֆիկը ստուգելու ալգորիթմի իմ ներդրման մասին: Չնայած ալգորիթմը ամենահիմնականներից մեկն է, այն ֆունկցիոնալ ոճով գեղեցիկ իրականացնելը ինձ մի քանի կրկնություններ պահանջեց և բավականին մեծ աշխատանք պահանջեց: Արդյունքում ես կարգավորեցի մոնադային տրանսֆորմատորներով իրականացումը:
About Me
Ես Վասիլի Ալֆերովն եմ, Սանկտ Պետերբուրգի HSE-ի չորրորդ կուրսի ուսանող եմ։ Ավելի վաղ բլոգում գրել էի и . Հենց հիմա ես պրակտիկա եմ անցնում Նորվեգիայում, որտեղ աշխատում եմ խնդրի շուրջ մոտեցումների վրա . Իմ հետաքրքրությունները ներառում են պարամետրացված ալգորիթմներ և ֆունկցիոնալ ծրագրավորում:
Ալգորիթմի իրականացման մասին
Նախաբան
Ծրագրին մասնակցող ուսանողներին խստորեն խրախուսվում է բլոգում: Նրանք ինձ հարթակ տրամադրեցին բլոգի համար . Այս հոդվածը թարգմանված է , գրված իմ կողմից այնտեղ հուլիսին անգլերենով, կարճ նախաբանով։
Քաշեք հարցումը տվյալ կոդով կարելի է գտնել .
Դուք կարող եք կարդալ իմ աշխատանքի արդյունքների մասին (անգլերեն) .
Այս գրառումը ենթադրում է, որ ընթերցողը ծանոթ է ֆունկցիոնալ ծրագրավորման հիմնական հասկացություններին, թեև ես կփորձեմ հիշել բոլոր օգտագործված տերմինները, երբ ժամանակը գա:
Գրաֆիկների ստուգում երկկողմանիության համար
Գրաֆիկի երկկողմանիության ստուգման ալգորիթմը սովորաբար տրվում է ալգորիթմների դասընթացում որպես ամենապարզ գրաֆիկական ալգորիթմներից մեկը: Նրա գաղափարը պարզ է. նախ մենք ինչ-որ կերպ գագաթներ ենք դնում ձախ կամ աջ բաժնետոմսում, և երբ հայտնաբերվում է հակասական եզր, մենք պնդում ենք, որ գրաֆիկը երկկողմանի չէ:
Մի փոքր ավելի մանրամասն. սկզբում մենք դնում ենք մի գագաթ ձախ մասում: Ակնհայտ է, որ այս գագաթի բոլոր հարեւանները պետք է պառկեն աջ բլթի մեջ: Ավելին, այս գագաթի հարևանների բոլոր հարևանները պետք է պառկեն ձախ բլթի մեջ և այլն: Մենք շարունակում ենք բաժնետոմսեր վերագրել գագաթներին այնքան ժամանակ, քանի դեռ մեր սկսած գագաթի միացված բաղադրիչում կան գագաթներ, որոնց հարևաններ չենք հատկացրել: Այնուհետև մենք կրկնում ենք այս գործողությունը բոլոր միացված բաղադրիչների համար:
Եթե գագաթների միջև կա եզր, որոնք ընկնում են նույն բաժանման մեջ, դժվար չէ գրաֆիկում գտնել տարօրինակ ցիկլ, որը լայնորեն հայտնի է (և միանգամայն ակնհայտորեն) անհնար է երկմասնության գրաֆիկում: Հակառակ դեպքում, մենք ունենք ճիշտ բաժանում, ինչը նշանակում է, որ գրաֆիկը երկկողմանի է:
Որպես կանոն, այս ալգորիթմն իրականացվում է օգտագործելով կամ . Հրամայական լեզուներում սովորաբար օգտագործվում է խորքային որոնումը, քանի որ այն մի փոքր ավելի պարզ է և չի պահանջում լրացուցիչ տվյալների կառուցվածքներ: Ես նաև ընտրեցի խորքային որոնումը, քանի որ այն ավելի ավանդական է:
Այսպիսով, մենք եկանք հետևյալ սխեմային. Մենք անցնում ենք գրաֆիկի գագաթները՝ օգտագործելով խորքային որոնումը և նրանց հատկացնում ենք բաժնետոմսեր՝ փոխելով բաժնետոմսի թիվը, երբ շարժվում ենք եզրով: Եթե փորձենք մասնաբաժինը վերագրել այն գագաթին, որն արդեն ունի հատկացված մասնաբաժին, ապա կարող ենք վստահորեն ասել, որ գրաֆիկը երկկողմանի չէ: Այն պահին, երբ բոլոր գագաթներին հատկացվում է մասնաբաժին, և մենք նայեցինք բոլոր եզրերին, մենք ունենք լավ բաժանում:
Հաշվարկների մաքրություն
Haskell-ում մենք ենթադրում ենք, որ բոլոր հաշվարկներն են մաքուր. Այնուամենայնիվ, եթե դա իսկապես այդպես լիներ, մենք էկրանին որևէ բան տպելու հնարավորություն չէինք ունենա: Ընդհանրապես, մաքուր հաշվարկներն այնքան ծույլ են, որ չկա մաքուր ինչ-որ բան հաշվարկելու պատճառներ. Ծրագրում կատարվող բոլոր հաշվարկները ինչ-որ կերպ պարտադրված են «անմաքուր» monad IO.
Մոնադները հաշվարկները ներկայացնելու միջոց են էֆեկտներ Հասքելում։ Բացատրելը, թե ինչպես են նրանք աշխատում, դուրս է այս գրառման շրջանակներից: Լավ և հստակ նկարագրությունը կարելի է կարդալ անգլերենով .
Այստեղ ես ուզում եմ նշել, որ եթե որոշ մոնադներ, ինչպիսիք են IO-ն, իրականացվում են կոմպիլյատորի մոգության միջոցով, գրեթե բոլոր մյուսները ներդրված են ծրագրային ապահովման մեջ, և դրանցում բոլոր հաշվարկները մաքուր են:
Շատ էֆեկտներ կան, և յուրաքանչյուրն ունի իր մոնադը: Սա շատ ուժեղ և գեղեցիկ տեսություն է. բոլոր մոնադներն իրականացնում են նույն ինտերֆեյսը: Մենք կխոսենք հետևյալ երեք մոնադների մասին.
- Կամ ea-ն հաշվարկ է, որը վերադարձնում է a տիպի արժեք կամ բացառություն է բացում e տիպից: Այս մոնադի վարքագիծը շատ նման է հրամայական լեզուներով բացառությունների մշակմանը. սխալները կարող են բռնվել կամ փոխանցվել: Հիմնական տարբերությունն այն է, որ մոնադը լիովին տրամաբանորեն իրականացվում է Haskell-ի ստանդարտ գրադարանում, մինչդեռ հրամայական լեզուները սովորաբար օգտագործում են օպերացիոն համակարգի մեխանիզմները:
- Sa վիճակը հաշվարկ է, որը վերադարձնում է a տիպի արժեք և հասանելի է s տեսակի փոփոխական վիճակին:
- Միգուցե ա. Գուցե մոնադն արտահայտում է հաշվարկ, որը կարող է ցանկացած պահի ընդհատվել՝ վերադարձնելով Ոչինչ: Այնուամենայնիվ, մենք կխոսենք MonadPlus դասի ներդրման մասին Maybe տեսակի համար, որն արտահայտում է հակառակ էֆեկտը՝ այն հաշվարկ է, որը ցանկացած պահի կարող է ընդհատվել՝ վերադարձնելով կոնկրետ արժեք։
Ալգորիթմի իրականացում
Մենք ունենք տվյալների երկու տեսակ՝ Graph a և Bigraph ab, որոնցից առաջինը ներկայացնում է a տիպի արժեքներով պիտակավորված գագաթներով գծապատկերներ, իսկ երկրորդը ներկայացնում է երկկողմանի գրաֆիկներ ձախակողմյան գագաթներով, որոնք պիտակավորված են a և աջ տիպի արժեքներով: - կողային գագաթները պիտակավորված b տեսակի արժեքներով:
Սրանք Alga գրադարանի տեսակներ չեն: Ալգան չունի չուղղորդված երկմաս գրաֆիկների ներկայացում: Պարզության համար ես այսպիսի տեսակներ եմ պատրաստել:
Մեզ անհրաժեշտ կլինեն նաև օգնականի գործառույթներ հետևյալ ստորագրություններով.
-- Список соседей данной вершины.
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-ի համար գուցե: Հիմնական տարբերությունն այն է, որ կամ կարող է վերադարձնել արժեք, եթե հաշվարկը չի դադարեցվել, և Maybe-ն այս դեպքում վերադարձնում է միայն այս մասին տեղեկություն: Քանի որ մեզ առանձին արժեք պետք չէ հաջողության համար (այն արդեն պահպանված է State-ում), մենք ընտրում ենք Գուցե: Եվ այն պահին, երբ պետք է համատեղել երկու մոնադների էֆեկտները, դրանք դուրս են գալիս , որոնք ճշգրիտ կերպով համատեղում են այս ազդեցությունները:
Ինչու՞ ընտրեցի նման բարդ տեսակ: Երկու պատճառ. Նախ, իրականացումը պարզվում է, որ շատ նման է հրամայականին: Երկրորդ, մենք պետք է շահարկենք վերադարձի արժեքը հակասության դեպքում ռեկուրսիայից վերադառնալիս՝ վերականգնելու տարօրինակ օղակը, ինչը շատ ավելի հեշտ է անել Maybe մոնադում:
Այսպիսով, մենք ստանում ենք այս իրականացումը:
{-# 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 vertex-ը:
- onEdge-ն այն հատվածն է, որտեղ մենք այցելում ենք եզր: Յուրաքանչյուր եզրի համար այն կոչվում է երկու անգամ: Այստեղ մենք ստուգում ենք, թե արդյոք մյուս կողմի գագաթն այցելել է, և այցելում ենք այն, եթե ոչ: Եթե այցելեք, մենք ստուգում ենք, թե արդյոք եզրը հակասական է: Եթե դա այդպես է, մենք վերադարձնում ենք արժեքը՝ ռեկուրսիոն կույտի ամենավերին մասը, որտեղ բոլոր մյուս գագաթները կտեղադրվեն վերադարձին:
- processVertex-ը ստուգում է յուրաքանչյուր գագաթի համար, թե արդյոք այն այցելել է, և աշխատում է դրա վրա, եթե ոչ:
- dfs-ը գործարկում է processVertex բոլոր գագաթներում:
Այսքանը.
INLINE բառի պատմությունը
INLINE բառը չի եղել ալգորիթմի առաջին ներդրման մեջ, այն հայտնվել է ավելի ուշ: Երբ ես փորձեցի գտնել ավելի լավ իրականացում, ես գտա, որ ոչ INLINE տարբերակը որոշ գրաֆիկների վրա նկատելիորեն ավելի դանդաղ էր: Հաշվի առնելով, որ իմաստային առումով ֆունկցիաները պետք է նույնը աշխատեն, սա ինձ շատ զարմացրեց։ Նույնիսկ տարօրինակ է, որ մեկ այլ մեքենայի վրա GHC-ի այլ տարբերակով նկատելի տարբերություն չկար:
Մեկ շաբաթ անցկացնելով GHC Core-ի ելքը կարդալուց հետո, ես կարողացա խնդիրը շտկել հստակ INLINE-ի մեկ տողով: GHC 8.4.4-ի և GHC 8.6.5-ի միջև ինչ-որ պահի, օպտիմիզատորը դադարեցրեց դա ինքնուրույն անել:
Ես չէի սպասում, որ նման կեղտ կհանդիպեմ Haskell ծրագրավորման մեջ։ Այնուամենայնիվ, նույնիսկ այսօր, օպտիմիզատորները երբեմն սխալվում են, և մեր խնդիրն է նրանց հուշումներ տալ: Օրինակ, այստեղ մենք գիտենք, որ ֆունկցիան պետք է ներգծված լինի, քանի որ այն ներգծված է հրամայական տարբերակում, և սա հիմք է կոմպիլյատորին հուշում տալու համար։
Ի՞նչ տեղի ունեցավ հետո:
Հետո ես ներդրեցի Hopcroft-Karp ալգորիթմը այլ մոնադների հետ, և դրանով ծրագիրը ավարտվեց։
Google Summer of Code-ի շնորհիվ ես ձեռք բերեցի գործնական փորձ ֆունկցիոնալ ծրագրավորման ոլորտում, որը ոչ միայն օգնեց ինձ պրակտիկա անցնել Ջեյն Սթրիթում հաջորդ ամառ (վստահ չեմ, թե որքան հայտնի է այս վայրը նույնիսկ Habr-ի բանիմաց լսարանի շրջանում, բայց դա մեկն է: այն քչերից, որտեղ դուք կարող եք ամառ զբաղվել ֆունկցիոնալ ծրագրավորմամբ), բայց նաև ինձ ներկայացրեց այս պարադիգմը գործնականում կիրառելու հրաշալի աշխարհը, որը զգալիորեն տարբերվում է ավանդական լեզուների իմ փորձից:
Source: www.habr.com