గత వేసవిలో నేను పాల్గొన్నాను - Google నుండి విద్యార్థుల కోసం ఒక ప్రోగ్రామ్. ప్రతి సంవత్సరం, నిర్వాహకులు అనేక ఓపెన్ సోర్స్ ప్రాజెక్ట్‌లను ఎంచుకుంటారు и . ఈ ప్రాజెక్ట్‌లలో పని చేయడానికి ప్రపంచవ్యాప్తంగా ఉన్న విద్యార్థులను Google ఆహ్వానిస్తుంది.
Google సమ్మర్ ఆఫ్ కోడ్ 2019లో భాగస్వామిగా, నేను లైబ్రరీలో ఒక ప్రాజెక్ట్ చేసాను సంస్థతో , ఇది హాస్కెల్ భాషను అభివృద్ధి చేస్తోంది - అత్యంత ప్రసిద్ధ ఫంక్షనల్ ప్రోగ్రామింగ్ భాషలలో ఒకటి. ఆల్గా ప్రాతినిధ్యం వహించే లైబ్రరీ హాస్కెల్‌లో గ్రాఫ్‌ల కోసం ప్రాతినిధ్యం. ఇది ఉపయోగించబడుతుంది, ఉదాహరణకు, లో — కోడ్ ఆధారంగా సెమాంటిక్ ట్రీలు, కాల్ మరియు డిపెండెన్సీ గ్రాఫ్‌లను రూపొందించే గితుబ్ లైబ్రరీ మరియు వాటిని పోల్చవచ్చు. నా ప్రాజెక్ట్ బైపార్టైట్ గ్రాఫ్‌లు మరియు ఆ ప్రాతినిధ్యం కోసం అల్గారిథమ్‌ల కోసం టైప్-సురక్షిత ప్రాతినిధ్యాన్ని జోడించడం.
ఈ పోస్ట్‌లో నేను హాస్కెల్‌లో ద్వైపాక్షికత కోసం గ్రాఫ్‌ని తనిఖీ చేయడానికి అల్గోరిథం యొక్క నా అమలు గురించి మాట్లాడతాను. అల్గోరిథం చాలా ప్రాథమికమైనది అయినప్పటికీ, దానిని ఫంక్షనల్ స్టైల్‌లో అందంగా అమలు చేయడానికి నాకు అనేక పునరావృత్తులు మరియు చాలా పని అవసరం. ఫలితంగా, నేను మోనాడ్ ట్రాన్స్‌ఫార్మర్‌లతో అమలు చేయడంపై స్థిరపడ్డాను.
నా గురించి
నా పేరు వాసిలీ అల్ఫెరోవ్, నేను సెయింట్ పీటర్స్‌బర్గ్ HSEలో నాల్గవ సంవత్సరం విద్యార్థిని. ఇంతకు ముందు బ్లాగులో రాశాను и . ప్రస్తుతం నేను ఇంటర్న్‌షిప్‌లో ఉన్నాను నార్వేలో, నేను సమస్యకు సంబంధించిన విధానాలపై పని చేస్తున్నాను . నా ఆసక్తులలో పారామీటరైజ్డ్ అల్గారిథమ్‌లు మరియు ఫంక్షనల్ ప్రోగ్రామింగ్ ఉన్నాయి.
అల్గోరిథం అమలు గురించి
ముందుమాట
కార్యక్రమంలో పాల్గొనే విద్యార్థులు బ్లాగ్ చేయడానికి గట్టిగా ప్రోత్సహించబడ్డారు. వారు నాకు బ్లాగుకు వేదికను అందించారు . ఈ వ్యాసం అనువాదం , నేను అక్కడ జూలైలో ఆంగ్లంలో చిన్న ముందుమాటతో వ్రాసాను.
ప్రశ్నలోని కోడ్‌తో పుల్ రిక్వెస్ట్ కనుగొనవచ్చు .
మీరు నా పని ఫలితాల గురించి చదువుకోవచ్చు (ఇంగ్లీష్‌లో) .
ఈ పోస్ట్ ఫంక్షనల్ ప్రోగ్రామింగ్‌లోని ప్రాథమిక భావనలతో పాఠకులకు పరిచయం చేయడానికి ఉద్దేశించబడింది, అయినప్పటికీ నేను సమయం వచ్చినప్పుడు ఉపయోగించిన అన్ని పదాలను గుర్తుకు తెచ్చుకోవడానికి ప్రయత్నిస్తాను.
ద్వైపాక్షికత కోసం గ్రాఫ్‌లను తనిఖీ చేస్తోంది
ద్వైపాక్షికత కోసం గ్రాఫ్‌ని తనిఖీ చేయడానికి ఒక అల్గోరిథం సాధారణంగా అల్గారిథమ్‌లపై ఒక కోర్సులో సరళమైన గ్రాఫ్ అల్గారిథమ్‌లలో ఒకటిగా ఇవ్వబడుతుంది. అతని ఆలోచన సూటిగా ఉంటుంది: మొదట మనం ఏదో ఒకవిధంగా ఎడమ లేదా కుడి వాటాలో శీర్షాలను ఉంచుతాము మరియు విరుద్ధమైన అంచు కనుగొనబడినప్పుడు, గ్రాఫ్ ద్వైపాక్షికం కాదని మేము నొక్కిచెప్పాము.
కొంచెం వివరంగా: మొదట మనం ఎడమ వాటాలో కొంత శీర్షాన్ని ఉంచాము. సహజంగానే, ఈ శీర్షం యొక్క అన్ని పొరుగువారు తప్పనిసరిగా కుడి లోబ్‌లో ఉండాలి. ఇంకా, ఈ శీర్షం యొక్క పొరుగువారి పొరుగువారందరూ తప్పనిసరిగా ఎడమ లోబ్‌లో ఉండాలి మరియు మొదలైనవి. మేము ప్రారంభించిన శీర్షం యొక్క కనెక్ట్ చేయబడిన కాంపోనెంట్‌లో పొరుగువారికి కేటాయించని శీర్షాలు ఉన్నంత వరకు మేము శీర్షాలకు షేర్‌లను కేటాయించడం కొనసాగిస్తాము. మేము కనెక్ట్ చేయబడిన అన్ని భాగాల కోసం ఈ చర్యను పునరావృతం చేస్తాము.
ఒకే విభజనలోకి వచ్చే శీర్షాల మధ్య అంచు ఉన్నట్లయితే, గ్రాఫ్‌లో బేసి చక్రాన్ని కనుగొనడం కష్టం కాదు, ఇది బైపార్టైట్ గ్రాఫ్‌లో విస్తృతంగా తెలిసిన (మరియు చాలా స్పష్టంగా) అసాధ్యం. లేకపోతే, మనకు సరైన విభజన ఉంది, అంటే గ్రాఫ్ ద్విపార్టీ అని అర్థం.
సాధారణంగా, ఈ అల్గోరిథం ఉపయోగించి అమలు చేయబడుతుంది లేదా . అత్యవసర భాషలలో, డెప్త్-ఫస్ట్ శోధన సాధారణంగా ఉపయోగించబడుతుంది ఎందుకంటే ఇది కొంచెం సరళమైనది మరియు అదనపు డేటా నిర్మాణాలు అవసరం లేదు. నేను డెప్త్-ఫస్ట్ సెర్చ్‌ని కూడా ఎంచుకున్నాను, ఎందుకంటే ఇది మరింత సాంప్రదాయంగా ఉంది.
కాబట్టి, మేము ఈ క్రింది పథకానికి వచ్చాము. మేము డెప్త్-ఫస్ట్ సెర్చ్‌ని ఉపయోగించి గ్రాఫ్ యొక్క శీర్షాలను దాటుతాము మరియు వాటికి షేర్‌లను కేటాయిస్తాము, మేము అంచున కదులుతున్నప్పుడు వాటా సంఖ్యను మారుస్తాము. మేము ఇప్పటికే కేటాయించిన వాటాను కలిగి ఉన్న శీర్షానికి వాటాను కేటాయించడానికి ప్రయత్నిస్తే, గ్రాఫ్ ద్విపార్టీ కాదని మేము సురక్షితంగా చెప్పగలము. అన్ని శీర్షాలకు వాటా కేటాయించబడిన క్షణం మరియు మేము అన్ని అంచులను పరిశీలించాము, మాకు మంచి విభజన ఉంది.
లెక్కల స్వచ్ఛత
హాస్కెల్‌లో మేము అన్ని లెక్కలు అని ఊహిస్తాము శుభ్రంగా. అయితే, ఇది నిజంగా జరిగితే, స్క్రీన్‌పై ఏదైనా ముద్రించడానికి మాకు మార్గం ఉండదు. అస్సలు, శుభ్రంగా లెక్కలు చాలా సోమరిగా ఉన్నాయి, ఒకటి లేదు శుభ్రంగా ఏదో లెక్కించడానికి కారణాలు. ప్రోగ్రామ్‌లో సంభవించే అన్ని లెక్కలు ఏదో ఒకవిధంగా బలవంతంగా ఉంటాయి "అపరిశుభ్రమైన" మొనాడ్ IO.
మొనాడ్స్ అనేది గణనలను సూచించడానికి ఒక మార్గం ప్రభావాలు హాస్కెల్‌లో. అవి ఎలా పని చేస్తాయో వివరించడం ఈ పోస్ట్ పరిధికి మించినది. మంచి మరియు స్పష్టమైన వివరణను ఆంగ్లంలో చదవవచ్చు .
IO వంటి కొన్ని మొనాడ్‌లు కంపైలర్ మాయాజాలం ద్వారా అమలు చేయబడినప్పటికీ, మిగతావన్నీ సాఫ్ట్‌వేర్‌లో అమలు చేయబడతాయి మరియు వాటిలోని అన్ని లెక్కలు స్వచ్ఛమైనవని ఇక్కడ నేను సూచించాలనుకుంటున్నాను.
చాలా ప్రభావాలు ఉన్నాయి మరియు ప్రతి దాని స్వంత మొనాడ్ ఉంది. ఇది చాలా బలమైన మరియు అందమైన సిద్ధాంతం: అన్ని మొనాడ్‌లు ఒకే ఇంటర్‌ఫేస్‌ను అమలు చేస్తాయి. మేము ఈ క్రింది మూడు మొనాడ్ల గురించి మాట్లాడుతాము:
- ea అనేది టైప్ a విలువను తిరిగి ఇచ్చే గణన లేదా రకం eకి మినహాయింపుని విసురుతుంది. ఈ మొనాడ్ యొక్క ప్రవర్తన అత్యవసర భాషలలో మినహాయింపు నిర్వహణకు చాలా పోలి ఉంటుంది: లోపాలను పట్టుకోవచ్చు లేదా పాస్ చేయవచ్చు. ప్రధాన వ్యత్యాసం ఏమిటంటే, హాస్కెల్‌లోని ప్రామాణిక లైబ్రరీలో మొనాడ్ పూర్తిగా తార్కికంగా అమలు చేయబడుతుంది, అయితే అత్యవసర భాషలు సాధారణంగా ఆపరేటింగ్ సిస్టమ్ మెకానిజమ్‌లను ఉపయోగిస్తాయి.
- స్టేట్ sa అనేది టైప్ a విలువను అందించే గణన మరియు s రకం యొక్క మార్చదగిన స్థితికి యాక్సెస్‌ను కలిగి ఉంటుంది.
- బహుశా ఎ. నథింగ్ రిటర్న్ చేయడం ద్వారా ఎప్పుడైనా అంతరాయం కలిగించే గణనను బహుశా మొనాడ్ వ్యక్తపరుస్తుంది. అయినప్పటికీ, మేము మోనాడ్‌ప్లస్ తరగతిని అమలు చేయడం గురించి మాట్లాడతాము, ఇది వ్యతిరేక ప్రభావాన్ని వ్యక్తపరుస్తుంది: ఇది నిర్దిష్ట విలువను తిరిగి ఇవ్వడం ద్వారా ఎప్పుడైనా అంతరాయం కలిగించే గణన.
అల్గోరిథం యొక్క అమలు
మాకు రెండు డేటా రకాలు ఉన్నాయి, గ్రాఫ్ a మరియు Bigraph ab, వీటిలో మొదటిది టైప్ a విలువలతో లేబుల్ చేయబడిన శీర్షాలతో గ్రాఫ్‌లను సూచిస్తుంది మరియు రెండవది టైప్ a మరియు కుడి విలువలతో లేబుల్ చేయబడిన ఎడమ వైపు శీర్షాలతో ద్విపార్టీ గ్రాఫ్‌లను సూచిస్తుంది. -టైప్ బి విలువలతో లేబుల్ చేయబడిన సైడ్ శీర్షాలు.
ఇవి ఆల్గా లైబ్రరీ నుండి వచ్చిన రకాలు కాదు. మళ్లించబడని ద్విపార్టీ గ్రాఫ్‌లకు ఆల్గా ప్రాతినిధ్యం లేదు. నేను స్పష్టత కోసం ఇలాంటి రకాలను తయారు చేసాను.
కింది సంతకాలతో మాకు సహాయక విధులు కూడా అవసరం:
-- Список соседей данной вершины.
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)లోతు-మొదటి శోధన సమయంలో మేము విరుద్ధమైన అంచుని కనుగొన్నట్లయితే, బేసి చక్రం రికర్షన్ స్టాక్ పైన ఉందని చూడటం సులభం. అందువల్ల, దాన్ని పునరుద్ధరించడానికి, మేము రికర్షన్ స్టాక్ నుండి చివరి శీర్షం యొక్క మొదటి సంఘటన వరకు ప్రతిదీ కత్తిరించాలి.
మేము ప్రతి శీర్షానికి సంబంధించిన షేర్ నంబర్‌ల అనుబంధ శ్రేణిని నిర్వహించడం ద్వారా లోతు-మొదటి శోధనను అమలు చేస్తాము. మేము ఎంచుకున్న మొనాడ్ యొక్క ఫంక్టార్ క్లాస్ అమలు చేయడం ద్వారా రికర్షన్ స్టాక్ స్వయంచాలకంగా నిర్వహించబడుతుంది: మేము పునరావృత ఫంక్షన్ నుండి తిరిగి వచ్చిన ఫలితంలో మార్గం నుండి అన్ని శీర్షాలను మాత్రమే ఉంచాలి.
నా మొదటి ఆలోచన ఏమిటంటే గాని మొనాడ్‌ను ఉపయోగించడం, ఇది మనకు అవసరమైన ప్రభావాలను ఖచ్చితంగా అమలు చేస్తుంది. నేను వ్రాసిన మొదటి అమలు ఈ ఎంపికకు చాలా దగ్గరగా ఉంది. వాస్తవానికి, నేను ఒక సమయంలో ఐదు వేర్వేరు అమలులను కలిగి ఉన్నాను మరియు చివరికి మరొకదానిపై స్థిరపడ్డాను.
ముందుగా, మనం షేర్ ఐడెంటిఫైయర్‌ల అనుబంధ శ్రేణిని నిర్వహించాలి - ఇది రాష్ట్రం గురించిన విషయం. రెండవది, వైరుధ్యం కనుగొనబడినప్పుడు మనం ఆపగలగాలి. ఇది మోనాడ్ కావచ్చు లేదా మోనాడ్‌ప్లస్ కావచ్చు. ప్రధాన వ్యత్యాసం ఏమిటంటే, గణన ఆపివేయబడకపోతే విలువను తిరిగి ఇవ్వవచ్చు మరియు ఈ సందర్భంలో దీని గురించి సమాచారాన్ని మాత్రమే అందిస్తుంది. విజయం కోసం మాకు ప్రత్యేక విలువ అవసరం లేదు కాబట్టి (ఇది ఇప్పటికే రాష్ట్రంలో నిల్వ చేయబడింది), మేము మేబీని ఎంచుకుంటాము. మరియు మేము రెండు మొనాడ్ల ప్రభావాలను మిళితం చేయాల్సిన సమయంలో, అవి బయటకు వస్తాయి , ఇది ఖచ్చితంగా ఈ ప్రభావాలను మిళితం చేస్తుంది.
నేను అలాంటి సంక్లిష్ట రకాన్ని ఎందుకు ఎంచుకున్నాను? రెండు కారణాలు. మొదట, అమలు చాలా అవసరం అని తేలింది. రెండవది, బేసి లూప్‌ను పునరుద్ధరించడానికి పునరావృతం నుండి తిరిగి వచ్చినప్పుడు వైరుధ్యం సంభవించినప్పుడు మేము రిటర్న్ విలువను మార్చవలసి ఉంటుంది, ఇది బహుశా మోనాడ్‌లో చేయడం చాలా సులభం.
కాబట్టి మేము ఈ అమలును పొందుతాము.
{-# 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 అన్ని శీర్షాలపై ప్రాసెస్‌వర్టెక్స్‌ను నడుపుతుంది.
అంతే.
INLINE అనే పదం యొక్క చరిత్ర
INLINE అనే పదం అల్గోరిథం యొక్క మొదటి అమలులో లేదు; అది తర్వాత కనిపించింది. నేను మెరుగైన అమలును కనుగొనడానికి ప్రయత్నించినప్పుడు, కొన్ని గ్రాఫ్‌లలో నాన్-ఇన్‌లైన్ వెర్షన్ గమనించదగినంత నెమ్మదిగా ఉందని నేను కనుగొన్నాను. సెమాంటిక్‌గా విధులు ఒకే విధంగా పనిచేయాలని పరిగణనలోకి తీసుకుంటే, ఇది నన్ను చాలా ఆశ్చర్యపరిచింది. అపరిచితుడు, GHC యొక్క విభిన్న వెర్షన్‌తో ఉన్న మరొక మెషీన్‌లో గుర్తించదగిన తేడా లేదు.
GHC కోర్ అవుట్‌పుట్ చదివిన వారం రోజుల తర్వాత, నేను స్పష్టమైన INLINE యొక్క ఒక లైన్‌తో సమస్యను పరిష్కరించగలిగాను. GHC 8.4.4 మరియు GHC 8.6.5 మధ్య ఏదో ఒక సమయంలో ఆప్టిమైజర్ దీన్ని స్వయంగా చేయడం ఆపివేసింది.
హాస్కెల్ ప్రోగ్రామింగ్‌లో ఇలాంటి చెత్త ఎదురవుతుందని నేను ఊహించలేదు. అయినప్పటికీ, నేటికీ, ఆప్టిమైజర్‌లు కొన్నిసార్లు తప్పులు చేస్తారు మరియు వారికి సూచనలు ఇవ్వడం మా పని. ఉదాహరణకు, ఫంక్షన్ ఇంపెరేటివ్ వెర్షన్‌లో ఇన్‌లైన్ చేయబడిందని ఇక్కడ మనకు తెలుసు మరియు కంపైలర్‌కు సూచనను అందించడానికి ఇది ఒక కారణం.
తరువాత ఏం జరిగింది?
అప్పుడు నేను ఇతర మోనాడ్‌లతో హాప్‌క్రాఫ్ట్-కార్ప్ అల్గోరిథంను అమలు చేసాను మరియు అది ప్రోగ్రామ్ ముగింపు.
Google సమ్మర్ ఆఫ్ కోడ్‌కు ధన్యవాదాలు, నేను ఫంక్షనల్ ప్రోగ్రామింగ్‌లో ఆచరణాత్మక అనుభవాన్ని పొందాను, ఇది తరువాతి వేసవిలో జేన్ స్ట్రీట్‌లో ఇంటర్న్‌షిప్ పొందడానికి నాకు సహాయపడింది (ఈ స్థలం హబ్ర్ యొక్క పరిజ్ఞానం ఉన్న ప్రేక్షకులలో కూడా ఎంత ప్రసిద్ధి చెందిందో నాకు ఖచ్చితంగా తెలియదు, కానీ ఇది ఒకటి మీరు వేసవిలో ఫంక్షనల్ ప్రోగ్రామింగ్‌లో పాల్గొనగలిగే కొన్నింటిలో), కానీ ఈ నమూనాను ఆచరణలో వర్తింపజేసే అద్భుతమైన ప్రపంచానికి నన్ను పరిచయం చేసారు, సాంప్రదాయ భాషలలో నా అనుభవానికి భిన్నంగా.
మూలం: www.habr.com