گزشتہ موسم گرما میں میں نے حصہ لیا - گوگل کے طلباء کے لیے ایک پروگرام۔ ہر سال، منتظمین کئی اوپن سورس پروجیکٹس کا انتخاب کرتے ہیں، بشمول ایسی معروف تنظیموں سے и . گوگل دنیا بھر کے طلباء کو ان پروجیکٹس پر کام کرنے کی دعوت دیتا ہے۔
گوگل سمر آف کوڈ 2019 میں ایک شریک کے طور پر، میں نے لائبریری کے اندر ایک پروجیکٹ کیا تنظیم کے ساتھ ، جو ہاسکل زبان کو ترقی دے رہی ہے - سب سے مشہور فنکشنل پروگرامنگ زبانوں میں سے ایک۔ الگا ایک لائبریری ہے جو نمائندگی کرتی ہے۔ ہاسکل میں گراف کی نمائندگی۔ یہ استعمال کیا جاتا ہے، مثال کے طور پر، میں - ایک گیتھب لائبریری جو کوڈ کی بنیاد پر سیمنٹک ٹری، کال اور انحصاری گراف بناتی ہے اور ان کا موازنہ کر سکتی ہے۔ میرا پروجیکٹ اس نمائندگی کے لیے دو طرفہ گرافس اور الگورتھم کے لیے ٹائپ سیف نمائندگی شامل کرنا تھا۔
اس پوسٹ میں میں ہاسکل میں دو طرفہ پن کے گراف کو چیک کرنے کے لیے الگورتھم کے اپنے نفاذ کے بارے میں بات کروں گا۔ اگرچہ الگورتھم سب سے بنیادی میں سے ایک ہے، اسے ایک فنکشنل انداز میں خوبصورتی سے لاگو کرنے میں مجھے کئی تکراریں لگیں اور کافی کام کی ضرورت پڑی۔ نتیجے کے طور پر، میں نے مونڈ ٹرانسفارمرز کے ساتھ عمل درآمد پر طے کیا۔
میرے بارے میں
میرا نام واسیلی الفروف ہے، میں سینٹ پیٹرزبرگ HSE میں چوتھے سال کا طالب علم ہوں۔ پہلے بلاگ میں لکھا تھا۔ и . اس وقت میں انٹرن شپ پر ہوں۔ ناروے میں، جہاں میں مسئلے کے حل پر کام کر رہا ہوں۔ . میری دلچسپیوں میں پیرامیٹرائزڈ الگورتھم اور فنکشنل پروگرامنگ شامل ہیں۔
الگورتھم کے نفاذ کے بارے میں
کردار
پروگرام میں حصہ لینے والے طلباء کو بلاگ کرنے کی بھرپور حوصلہ افزائی کی جاتی ہے۔ انہوں نے مجھے بلاگ کے لیے ایک پلیٹ فارم مہیا کیا۔ . یہ مضمون ترجمہ ہے۔ , میرے ذریعہ جولائی میں انگریزی میں لکھا گیا، ایک مختصر دیباچے کے ساتھ۔
سوال میں کوڈ کے ساتھ پل کی درخواست مل سکتی ہے۔ .
آپ میرے کام کے نتائج کے بارے میں پڑھ سکتے ہیں (انگریزی میں) .
اس پوسٹ کا مقصد قارئین کو فنکشنل پروگرامنگ کے بنیادی تصورات سے آشنا کرنا ہے، اگرچہ وقت آنے پر میں استعمال ہونے والی تمام اصطلاحات کو یاد کرنے کی کوشش کروں گا۔
دو طرفہ پن کے لیے گراف کی جانچ کرنا
دو طرفہ پن کے لیے گراف کی جانچ کرنے کے لیے ایک الگورتھم عام طور پر الگورتھم کے ایک کورس میں آسان ترین گراف الگورتھم میں سے ایک کے طور پر دیا جاتا ہے۔ اس کا خیال سیدھا ہے: پہلے ہم کسی نہ کسی طرح بائیں یا دائیں حصے میں عمودی جگہیں ڈالتے ہیں، اور جب کوئی متضاد کنارہ مل جاتا ہے، تو ہم دعویٰ کرتے ہیں کہ گراف دو طرفہ نہیں ہے۔
تھوڑی اور تفصیل: پہلے ہم بائیں حصے میں کچھ ورٹیکس ڈالتے ہیں۔ ظاہر ہے، اس چوٹی کے تمام پڑوسیوں کو دائیں لاب میں لیٹنا چاہیے۔ اس کے علاوہ، اس چوٹی کے پڑوسیوں کے تمام پڑوسیوں کو بائیں لاب میں لیٹنا ضروری ہے، اور اسی طرح. ہم عمودی حصوں کو اس وقت تک حصص تفویض کرنا جاری رکھتے ہیں جب تک کہ ہم نے اس کے ساتھ شروع کیے ہوئے ورٹیکس کے منسلک جزو میں اب بھی عمودی حصے موجود ہیں جن کے لیے ہم نے پڑوسیوں کو تفویض نہیں کیا ہے۔ پھر ہم اس عمل کو تمام منسلک اجزاء کے لیے دہراتے ہیں۔
اگر ایک ہی پارٹیشن میں گرنے والے عمودی حصوں کے درمیان کوئی کنارہ ہے تو، گراف میں ایک طاق سائیکل تلاش کرنا مشکل نہیں ہے، جو دو طرفہ گراف میں وسیع پیمانے پر جانا جاتا ہے (اور بالکل واضح طور پر) ناممکن ہے۔ بصورت دیگر، ہمارے پاس صحیح تقسیم ہے، جس کا مطلب ہے کہ گراف دو طرفہ ہے۔
عام طور پر، اس الگورتھم کو استعمال کرتے ہوئے لاگو کیا جاتا ہے۔ یا . لازمی زبانوں میں، گہرائی سے پہلی تلاش عام طور پر استعمال کی جاتی ہے کیونکہ یہ قدرے آسان ہے اور اضافی ڈیٹا ڈھانچے کی ضرورت نہیں ہے۔ میں نے گہرائی سے پہلی تلاش کا بھی انتخاب کیا کیونکہ یہ زیادہ روایتی ہے۔
اس طرح، ہم مندرجہ ذیل اسکیم پر آئے۔ ہم گہرائی کی پہلی تلاش کا استعمال کرتے ہوئے گراف کے چوٹیوں کو عبور کرتے ہیں اور ان کو حصص تفویض کرتے ہیں، جیسے جیسے ہم کنارے کے ساتھ آگے بڑھتے ہیں شیئر کی تعداد کو تبدیل کرتے ہیں۔ اگر ہم کسی ایسے ورٹیکس کو حصہ تفویض کرنے کی کوشش کرتے ہیں جس میں پہلے سے ہی ایک حصہ تفویض کیا گیا ہے، تو ہم محفوظ طریقے سے کہہ سکتے ہیں کہ گراف دو طرفہ نہیں ہے۔ جس لمحے تمام چوٹیوں کو ایک حصہ تفویض کیا جاتا ہے اور ہم نے تمام کناروں کو دیکھا ہے، ہمارے پاس ایک اچھی تقسیم ہے۔
حساب کی پاکیزگی
ہاسکل میں ہم فرض کرتے ہیں کہ تمام حسابات ہیں۔ صاف تاہم، اگر واقعی ایسا ہوتا، تو ہمارے پاس اسکرین پر کچھ بھی پرنٹ کرنے کا کوئی طریقہ نہیں ہوتا۔ بالکل، صاف حسابات اتنے سست ہیں کہ ایک بھی نہیں ہے۔ صاف کسی چیز کا حساب لگانے کی وجوہات۔ پروگرام میں ہونے والے تمام حسابات کسی نہ کسی طرح مجبور ہیں۔ "ناپاک" مونڈ آئی او۔
مونڈز حسابات کی نمائندگی کرنے کا ایک طریقہ ہیں۔ اثرات ہاسکل میں یہ بتانا کہ وہ کیسے کام کرتے ہیں اس پوسٹ کے دائرہ کار سے باہر ہے۔ انگریزی میں اچھی اور واضح تفصیل پڑھی جا سکتی ہے۔ .
یہاں میں یہ بتانا چاہتا ہوں کہ اگرچہ کچھ مونڈز، جیسے IO، کو کمپائلر میجک کے ذریعے لاگو کیا جاتا ہے، تقریباً تمام دیگر سافٹ ویئر میں لاگو ہوتے ہیں اور ان میں تمام حسابات خالص ہوتے ہیں۔
بہت سارے اثرات ہیں اور ہر ایک کا اپنا مونڈ ہے۔ یہ ایک بہت مضبوط اور خوبصورت نظریہ ہے: تمام مونڈ ایک ہی انٹرفیس کو نافذ کرتے ہیں۔ ہم مندرجہ ذیل تین مونڈز کے بارے میں بات کریں گے:
- یا تو ea ایک حساب ہے جو قسم a کی قدر لوٹاتا ہے یا قسم e کی رعایت دیتا ہے۔ اس مونڈ کا طرز عمل لازمی زبانوں میں مستثنیٰ ہینڈلنگ سے بہت ملتا جلتا ہے: غلطیوں کو پکڑا یا آگے بڑھایا جا سکتا ہے۔ بنیادی فرق یہ ہے کہ مونڈ کو مکمل طور پر منطقی طور پر ہاسکل میں معیاری لائبریری میں لاگو کیا جاتا ہے، جبکہ لازمی زبانیں عام طور پر آپریٹنگ سسٹم کے طریقہ کار کا استعمال کرتی ہیں۔
- اسٹیٹ sa ایک ایسا حساب ہے جو قسم a کی قدر لوٹاتا ہے اور اسے s قسم کی تغیر پذیر حالت تک رسائی حاصل ہے۔
- شاید ایک. Maybe monad ایک کمپیوٹیشن کا اظہار کرتا ہے جسے کسی بھی وقت Nothing واپس کر کے روکا جا سکتا ہے۔ تاہم، ہم Maybe قسم کے لیے 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)یہ دیکھنا آسان ہے کہ اگر گہرائی کی پہلی تلاش کے دوران ہمیں ایک متضاد کنارہ ملتا ہے، تو عجیب چکر تکرار کے اسٹیک کے اوپر ہوتا ہے۔ اس طرح، اسے بحال کرنے کے لیے، ہمیں ریکریشن اسٹیک سے لے کر آخری ورٹیکس کی پہلی موجودگی تک ہر چیز کو کاٹنا ہوگا۔
ہم ہر چوٹی کے لیے شیئر نمبرز کی ایک ایسوسی ایٹیو صف کو برقرار رکھ کر گہرائی سے پہلی تلاش کو نافذ کرتے ہیں۔ ریکسریشن اسٹیک خود بخود منڈ کے فنیکٹر کلاس کے نفاذ کے ذریعے برقرار رکھا جائے گا جس کا ہم نے انتخاب کیا ہے: ہمیں صرف راستے سے تمام چوٹیوں کو تکراری فنکشن سے واپس آنے والے نتیجے میں ڈالنے کی ضرورت ہوگی۔
میرا پہلا خیال Either monad استعمال کرنا تھا، جو ایسا لگتا ہے کہ بالکل وہی اثرات مرتب کرتا ہے جن کی ہمیں ضرورت ہے۔ میں نے جو پہلا نفاذ لکھا وہ اس اختیار کے بہت قریب تھا۔ درحقیقت، میرے پاس ایک موقع پر پانچ مختلف نفاذ تھے اور آخر کار ایک دوسرے پر طے ہو گئے۔
سب سے پہلے، ہمیں شیئر شناخت کنندگان کی ایک ایسوسی ایٹیو صف کو برقرار رکھنے کی ضرورت ہے - یہ ریاست کے بارے میں کچھ ہے۔ دوم، ہمیں تنازعہ کا پتہ چلنے پر روکنے کے قابل ہونا چاہیے۔ یہ یا تو Monad for Either، یا 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 وہ حصہ ہے جہاں ہم کنارے پر جاتے ہیں۔ اسے ہر کنارے کے لیے دو بار کہا جاتا ہے۔ یہاں ہم چیک کرتے ہیں کہ آیا دوسری طرف کی چوٹی کا دورہ کیا گیا ہے، اور اگر نہیں تو اسے دیکھیں۔ اگر ملاحظہ کیا جائے تو ہم چیک کرتے ہیں کہ آیا کنارہ متضاد ہے۔ اگر ایسا ہے تو، ہم قدر واپس کرتے ہیں - تکرار اسٹیک کے بالکل اوپر، جہاں واپسی پر باقی تمام چوٹیوں کو رکھا جائے گا۔
- پروسیس ورٹیکس ہر ایک چوٹی کے لیے چیک کرتا ہے کہ آیا اس کا دورہ کیا گیا ہے اور اگر نہیں تو اس پر ورٹیکس چلتا ہے۔
- dfs تمام چوٹیوں پر پروسیس ورٹیکس چلاتا ہے۔
بس۔
لفظ INLINE کی تاریخ
لفظ INLINE الگورتھم کے پہلے نفاذ میں نہیں تھا؛ یہ بعد میں ظاہر ہوا۔ جب میں نے بہتر نفاذ تلاش کرنے کی کوشش کی تو مجھے معلوم ہوا کہ غیر ان لائن ورژن کچھ گرافس پر نمایاں طور پر سست تھا۔ اس بات پر غور کرتے ہوئے کہ لفظی طور پر افعال کو یکساں کام کرنا چاہئے، اس نے مجھے بہت حیران کیا۔ یہاں تک کہ اجنبی، GHC کے مختلف ورژن والی دوسری مشین پر کوئی قابل توجہ فرق نہیں تھا۔
GHC کور آؤٹ پٹ کو پڑھنے میں ایک ہفتہ گزارنے کے بعد، میں واضح INLINE کی ایک لائن سے مسئلہ حل کرنے میں کامیاب ہو گیا۔ GHC 8.4.4 اور GHC 8.6.5 کے درمیان کسی وقت آپٹمائزر نے خود ہی ایسا کرنا چھوڑ دیا۔
مجھے ہاسکل پروگرامنگ میں اس طرح کی گندگی کا سامنا کرنے کی توقع نہیں تھی۔ تاہم، آج بھی، اصلاح کرنے والے بعض اوقات غلطیاں کرتے ہیں، اور انہیں اشارے دینا ہمارا کام ہے۔ مثال کے طور پر، یہاں ہم جانتے ہیں کہ فنکشن کو ان لائن ہونا چاہیے کیونکہ یہ لازمی ورژن میں ان لائن ہے، اور یہ کمپائلر کو اشارہ دینے کی ایک وجہ ہے۔
آگے کیا ہوا؟
پھر میں نے Hopcroft-Karp الگورتھم کو دوسرے مونڈز کے ساتھ لاگو کیا، اور یہ پروگرام کا اختتام تھا۔
گوگل سمر آف کوڈ کی بدولت، میں نے فنکشنل پروگرامنگ کا عملی تجربہ حاصل کیا، جس نے نہ صرف مجھے اگلے موسم گرما میں جین اسٹریٹ میں انٹرنشپ حاصل کرنے میں مدد کی (مجھے یقین نہیں ہے کہ یہ جگہ حبر کے جاننے والے سامعین میں بھی کتنی مشہور ہے، لیکن یہ ایک ہے ان چند میں سے جہاں آپ فنکشنل پروگرامنگ میں مشغول ہونے کے لیے موسم گرما میں شامل ہو سکتے ہیں) بلکہ اس پیراڈائم کو عملی طور پر لاگو کرنے کی شاندار دنیا سے بھی متعارف کرایا، جو روایتی زبانوں میں میرے تجربے سے نمایاں طور پر مختلف ہے۔
ماخذ: www.habr.com